Skip to Main content Skip to Navigation
Conference papers

Linear Depth Integer-Wise Homomorphic Division

Abstract : We propose a secure integer-wise homomorphic division algorithm on fully homomorphic encryption schemes (FHE). For integer-wise algorithms, we encrypt plaintexts as integers without encoding them into bit values, while in bit-wise algorithms, plaintexts are encoded into binary and bit values are encrypted one by one. All the publicly available division algorithms are constructed in bit-wise style, and to the best of our knowledge there are no known integer-wise algorithm for secure division. We derive some empirical results on the FHE library HElib and show that our algorithm is 2.45x faster than the fastest bit-wise algorithm. We also show that the multiplicative depth of our algorithm is O(l), where l is the integer bit length, while that of existing division algorithms is $$O(l^2)$$. Furthermore, we generalise our secure division algorithm and propose a method for secure calculation of a general 2-variable function. The order of multiplicative depth of the algorithm, which is a main factor of the complexity of a FHE algorithm, is exactly the same as our secure division algorithm.
Document type :
Conference papers
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Monday, September 23, 2019 - 3:49:26 PM
Last modification on : Monday, September 23, 2019 - 3:52:11 PM
Long-term archiving on: : Sunday, February 9, 2020 - 1:27:39 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Hiroki Okada, Carlos Cid, Seira Hidano, Shinsaku Kiyomoto. Linear Depth Integer-Wise Homomorphic Division. 12th IFIP International Conference on Information Security Theory and Practice (WISTP), Dec 2018, Brussels, Belgium. pp.91-106, ⟨10.1007/978-3-030-20074-9_8⟩. ⟨hal-02294597⟩



Record views