Ring packing and amortized FHEW bootstrapping¶
Year: 2018
type: technique collection: schemes status: auto
Links: ePrint 2018/532
Summary¶
Auto-extracted summary (unreviewed)
Micciancio and Sorrell address the main throughput bottleneck of FHEW, whose refreshing (bootstrapping) procedure must run after every NAND gate on a single encrypted bit. They give a new ring-packing-based refreshing procedure that refreshes n FHEW ciphertexts simultaneously at a cost comparable to one single-bit refresh, so the bootstrapping cost is amortized over n bits and the throughput of homomorphic boolean-circuit evaluation improves by roughly a factor n.
Abstract¶
The FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) offers very fast homomorphic NAND-gate computations (on encrypted data) and a relatively fast refreshing procedure that allows to homomorphically evaluate arbitrary NAND boolean circuits. Unfortunately, the refreshing procedure needs to be executed after every single NAND computation, and each refreshing operates on a single encrypted bit, greatly decreasing the overall throughput of the scheme. We give a new refreshing procedure that simultaneously refreshes n FHEW ciphertexts, at a cost comparable to a single-bit FHEW refreshing operation. As a result, the cost of each refreshing is amortized over n encrypted bits, improving the throughput for the homomorphic evaluation of boolean circuits roughly by a factor n.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Amortized FHEW bootstrapping: refresh n ciphertexts at the cost of about one single-bit refresh | llm | 0.60 |
| contribution | Ring-packing technique to batch LWE ciphertexts for simultaneous refreshing | llm | 0.60 |
| contribution | Roughly factor-n throughput improvement for homomorphic evaluation of boolean circuits | llm | 0.60 |
| schemes | FHEW | llm | 0.60 |
| tasks | homomorphic evaluation of boolean (NAND) circuits | llm | 0.60 |
| interaction | non-interactive FHE | llm | 0.60 |
| llm relevance | low | llm | 0.60 |
| key result | throughput improvement: roughly factor n (amortized refreshing of n FHEW ciphertexts at cost comparable to one single-bit refresh) | llm | 0.60 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: FHEW 35 [p.1], GSW 25 [p.4]
- library: HElib 3 [p.2]
- technique: Bootstrapping 45 [p.1], Modulus switching 9 [p.5], Key switching 6 [p.4], Polynomial approximation 6 [p.1], Rotations 3 [p.6], SIMD packing 2 [p.10], Convolution 2 [p.6]
- assumption: LWE 57 [p.2], RLWE 44 [p.2], Lattice-based 11 [p.1]
- topic: Homomorphic encryption 22 [p.1]
Related papers¶
- this paper follow up of FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second — follow-up listed for scheme "FHEW (DM)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s21-1_eprint-2018-532.pdf |
schemes | 25 | 381.9 KB | 4373bdf6f9a6 |
Database key: ring-packing-and-amortized-fhew-bootstrapping · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set ring-packing-and-amortized-fhew-bootstrapping COLUMN VALUE