Paper 2019/677 Original: eprint.iacr.org/2019/677 ↗
A Note on Lower Digits Extraction Polynomial for Bootstrapping
Abstract
Bootstrapping is a crucial but computationally expensive step for realizing Fully Homomorphic Encryption (FHE). Recently, Chen and Han (Eurocrypt 2018) introduced a family of low-degree polynomials to extract the lowest digit with respect to a certain congruence, which helps improve the bootstrapping for both FV and BGV schemes. In this note, we present the following relevant findings about the work of Chen and Han (referred to as CH18): 1. We provide a simpler construction of the low-degree polynomials that serve the same purpose and match the asymptotic bound achieved in CH18; 2. We show the optimality and limit of our approach by solving a minimal polynomial degree problem; 3. We consider the problem of extracting other low-order digits using polynomials and provide negative results.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2019-06-11: last updated
- 2019-06-11: published
- Short URL
- https://ia.cr/2019/677
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2019/677,
author = {Mingjia Huo and Kewen Wu and Qi Ye},
title = {A Note on Lower Digits Extraction Polynomial for Bootstrapping},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/677},
year = {2019},
url = {https://eprint.iacr.org/2019/677}
}