Skip to content

Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation

Authors: Bossuat, Troncoso-Pastoriza, Hubaux
Year: 2022
Venue: ACNS 2022

type: scheme collection: schemes status: auto

Links: ePrint 2022/24 · link

Visual lesson: Sparse-secret encapsulation CKKS · Scheme table row: Sparse-secret encapsulation CKKS

Summary

Auto-extracted summary (unreviewed)

Presents a CKKS bootstrapping procedure that encapsulates a dense main secret with a sparse ephemeral secret, so that homomorphic capacity is set by a dense-secret parameterization while bootstrapping cost stays that of a sparse secret with a large security margin. This makes it easy to parameterize the EvalMod step for negligible failure probability; implemented in Lattigo, it bootstraps a C^32768 plaintext in 20.2 s with 32.11 bits of precision, 285 bits of remaining modulus and failure probability 2^-138.7 at 128-bit security.

Abstract

Bootstrapping parameters for the approximate homomorphicencryption scheme of Cheon et al., CKKS (Asiacrypt 17), are usually instantiated using sparse secrets to be efficient. However, using sparse secrets constrains the range of practical parameters within a tight interval, as they must support a large enough depth for the bootstrapping circuit but also be secure with respect to the sparsity of their secret. We present a bootstrapping procedure for the CKKS scheme that combines both dense and sparse secrets. Our construction enables the use of parameters for which the homomorphic capacity is based on a dense secret, yet with a bootstrapping complexity that remains the one of a sparse secret and with a large security margin. Moreover, this also enables us to easily parameterize the bootstrapping circuit so that it has a negligible failure probability that, to the best of our knowledge, has never been achieved for the CKKS scheme. When using the parameters of previous works, our bootstrapping procedures enables a faster procedure with an increased precision and lower failure probability. For example we are able to bootstrap a plaintext of C32768 in 20.2 sec, with 32.11 bits of precision, 285 bits of modulus remaining, a failure probability of 2−138.7 and 128 bit security.
Source: pdf

Extracted details

Field Value Source Confidence
contribution sparse-secret encapsulation combining dense and sparse secrets in CKKS bootstrapping llm 0.90
contribution first CKKS bootstrapping with negligible failure probability llm 0.90
contribution higher precision and smaller EvalMod interpolant at the same parameters as prior work llm 0.90
contribution security analysis of the ephemeral sparse secret llm 0.90
contribution implementation in the Lattigo library llm 0.90
schemes CKKS llm 0.90
libraries Lattigo llm 0.90
tasks FHE bootstrapping llm 0.90
hardware Intel i5-6600K 3.50 GHz, 32 GB RAM, single-threaded (Windows 10) llm 0.90
security level 128-bit (ephemeral secret about 141-168-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/ldsec/lattigo/tree/btp_eprint (URL found in the full text) regex 0.50
code url https://github.com/ldsec/lattigo/tree/btp_eprint llm 0.90
limitations with the Han-Ki interpolation method, K = 16 is the largest range achievable with a depth-5 interpolant llm 0.90
limitations noise from a denser main secret dominates once ciphertext multiplications are involved llm 0.90
llm relevance low llm 0.90
key result bootstrapping latency: 20.2 s (plaintext in C^32768, 128-bit security) llm 0.90
key result bootstrapping precision: 32.11 bits (Set II parameters, K = 16) llm 0.90
key result remaining modulus after bootstrapping: 285 bits (C^32768 plaintext) llm 0.90
key result failure probability: 2^-138.7 (vs 2^-15.58 in Bossuat et al.) (n = 2^15 slots, K = 16, same parameters as prior work) llm 0.90

Scheme card: Sparse-secret encapsulation CKKS

Group 1. CKKS and its variants
Kind Variant
Hardness assumption RLWE
Plaintext type Approximate real/complex
SIMD packing Yes
Bootstrapping Yes, faster with dense secrets
Post-quantum Yes
Status Active
Fit for LLM inference Gets fast bootstrapping without weakening the main secret key.
Libraries Lattigo

Keyword mentions

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

  • scheme: CKKS 36 [p.1]
  • library: Lattigo 2 [p.15]
  • technique: Bootstrapping 138 [p.1], Key switching 9 [p.7], Polynomial approximation 6 [p.3], RNS 6 [p.3], Rescaling 3 [p.2], Rotations 3 [p.6], Minimax approximation 2 [p.3], Taylor expansion 2 [p.13]
  • assumption: LWE 16 [p.1], RLWE 12 [p.1], Lattice-based 2 [p.21], 128-bit security 2 [p.11]
  • topic: Homomorphic encryption 9 [p.21], Open source 3 [p.3]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s04-0_bootstrapping-for-approximate-homomorphic-encryption-with-ne.pdf schemes 22 488.2 KB 37863df80532

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