Faster bootstrapping with polynomial error¶
Authors: Jacob Alperin-Sheriff; Chris Peikert
Year: 2014
Venue: Lecture Notes in Computer Science
type: technique collection: schemes, sok-references status: auto
Links: DOI · ePrint 2014/94 · link · Semantic Scholar
Summary¶
Auto-extracted summary (unreviewed)
Alperin-Sheriff and Peikert give a bootstrapping algorithm for GSW-style FHE whose runtime and LWE approximation factor are both small polynomials, replacing the boolean-circuit/Barrington's-theorem approach of Brakerski-Vaikuntanathan with a direct arithmetic procedure. For 2^lambda security it needs only a quasi-linear O~(lambda) number of homomorphic operations on GSW ciphertexts, optimal up to polylogarithmic factors for one-bit ciphertexts, and the paper also gives a simpler GSW variant with a tighter error analysis.
Abstract¶
Bootstrapping is a technique, originally due to Gentry (STOC 2009), for “refreshing” ciphertexts of a somewhat homomorphic encryption scheme so that they can support further homomorphic operations. To date, bootstrapping remains the only known way of obtaining fully homomorphic encryption for arbitrary unbounded computations. Over the past few years, several works have dramatically improved the efficiency of bootstrapping and the hardness assumptions needed to implement it. Recently, Brakerski and Vaikuntanathan (ITCS 2014) reached the major milestone of a bootstrapping algorithm based on Learning With Errors for polynomial approximation factors. Their method uses the Gentry-Sahai-Waters (GSW) cryptosystem (CRYPTO 2013) in conjunction with Barrington’s “circuit sequentialization” theorem (STOC 1986). This approach, however, results in very large polynomial runtimes and approximation factors. (The approximation factors can be improved, but at even greater costs in runtime and space.) In this work we give a new bootstrapping algorithm whose runtime and associated approximation factor are both small polynomials. Unlike most previous methods, ours implements an elementary and efficient arithmetic procedure, thereby avoiding the inefficiencies inherent to the use of boolean circuits and Barrington’s Theorem. For 2λ security under conventional lattice assumptions, our method requires only a quasi-linear ˜O(λ) number of homomorphic operations on GSW ciphertexts, which is optimal (up to polylogarithmic factors) for schemes that encrypt just one bit per ciphertext. As a contribution of independent interest, we also give a technically simpler variant of the GSW system and a tighter error analysis for its homomorphic operations. ∗School of Computer Science, College of Computing, Georgia Institute of Technology. Email: jmas6@cc.gatech.edu †School of Computer Science, Georgia Institute of Technology. Email: cpeikert@cc.gatech.edu. This material is based upon work supported by the National Science Foundation under CAREER Award CCF-1054495, by the Alfred P. Sloan Foundation, and by the Defense Advanced Research Projects Agency (DARPA) and the Air Force Research Laboratory (AFRL) under Contract No. FA8750-11-C-0098. The views expressed are those of the authors and do not necessarily reflect the official policy or position of the National Science Foundation, the Sloan Foundation, DARPA or the U.S. Government.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | bootstrapping with polynomial runtime and polynomial LWE approximation factor | llm | 0.85 |
| contribution | arithmetic bootstrapping procedure avoiding boolean circuits and Barrington's theorem | llm | 0.85 |
| contribution | quasi-linear O~(lambda) GSW homomorphic operations for 2^lambda security | llm | 0.85 |
| contribution | technically simpler variant of the GSW cryptosystem with tighter error analysis | llm | 0.85 |
| schemes | GSW | llm | 0.85 |
| schemes | LWE-based FHE | llm | 0.85 |
| tasks | FHE bootstrapping | llm | 0.85 |
| security level | 2^lambda security under LWE with polynomial approximation factors | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | bootstrapping cost: O~(lambda) homomorphic operations on GSW ciphertexts (2^lambda security, polynomial approximation factor) | llm | 0.85 |
SoK reference [61]¶
J. Alperin-Sheriff and C. Peikert, “Faster bootstrapping with polynomial error,” in Advances in Cryptology – CRYPTO 2014, Part I, ser. Lecture Notes in Computer Science, J. A. Garay and R. Gennaro, Eds., vol. 8616. Santa Barbara, CA, USA: Springer Berlin Heidelberg, Germany, Aug. 17–21, 2014, pp. 297–314.
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: GSW 60 [p.1], Leveled / somewhat HE 3 [p.1]
- technique: Bootstrapping 47 [p.1], Rotations 4 [p.4], Polynomial approximation 3 [p.2], Matrix multiplication 3 [p.3], Chebyshev 2 [p.7]
- assumption: LWE 28 [p.2], Lattice-based 21 [p.1], RLWE 2 [p.3], IND-CPA 2 [p.9]
- topic: Homomorphic encryption 20 [p.1]
Related papers¶
- this paper follow up of Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based — follow-up listed for scheme "GSW"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s20-1_eprint-2014-094.pdf |
schemes | 18 | 338.6 KB | cecd346d2e87 |
|
references/sok-references/061_faster-bootstrapping-with-polynomial-error.pdf |
sok-references | 18 | 338.6 KB | cecd346d2e87 |
byte-identical to references/schemes/s20-1_eprint-2014-094.pdf |
Database key: faster-bootstrapping-with-polynomial-error · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set faster-bootstrapping-with-polynomial-error COLUMN VALUE