Skip to content

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]

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