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 metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02294597
Contributor : Hal Ifip <>
Submitted on : Monday, September 23, 2019 - 3:49:26 PM
Last modification on : Monday, September 23, 2019 - 3:52:11 PM

File

 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

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

10