Paper 2022/1364
On Polynomial Functions Modulo $p^e$ and Faster Bootstrapping for Homomorphic Encryption
Abstract
In this paper, we perform a systematic study of functions $f: \mathbb{Z}_{p^e} \to \mathbb{Z}_{p^e}$ and categorize those functions that can be represented by a polynomial with integer coefficients. More specifically, we cover the following properties: necessary and sufficient conditions for the existence of an integer polynomial representation; computation of such a representation; and the complete set of equivalent polynomials that represent a given function. As an application, we use the newly developed theory to speed up bootstrapping for the BGV and BFV homomorphic encryption schemes. The crucial ingredient underlying our improvements is the existence of null polynomials, i.e. nonzero polynomials that evaluate to zero in every point. We exploit the rich algebraic structure of these null polynomials to find better representations of the digit extraction function, which is the main bottleneck in bootstrapping. As such, we obtain sparse polynomials that have 50% fewer coefficients than the original ones. In addition, we propose a new method to decompose digit extraction as a series of polynomial evaluations. This lowers the time complexity from $\mathcal{O}(\sqrt{pe})$ to $\mathcal{O}(\sqrt{p}\sqrt[^4]{e})$ for digit extraction modulo $p^e$, at the cost of a slight increase in multiplicative depth. Overall, our implementation in HElib shows a significant speedup of a factor up to 2.6 over the stateoftheart.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2023
 DOI
 10.1007/9783031306204_9
 Keywords
 Homomorphic encryptionBootstrappingPolyfunctions
 Contact author(s)

robin geelen @ esat kuleuven be
ilia @ ciphermode com
jiayi kang @ esat kuleuven be
frederik vercauteren @ esat kuleuven be  History
 20231118: last of 5 revisions
 20221011: received
 See all versions
 Short URL
 https://ia.cr/2022/1364
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1364, author = {Robin Geelen and Ilia Iliashenko and Jiayi Kang and Frederik Vercauteren}, title = {On Polynomial Functions Modulo $p^e$ and Faster Bootstrapping for Homomorphic Encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1364}, year = {2022}, doi = {10.1007/9783031306204_9}, url = {https://eprint.iacr.org/2022/1364} }