Paper 2024/171
Approximate Methods for the Computation of Step Functions in Homomorphic Encryption
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
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
-
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} }