Paper 2022/280

Efficient Homomorphic Evaluation on Large Interval

Jung Hee Cheon, Wootae Kim, and Jai Hyun Park

Abstract

Homomorphic encryption (HE) is being widely used for privacy-preserving computation. Since HE schemes only support polynomial operations, it is prevalent to use polynomial approximations of non-polynomial functions. We cannot monitor the intermediate values during the evaluation; as a consequence, we should utilize polynomial approximations with sufficiently large approximation intervals to prevent the failure of the evaluation. However, the large approximation interval potentially accompanies computational overhead, and it is a serious bottleneck of HE application on real data. In this work, we introduce domain extension polynomials (DEPs) that extend the domain interval of functions by a factor of $k$ while preserving the feature of the original function on its original domain interval. By repeatedly iterating the domain-extension process with DEPs, we can extend with $O(\log{K})$ multiplications the domain of given function by a factor of $K$ while the feature of the original function is preserved on its original domain interval. By using DEPs, we can efficiently evaluate in encrypted state a function that converges at infinities. To uniformly approximate the function on $[-R,R]$, our method exploits $O(\log{R})$ multiplications and $O(1)$ memory. This is more efficient than the current best approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses $O(\sqrt{R})$ multiplications and $O(\sqrt{R})$ memory for the evaluation. As another application of DEPs, we also suggest a method to manage the risky outliers from a wide interval $[-R,R]$ by using $O(\log{R})$ additional multiplications. As a real-world application, we exploit our uniform approximation of the logistic function on wide intervals to logistic regression. We trained the model on large public datasets in encrypted state using the polynomial approximation of the logistic function on $[-7683,7683]$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Homomorphic encryptionComposite polynomial approximation
Contact author(s)
jhyunp @ snu ac kr
History
2022-03-02: received
Short URL
https://ia.cr/2022/280
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/280,
      author = {Jung Hee Cheon and Wootae Kim and Jai Hyun Park},
      title = {Efficient Homomorphic Evaluation on Large Interval},
      howpublished = {Cryptology ePrint Archive, Paper 2022/280},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/280}},
      url = {https://eprint.iacr.org/2022/280}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.