Skip to content

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]

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