Skip to content

Better Bootstrapping for Approximate Homomorphic Encryption

Authors: Han, Ki
Year: 2020
Venue: CT-RSA 2020

type: technique collection: catalogue status: auto

Links: ePrint 2019/688

Summary

Auto-extracted summary (unreviewed)

Generalizes the key-switching of the full-RNS variant of HEAAN (CKKS) to use fewer temporary moduli, so more multiplicative depth is available before bootstrapping at the same security level, and proposes a new polynomial approximation of the sine function tailored to bootstrapping that exploits the plaintext-to-modulus ratio and needs about half the non-scalar multiplications of the Chebyshev method. The authors give the first bootstrapping implementation for full-RNS CKKS, refreshing a C^16384 plaintext in 52 seconds while keeping 11 bits of precision per slot.

Abstract

After Cheon et al. (Asiacrypt’ 17) proposed an approximate homomorphic encryption scheme, HEAAN, for operations between encrypted real (or complex) numbers, the scheme is widely used in a variety of fields with needs on privacy-preserving in data analysis. After that, a bootstrapping method for HEAAN is proposed by Cheon et al. (Eurocrypt’ 18) with modulus reduction being replaced by a sine function. In this paper, we generalize the Full-RNS variant of HEAAN proposed by Cheon et al. (SAC, 19) to reduce the number of temporary moduli used in key-switching. As a result, our scheme can support more depth computations without bootstrapping while ensuring the same level of security. We also propose a new polynomial approximation method to evaluate a sine function in an encrypted state, which is specialized for the bootstrapping for HEAAN. Our method considers a ratio between the size of a plaintext and the size of a ciphertext modulus. Consequently, it requires a smaller number of non-scalar multiplications, which is about half of the Chebyshev method. With our variant of the Full-RNS scheme and a new sine evaluation method, we firstly implement bootstrapping for a Full-RNS variant of approximate homomorphic encryption scheme. Our method enables bootstrapping for a plaintext in the space C16384 to be completed in 52 seconds while preserving 11 bit precision of each slot.
Source: pdf

Extracted details

Field Value Source Confidence
contribution generalized key-switching for full-RNS HEAAN reducing the number of temporary moduli llm 0.85
contribution sine approximation method specialized for bootstrapping that halves non-scalar multiplications vs Chebyshev llm 0.85
contribution first implementation of bootstrapping for a full-RNS variant of approximate HE llm 0.85
schemes CKKS llm 0.85
tasks CKKS bootstrapping llm 0.85
tasks approximate homomorphic arithmetic llm 0.85
security level 128-bit (checked with the LWE estimator) llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/DohyeongKi/better-homomorphic-sine-evaluation (URL found in the full text) regex 0.50
code url https://github.com/DohyeongKi/better-homomorphic-sine-evaluation llm 0.85
limitations sine-based approximation of modulus reduction carries an inevitable approximation error; a different approximation of the modulus function is left as future work llm 0.85
llm relevance low llm 0.85
key result bootstrapping latency: 52 s (plaintext space C^16384, 11-bit precision per slot, full-RNS CKKS) llm 0.85
key result non-scalar multiplications for sine evaluation: about half of the Chebyshev method (bootstrapping sine approximation) llm 0.85

System card: Hybrid key switching

Group 3. CKKS bootstrapping and operation advances
Family Key switching / bootstrapping
Arithmetic -
Interaction -
Model scale -
Status Widely used
Relation to the SoK The key-switching method used in most libraries.
Note Balances key size and noise. Key switching dominates rotation and bootstrapping cost.
Systems page Hybrid key switching

Keyword mentions

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

  • scheme: CKKS 67 [p.1], BFV 2 [p.2]
  • library: Microsoft SEAL 17 [p.2], nGraph-HE 2 [p.2]
  • model: Logistic regression 6 [p.2], CNN 2 [p.2]
  • technique: RNS 78 [p.1], Bootstrapping 60 [p.1], Chebyshev 27 [p.1], Key switching 19 [p.1], NTT 6 [p.13], Polynomial approximation 5 [p.1], Taylor expansion 5 [p.2], Paterson-Stockmeyer 5 [p.18], Rescaling 4 [p.13], Modulus switching 2 [p.5]
  • assumption: LWE 3 [p.12]
  • task: Language modeling / generation 5 [p.7], Medical / healthcare 4 [p.24], Genomics 2 [p.2]
  • topic: Homomorphic encryption 17 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/3-038_better-bootstrapping-for-approximate-homomorphic-encryption.pdf catalogue 26 526.3 KB e26dced60e17

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