Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption¶
Authors: Yongwoo Lee; Daniele Micciancio; Andrey Kim; Rakyong Choi; Maxim Deryabin; Jieun Eom; Donghoon Yoo
Year: 2023
Venue: EUROCRYPT 2023
type: scheme collection: schemes status: auto
Links: DOI · ePrint 2022/198 · Semantic Scholar
Visual lesson: FHEW with small keys (LMKCDEY) · Scheme table row: FHEW with small keys (LMKCDEY)
Summary¶
Auto-extracted summary (unreviewed)
Proposes a new automorphism-based blind-rotation (bootstrapping) procedure for FHEW/TFHE-like schemes that supports arbitrary secret-key distributions at no extra runtime cost while keeping evaluation keys small, with lower noise growth than both the AP and GINX methods. At a 128-bit security level the evaluation key of the best previous scheme shrinks by more than 30% with slightly lower runtime, and a prototype in PALISADE/OpenFHE shows the best runtime and key size among known FHEW bootstrapping methods; the paper also sketches a threshold HE construction based on FHEW.
Abstract¶
There are two competing approaches to bootstrap the FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) and its variants: the original AP/FHEW method, which supports arbitrary secret key distributions, and the improved GINX/TFHE method, which uses much smaller evaluation keys, but is directly applicable only to binary secret keys, restricting the scheme’s applicability. In this paper, we present a new bootstrapping procedure for FHEW-like encryption schemes that achieves the best features of both methods: support for arbitrary secret key distributions at no additional runtime costs, while using small evaluation keys. (Support for arbitrary secret keys is critical in a number of important applications, like threshold and some multi-key homomorphic encryption schemes.) As an added benefit, our new bootstrapping procedure results in smaller noise growth than both AP and GINX, regardless of the key distribution. Our improvements are both theoretically significant (offering asymptotic savings, up to a O(log n) multiplicative factor, either on the running time or public evaluation key size), and practically relevant. For example, for a concrete 128-bit target security level, we show how to decrease the evaluation key size of the best previously known scheme by more than 30%, while also slightly reducing the running time. We demonstrate the practicality of the proposed methods by building a prototype implementation within the PALISADE/OpenFHE open-source homomorphic encryption library. We provide optimized parameter sets and implementation results showing that the proposed algorithm has the best performance among all known FHEW bootstrapping methods in terms of runtime and key size. We illustrate the benefits of our method by sketching a simple construction of threshold homomorphic encryption based on FHEW.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | New blind rotation algorithm for FHEW-like schemes combining AP-style key-distribution generality with GINX-style small keys | llm | 0.80 |
| contribution | Smaller noise growth than AP and GINX regardless of key distribution | llm | 0.80 |
| contribution | Asymptotic savings up to O(log n) in runtime or evaluation-key size | llm | 0.80 |
| contribution | Optimized 128-bit parameter sets and prototype in PALISADE/OpenFHE | llm | 0.80 |
| contribution | Sketch of threshold homomorphic encryption from FHEW with distributed evaluation-key generation | llm | 0.80 |
| schemes | FHEW | llm | 0.80 |
| schemes | TFHE | llm | 0.80 |
| schemes | threshold HE | llm | 0.80 |
| schemes | multi-key HE | llm | 0.80 |
| libraries | OpenFHE | llm | 0.80 |
| libraries | PALISADE | llm | 0.80 |
| tasks | FHEW bootstrapping | llm | 0.80 |
| tasks | threshold homomorphic encryption | llm | 0.80 |
| security level | 128-bit | llm | 0.80 |
| interaction | non-interactive FHE | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
| key result | evaluation key size reduction: >30% (vs best previously known FHEW bootstrapping scheme, 128-bit security) | llm | 0.80 |
| key result | runtime: slightly reduced vs best prior method (single-user gate bootstrapping, 128-bit security) | llm | 0.80 |
| key result | asymptotic saving: up to O(log n) factor (runtime or public evaluation key size) | llm | 0.80 |
Scheme card: FHEW with small keys (LMKCDEY)¶
| Group | 3. Bit-wise / lookup-table FHE (GSW, FHEW, TFHE family) |
| Kind | Scheme |
| Hardness assumption | RLWE (automorphism-based blind rotation) |
| Plaintext type | Bits / small integers |
| SIMD packing | No |
| Bootstrapping | Yes, small keys |
| Post-quantum | Yes |
| Status | Active |
| Fit for LLM inference | Small keys and good threshold support. In OpenFHE. |
| Follow-ups | LFHE: bootstrapping keys under 1 MB (2023/767); large-plaintext FBS with small keys (2025/1717). |
| Libraries | OpenFHE |
| Follow-up papers in the archive | LFHE: Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: FHEW 54 [p.1], TFHE 17 [p.1], Threshold HE 17 [p.1], Multi-key HE 10 [p.1], BGV 5 [p.4], MPC 4 [p.7], CKKS 3 [p.8], Secret sharing 3 [p.3], BFV 2 [p.9], NTRU 2 [p.25], Paillier 2 [p.27]
- library: PALISADE 4 [p.1], OpenFHE 2 [p.1], HElib 2 [p.6]
- hardware: Intel Xeon 1 [p.21]
- technique: Rotations 99 [p.1], Bootstrapping 67 [p.1], Key switching 13 [p.6], Modulus switching 5 [p.17], NTT 5 [p.10]
- assumption: RLWE 73 [p.5], LWE 44 [p.3], Lattice-based 18 [p.2]
- topic: Homomorphic encryption 55 [p.1], Open source 3 [p.1]
Related papers¶
- LFHE: Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte follow up of this paper — follow-up listed for scheme "FHEW with small keys (LMKCDEY)"
- Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys follow up of this paper — follow-up listed for scheme "FHEW with small keys (LMKCDEY)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s23-0_efficient-fhew-bootstrapping-with-small-evaluation-keys-and.pdf |
schemes | 28 | 589.3 KB | 218f6c719ae3 |
Database key: efficient-fhew-bootstrapping-with-small-evaluation-keys-and · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-fhew-bootstrapping-with-small-evaluation-keys-and COLUMN VALUE