2019/06/07 by Mingjia Huo, Kewen Wu, Huo, Mingjia +3
Computer Science · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1906.02867
openalex publication_date 2019/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.