Paper 2022/280
Efficient Homomorphic Evaluation on Large Intervals
Abstract
Homomorphic encryption (HE) is being widely used for privacypreserving computation. Since HE schemes only support polynomial operations, it is prevalent to use polynomial approximations of nonpolynomial 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 realworld 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 domainextension 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 PatersonStockmeyer 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 realworld 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]$.
Note: DOI: 10.1109/TIFS.2022.3188145
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. IEEE Transactions on Information Forensics and Security
 Keywords
 Homomorphic encryption Composite polynomial approximation
 Contact author(s)
 jhyunp @ snu ac kr
 History
 20220718: last of 5 revisions
 20220302: received
 See all versions
 Short URL
 https://ia.cr/2022/280
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/280, 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{https://eprint.iacr.org/2022/280}}, url = {https://eprint.iacr.org/2022/280} }