Skip to content

Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys

Authors: Bossuat, Mouchet, Troncoso-Pastoriza, Hubaux
Year: 2021
Venue: EUROCRYPT 2021

type: technique collection: catalogue status: auto

Links: ePrint 2020/1203

Summary

Auto-extracted summary (unreviewed)

The paper presents a bootstrapping procedure for full-RNS CKKS that works with dense (non-sparse) secret keys and is therefore 128-bit secure under recent attacks on sparse R-LWE secrets. It contributes a level-optimal homomorphic polynomial evaluation that accounts for approximate rescaling, an optimized key-switch with a double-hoisting technique for linear transformations, and a systematic parameterization method with an explicit failure-probability estimate. Implemented in Lattigo, bootstrapping a C^32768 plaintext takes 18 s with 19.1 bits of mean precision and failure probability 2^-15.58, a 14.1x throughput gain and 468x lower failure probability than prior work.

Abstract

We present a bootstrapping procedure for the full-RNS variant of the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17, SAC 18). Compared to the previously proposed procedures (Eurocrypt 18 & 19, CT-RSA 20), our bootstrapping procedure is more precise, more efficient (in terms of CPU cost and number of consumed levels), and is more reliable and 128-bit-secure. Unlike the previous approaches, it does not require the use of sparse secret-keys. Therefore, to the best of our knowledge, this is the first procedure that enables a highly efficient and precise bootstrapping with a low probability of failure for parameters that are 128-bit-secure under the most recent attacks on sparse R-LWE secrets. We achieve this efficiency and precision by introducing three novel contributions: (i) We propose a generic algorithm for homomorphic polynomialevaluation that takes into account the approximate rescaling and is optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique for linear transformations (double hoisting). (iii) We propose a systematic approach to parameterize the bootstrapping, including a precise way to assess its failure probability. We implemented our improvements and bootstrapping procedure in the open-source Lattigo library. For example, bootstrapping a plaintext in C32768 takes 18 seconds, has an output coefficient modulus of 505 bits, a mean precision of 19.1 bits, and a failure probability of 2−15.58. Hence, we achieve 14.1× improvement in bootstrapped throughput (plaintextbit per second), with respect to the previous best results, and we have a failure probability 468× smaller and ensure 128-bit security.
Source: pdf

Extracted details

Field Value Source Confidence
contribution generic homomorphic polynomial evaluation algorithm optimal in level consumption under approximate rescaling llm 0.90
contribution optimized key-switch procedure and double-hoisting technique for linear transformations llm 0.90
contribution systematic bootstrapping parameterization including a precise failure-probability estimate llm 0.90
contribution first open-source bootstrapping for full-RNS CKKS with dense keys (in Lattigo) llm 0.90
schemes CKKS llm 0.90
libraries Lattigo llm 0.90
tasks CKKS bootstrapping llm 0.90
hardware Intel i5-6600k 3.5 GHz, 32 GB RAM, single-threaded llm 0.90
security level 128-bit llm 0.90
interaction non-interactive FHE llm 0.90
code url https://github.com/ldsec/lattigo (URL found in the full text) regex 0.50
code url https://github.com/snucrypto/HEAAN (URL found in the full text) regex 0.50
code url https://github.com/Microsoft/SEAL (URL found in the full text) regex 0.50
code url https://github.com/ldsec/lattigo llm 0.90
limitations comparison with prior works relies on their reported numbers because their implementations were not publicly released llm 0.90
llm relevance low llm 0.90
key result bootstrapping latency: 18 s (plaintext in C^32768, single-threaded) llm 0.90
key result output coefficient modulus: 505 bits (C^32768 bootstrapping) llm 0.90
key result mean output precision: 19.1 bits (C^32768 bootstrapping) llm 0.90
key result failure probability: 2^-15.58 (468x smaller than prior best) (C^32768 bootstrapping) llm 0.90
key result bootstrapping throughput improvement: 14.1x (plaintext-bits per second vs previous best results) llm 0.90

System card: Non-sparse-key bootstrapping (Bossuat et al.)

Group 3. CKKS bootstrapping and operation advances
Family CKKS bootstrapping
Arithmetic -
Interaction -
Model scale -
Status Widely used
Relation to the SoK Secure, precise bootstrapping implemented in Lattigo.
Note Removes the sparse-key assumption that weakened security.
Code https://github.com/tuneinsight/lattigo
Systems page Non-sparse-key bootstrapping (Bossuat et al.)

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 55 [p.1], BFV 5 [p.16], BGV 3 [p.13], RSA 3 [p.1]
  • library: Lattigo 8 [p.1], Microsoft SEAL 5 [p.7], HElib 3 [p.31]
  • model: CNN 1 [p.29]
  • technique: Bootstrapping 134 [p.1], Rotations 54 [p.3], RNS 37 [p.1], Rescaling 23 [p.1], NTT 19 [p.2], Chebyshev 12 [p.6], Convolution 4 [p.4], Relinearization 2 [p.5], Polynomial approximation 2 [p.25]
  • assumption: LWE 11 [p.1], RLWE 6 [p.1], 128-bit security 4 [p.1], Lattice-based 3 [p.1]
  • task: Language modeling / generation 9 [p.6]
  • topic: Homomorphic encryption 15 [p.1], Open source 8 [p.1], Benchmark 2 [p.26]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/3-035_efficient-bootstrapping-for-approximate-homomorphic-encrypti.pdf catalogue 46 1.5 MB 3b53cf70c8cd

Database key: efficient-bootstrapping-for-approximate-homomorphic-encryption-with-non · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-bootstrapping-for-approximate-homomorphic-encryption-with-non COLUMN VALUE