CryptoDB
Ju-Sung Kang
ORCID: 0000-0002-1093-7978
Publications
Year
Venue
Title
2023
EUROCRYPT
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. 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.
Coauthors
- Jung Hee Cheon (1)
- Robin Geelen (1)
- Jae Woo Han (1)
- Dowon Hong (2)
- Seokhie Hong (1)
- Ilia Iliashenko (1)
- Ju-Sung Kang (5)
- Youngdai Ko (1)
- Ki Hyoung Ko (1)
- Wonil Lee (1)
- Sangjin Lee (2)
- Choonsik Park (1)
- Bart Preneel (1)
- Heuisu Ryu (1)
- Sang Uk Shin (1)
- Frederik Vercauteren (1)
- Okyeon Yi (1)