Paper 2024/171

Approximate Methods for the Computation of Step Functions in Homomorphic Encryption

Tairong Huang, Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
Shihe Ma, Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China
Anyu Wang, Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China, Zhongguancun Laboratory, Beijing, China, National Financial Cryptography Research Center, Beijing, China
XiaoYun Wang, Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China, Zhongguancun Laboratory, Beijing, China, National Financial Cryptography Research Center, Beijing, China, Shandong Institute of Blockchain, Jinan, China, Key Laboratory of Cryptologic Technology and Information Security (Ministry of Education), School of Cyber Science and Technology, Shandong University, China
Abstract

The computation of step functions over encrypted data is an essential issue in homomorphic encryption due to its fundamental application in privacy-preserving computing. However, an effective method for homomorphically computing general step functions remains elusive in cryptography. This paper proposes two polynomial approximation methods for general step functions to tackle this problem. The first method leverages the fact that any step function can be expressed as a linear combination of shifted sign functions. This connection enables the homomorphic evaluation of any step function using known polynomial approximations of the sign function. The second method boosts computational efficiency by employing a composite polynomial approximation strategy. We present a systematic approach to construct a composite polynomial $f_k \circ f_{k-1} \circ \cdots \circ f_1$ that increasingly approximates the step function as $k$ increases. This method utilizes an adaptive linear programming approach that we developed to optimize the approximation effect of $f_i$ while maintaining the degree and coefficients bounded. We demonstrate the effectiveness of these two methods by applying them to typical step functions such as the round function and encrypted data bucketing, implemented in the HEAAN homomorphic encryption library. Experimental results validate that our methods can effectively address the homomorphic computation of step functions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. ACISP 2024
Keywords
Step functionHomomorphic encryptionCKKSPolynomial approximationRound functionEncrypted data bucketing
Contact author(s)
htr19 @ mails tsinghua edu cn
msh21 @ mails tsinghua edu cn
anyuwang @ tsinghua edu cn
xiaoyunwang @ tsinghua edu cn
History
2024-02-06: approved
2024-02-05: received
See all versions
Short URL
https://ia.cr/2024/171
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/171,
      author = {Tairong Huang and Shihe Ma and Anyu Wang and XiaoYun Wang},
      title = {Approximate Methods for the Computation of Step Functions in Homomorphic Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/171},
      year = {2024},
      url = {https://eprint.iacr.org/2024/171}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.