Cryptology ePrint Archive: Report 2019/677

A Note on Lower Digits Extraction Polynomial for Bootstrapping

Mingjia Huo and Kewen Wu and Qi Ye

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.

Category / Keywords: public-key cryptography / Fully Homomorphic Encryption; Bootstrapping

Date: received 6 Jun 2019

Contact author: mingjia at pku edu cn,shlw_kevin@pku edu cn,yeq18@mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20190611:082019 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]