Paper 2022/280

Efficient Homomorphic Evaluation on Large Intervals

Jung Hee Cheon, Seoul National University
Wootae Kim, Seoul National University
Jai Hyun Park, Seoul National University

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 homomorphic 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 overheads, and it is a serious bottleneck of HE application on real-world 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})$ operations the domain of a given function by a factor of $K$ while the feature of the original function is preserved in its original domain interval. By using DEPs, we can efficiently evaluate in an encrypted state a function that converges at infinities, i.e., $\lim_{x\to\infty}f(x)$ and $\lim_{x\to-\infty}f(x)$ exist in $\mathbb{R}$. To uniformly approximate the function on $[-R,R]$, our method exploits $O(\log{R})$ operations and $O(1)$ memory. This is more efficient than the previous approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses $\Omega(\sqrt{R})$ multiplications and $\Omega(\sqrt{R})$ memory for the evaluation. As another application of DEPs, we also suggest a method to manage the risky outliers from a large interval $[-R,R]$ by using $O(\log{R})$ additional multiplications. As a real-world application, we trained the logistic regression classifier on large public datasets in an encrypted state by using our method. We exploit our method to the evaluation of the logistic function on large intervals, e.g., $[-7683,7683]$.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. IEEE Transactions on Information Forensics and Security
Homomorphic encryption Composite polynomial approximation
Contact author(s)
jhyunp @ snu ac kr
2022-07-02: last of 3 revisions
2022-03-02: received
See all versions
Short URL
Creative Commons Attribution


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