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(l2)
Origin | Files produced by the author(s) |
---|