Paper 2022/1364

On Polynomial Functions Modulo $p^e$ and Faster Bootstrapping for Homomorphic Encryption

Robin Geelen, KU Leuven
Ilia Iliashenko, CipherMode Labs
Jiayi Kang, KU Leuven
Frederik Vercauteren, KU Leuven

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. non-zero 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 state-of-the-art.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
Homomorphic encryptionBootstrappingPolyfunctions
Contact author(s)
robin geelen @ esat kuleuven be
ilia @ ciphermode com
jiayi kang @ esat kuleuven be
frederik vercauteren @ esat kuleuven be
2023-11-18: last of 5 revisions
2022-10-11: received
See all versions
Short URL
Creative Commons Attribution


      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/978-3-031-30620-4_9},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.