Paper 2023/366

Efficient Homomorphic Evaluation of Arbitrary Uni/Bivariate Integer Functions and Their Applications

Daisuke Maeda, University of Tsukuba
Koki Morimura, University of Tsukuba
Shintaro Narisada, KDDI Research, Inc.
Kazuhide Fukushima, KDDI Research, Inc.
Takashi Nishide, University of Tsukuba
Abstract

We propose how to homomorphically evaluate arbitrary univariate and 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 $\mathbb{Z}_{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., $\mathbb{Z}_{2^{15}}$ in a reasonably efficient way. In addition, we show how to slightly extend the input domain size to $\mathbb{Z}_{2^{16}}$ with a relatively moderate overhead. Further we show another approach to handling the larger input domain size by using two ciphertexts to encrypt one integer plaintext and applying our techniques for uni/bivariate function evaluation. 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 $\mathbb{Z}_{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.

Note: This is the full version including a new appendix.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. WAHC 2022 - 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography
DOI
10.1145/3560827.3563378
Keywords
Fully Homomorphic EncryptionEvaluation of Non-Linear Function
Contact author(s)
nishide @ risk tsukuba ac jp
History
2023-03-16: approved
2023-03-14: received
See all versions
Short URL
https://ia.cr/2023/366
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/366,
      author = {Daisuke Maeda and Koki Morimura and Shintaro Narisada and Kazuhide Fukushima and Takashi Nishide},
      title = {Efficient Homomorphic Evaluation of Arbitrary Uni/Bivariate Integer Functions and Their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/366},
      year = {2023},
      doi = {10.1145/3560827.3563378},
      note = {\url{https://eprint.iacr.org/2023/366}},
      url = {https://eprint.iacr.org/2023/366}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.