A Note on Lower Digits Extraction Polynomial for Bootstrapping

Mingjia Huo, Kewen Wu, Qi YearXiv 2019 · arXiv

Introduction

Fully Homomorphic Encryption (FHE) is often described as the "holy grail" of cryptography, enabling computation on encrypted data without requiring decryption. This capability is essential for privacy-preserving cloud computing and secure data analysis. However, FHE schemes—such as BGV and FV—suffer from the accumulation of "noise" during mathematical operations. If this noise exceeds a specific threshold, the ciphertext becomes undecipherable.

To manage this, researchers employ a process called bootstrapping, which refreshes the ciphertext and resets the noise level. Bootstrapping is the primary computational bottleneck in FHE, and its most intensive component is digit extraction. This paper provides a simplified, more intuitive mathematical framework for constructing the polynomials used in digit extraction, establishes theoretical limits on their efficiency, and proves the impossibility of certain multi-digit optimizations.

The Digit Extraction Problem

In the context of FHE bootstrapping, digit extraction involves isolating the lowest digit of an encrypted integer modulo a prime power $p^e$. Efficiently performing this operation requires finding a polynomial of the lowest possible degree that maps integers to their corresponding least significant digits.

Previous state-of-the-art work, specifically by Chen and Han (CH18), introduced efficient polynomials for this task. However, their constructions were mathematically dense and lacked an intuitive derivation. This research seeks to bridge that gap by providing a "natural" construction that achieves the same asymptotic efficiency while clarifying the underlying number theory.

Methodology: The Zero-Polynomial Approach

The authors' primary contribution to the construction of extraction polynomials is the utilization of a "Zero-Polynomial" identity. They identify a simple polynomial that evaluates to zero for any integer input modulo $p^e$:

$$f(x) = (x(x^{p-1} - 1))^e \equiv 0 \pmod{p^e}$$

By leveraging this identity, the authors simplify the extraction process through the following steps:

  1. Reduction: They take a known, high-degree extraction polynomial from earlier literature (such as HS15) and reduce it modulo their "Zero-Polynomial."
  2. Degree Optimization: This reduction produces a new polynomial, denoted as $L_e$, which possesses a significantly lower degree of $(ep - 1)$.
  3. $p$-adic Analysis: To verify the optimality of this construction, the authors employ $p$-adic analysis—specifically the $ord_p$ function—to demonstrate that the degree of $L_e$ is near the theoretical minimum required for such a mapping.

Key Insights and Theoretical Bounds

Simplicity and Efficiency

The research demonstrates that the complex constructions previously thought necessary to reach optimal bounds are not required. The intuitive approach based on basic modular arithmetic identities yields the same performance as the CH18 method, making the implementation of FHE bootstrapping more accessible for developers and researchers.

The Degree Floor

The paper establishes a fundamental limit on polynomial-based digit extraction. The authors prove that any polynomial that vanishes on all integers modulo $p^e$ must have a degree of at least $ord_p^{-1}(e)$, which is approximately $e(p-1)$. This result provides a clear target for the field: once a polynomial reaches this degree, further optimizations in terms of degree reduction are mathematically impossible.

The "No-Go" Theorem for Higher Digits

A significant portion of the paper is dedicated to exploring whether a single polynomial can extract higher-order digits (e.g., the second or third digit) directly while ignoring the lower digits. Using a proof by contradiction, the authors provide a definitive negative result (Lemma 5). They prove that for any $r > 1$, no such polynomial exists. This implies that digit extraction must remain a sequential or multi-step process, ruling out a specific class of potential shortcuts in the bootstrapping pipeline.

Results and Implications

  • Lemma 3: This lemma provides the concrete construction for the degree-$(ep-1)$ polynomial. It maintains the efficiency required for modern FHE schemes while being significantly easier to derive and implement than previous iterations.
  • Near-Optimality: The gap between the authors' construction and the theoretical lower bound is shown to be marginal, confirming that current methods are operating near the peak of mathematical possibility.
  • Structural Constraints: By proving the impossibility of direct higher-digit extraction, the paper saves future researchers from pursuing a mathematically non-viable path, instead focusing efforts on improving the sequential efficiency of the extraction process.

Conclusion

This work serves as a theoretical refinement of the FHE bootstrapping process. While it does not offer a massive empirical speedup over the CH18 method, it provides the mathematical proof that CH18 was already near the theoretical limit. By simplifying the construction of extraction polynomials and defining the "no-go" zones for higher-digit extraction, this paper clarifies the algebraic landscape of bootstrapping and sets the stage for future non-polynomial or multi-step algebraic explorations.

Summary updated

BibTeX
@misc{huo2019note,
  author = {Mingjia Huo and Kewen Wu and Qi Ye},
  title = {{A Note on Lower Digits Extraction Polynomial for Bootstrapping}},
  year = {2019},
  eprint = {1906.02867},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.02867},
}
Figure