Welcome to the resource topic for 2022/1364
Title:
On Polynomial Functions Modulo p^e and Faster Bootstrapping for Homomorphic Encryption
Authors: Robin Geelen, Ilia Iliashenko, Jiayi Kang, Frederik Vercauteren
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. 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.
ePrint: https://eprint.iacr.org/2022/1364
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .