Efficient Homomorphic Evaluation of Arbitrary Bivariate Integer Functions
Daisuke Maeda, Koki Morimura, Takashi Nishide · 2022
We propose how to homomorphically evaluate arbitrary bivariate integer functions such as division. A prior work proposed by Okada et al.\ (WISTP'18) uses polynomial evaluations such that the scheme is still compatible with the SIMD operations in BFV and BGV, and is implemented with the input domain size \mathbbZ _257 . However, the scheme of Okada et al.\ requires the quadratic number of plaintext-ciphertext multiplications and ciphertext-ciphertext additions in the input domain size, and although these operations are more lightweight than the ciphertext-ciphertext multiplication, the quadratic complexity makes handling larger inputs quite inefficient. In this work, first we improve the prior work and also propose a new approach that exploits the packing method to handle the larger input domain size instead of enabling the SIMD operation, thus making it possible to work with the larger input domain size, e.g., \mathbbZ _2^15 in a reasonably efficient way. In addition, we show how to extend the input domain size to \mathbbZ _2^16 with a relatively moderate overhead. We implement the prior work of Okada et al., our improved scheme of Okada et al., and our new scheme in PALISADE with the input domain size \mathbbZ _2^15 , and confirm that the estimated run-times of the prior work and our improved scheme of the prior work are still about 117 days and 59 days respectively while our new scheme can be computed in 307 seconds.