FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second¶
Authors: Ducas, Micciancio
Year: 2015
Venue: EUROCRYPT 2015
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2014/816
Visual lesson: FHEW (DM) · Scheme table row: FHEW (DM)
Summary¶
Auto-extracted summary (unreviewed)
FHEW introduces a new way to homomorphically evaluate a single binary gate (NAND) and refresh the result, so that a complete bootstrapped boolean operation runs in well under a second on a personal computer instead of the minutes-per-batch required by HElib. The scheme is based on the worst-case hardness of standard lattice problems and is accompanied by a prototype C++ implementation that performs a HomNAND plus Refresh in 0.69 s on a single 3 GHz core.
Abstract¶
The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. Bootstrapping in the latest implementation of FHE, the HElib library of Halevi and Shoup (Crypto 2014), requires about six minutes per batch. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second. We present a detailed technical analysis of the scheme (based on the worst-case hardness of standard lattice problems) and report on the performance of our prototype implementation.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | New homomorphic NAND gate with integrated bootstrapping (refresh) in a fraction of a second | llm | 0.90 |
| contribution | Accumulator-based bootstrapping technique using ring-LWE encryption and MSB extraction | llm | 0.90 |
| contribution | Security analysis based on worst-case hardness of standard lattice problems | llm | 0.90 |
| contribution | Open-source prototype implementation (~600 lines of C++ on top of FFTW) | llm | 0.90 |
| contribution | Extensions to majority, threshold and multi-output gates | llm | 0.90 |
| schemes | FHEW | llm | 0.90 |
| schemes | LWE | llm | 0.90 |
| schemes | Ring-LWE | llm | 0.90 |
| libraries | FFTW | llm | 0.90 |
| libraries | HElib | llm | 0.90 |
| tasks | boolean circuit evaluation | llm | 0.90 |
| tasks | bootstrapping | llm | 0.90 |
| hardware | single 64-bit Intel core at 3 GHz | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/lducas/FHEW (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/lducas/FHEW | llm | 0.90 |
| limitations | Key switching step not yet vectorized, so running time is above the FFT-count prediction | llm | 0.90 |
| limitations | Memory use is about twice the prediction because the bootstrapping key is stored in FFT form | llm | 0.90 |
| limitations | Only simple gates (NAND and small extensions) are supported; complex multi-input gates grow exponentially in cost | llm | 0.90 |
| limitations | Direct benchmarking against HElib is hard because of different security parameters and gate sets | llm | 0.90 |
| limitations | Circular security assumption still required to obtain a non-leveled scheme | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | HomNAND + Refresh latency: 0.69 s (single 64-bit Intel core at 3 GHz (predicted 0.5 s)) | llm | 0.90 |
| key result | memory consumption: 2.2 GB (bootstrapping key stored in FFT form at double precision) | llm | 0.90 |
| key result | comparison to HElib bootstrapping: within one order of magnitude of HElib amortized cost; HElib needs about 6 minutes per batch (different security parameters and gate sets, so not directly comparable) | llm | 0.90 |
| key result | implementation size: about 600 lines of C++ (excluding FFTW) (prototype) | llm | 0.90 |
Scheme card: FHEW (DM)¶
| Group | 3. Bit-wise / lookup-table FHE (GSW, FHEW, TFHE family) |
| Kind | Scheme |
| Hardness assumption | LWE + RGSW |
| Plaintext type | Bits / small integers via LUT |
| SIMD packing | No (amortized variants exist) |
| Bootstrapping | Yes, fast per gate |
| Post-quantum | Yes |
| Status | Widely used |
| Fit for LLM inference | Exact non-linear lookups, but no SIMD, so large matrix products are impractical. |
| Follow-ups | Ring packing and amortized FHEW bootstrapping (2018/532). |
| Libraries | OpenFHE |
| Follow-up papers in the archive | Ring packing and amortized FHEW bootstrapping |
System card: FHEW¶
| Group | 4. Alternative FHE schemes |
| Family | LWE + RGSW blind rotation |
| Arithmetic | Bits / small integers via LUT |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | Fast per-gate bootstrapping with no SIMD. |
| Note | Exact LUT evaluation of arbitrary functions. Available in OpenFHE, including scheme switching with CKKS. |
| Code | https://github.com/openfheorg/openfhe-development |
| Systems page | FHEW |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: GSW 11 [p.9], FHEW 3 [p.1], NTRU 2 [p.2], RSA 2 [p.17]
- library: HElib 6 [p.1]
- technique: Bootstrapping 32 [p.1], Key switching 11 [p.3], Modulus switching 5 [p.5], NTT 3 [p.10]
- assumption: LWE 40 [p.2], Lattice-based 26 [p.1], RLWE 4 [p.11]
- topic: Homomorphic encryption 31 [p.1], Benchmark 4 [p.13], Open source 2 [p.16]
Related papers¶
- Ring packing and amortized FHEW bootstrapping follow up of this paper — follow-up listed for scheme "FHEW (DM)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/4-053_fhew-bootstrapping-homomorphic-encryption-in-less-than-a-sec.pdf |
catalogue | 18 | 450.5 KB | 517f7cce620e |
|
references/schemes/s21-0_fhew-bootstrapping-homomorphic-encryption-in-less-than-a-sec.pdf |
schemes | 18 | 450.5 KB | 517f7cce620e |
byte-identical to references/catalogue/4-053_fhew-bootstrapping-homomorphic-encryption-in-less-than-a-sec.pdf |
Database key: fhew-bootstrapping-homomorphic-encryption-in-less-than-a-second · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fhew-bootstrapping-homomorphic-encryption-in-less-than-a-second COLUMN VALUE