Linear Depth Integer-Wise Homomorphic Division - Information Security Theory and Practice
Conference Papers Year : 2019

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.
Fichier principal
Vignette du fichier
484602_1_En_8_Chapter.pdf (546.12 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02294597 , version 1 (23-09-2019)

Licence

Identifiers

Cite

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⟩
189 View
182 Download

Altmetric

Share

More