Skip to content

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]

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