High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function¶
Authors: Joon-Woo Lee; Eunsang Lee; Yongwoo Lee; Young-Sik Kim; Jong-Seon No
Year: 2021
Venue: EUROCRYPT 2021
type: technique collection: catalogue status: auto
Links: DOI · ePrint 2020/552 · Semantic Scholar
Summary¶
Auto-extracted summary (unreviewed)
This paper raises the message precision of RNS-CKKS bootstrapping by improving the homomorphic modular reduction step: an improved multi-interval Remez algorithm computes the optimal minimax polynomial approximation of the modular reduction / scaled cosine function over a union of intervals, and a composite function method using the inverse sine function removes the mismatch between the bootstrapping scaling factor and the default scaling factor. Measured in SEAL, the approximation error drops by 1/1176 to 1/42 (5.4-10.2 bits), raising bootstrapping precision from at most 27.2-30.3 bits to 32.6-40.5 bits, above 32-bit fixed-point precision.
Abstract¶
Approximate homomorphic encryption with the residue number system (RNS), called RNS-variant Cheon-Kim-Kim-Song (RNS-CKKS) scheme [12, 13], is a fully homomorphic encryption scheme that supports arithmetic operations for real or complex number data encrypted. Although the RNS-CKKS scheme is a fully homomorphic encryption scheme, most of the applications with the RNS-CKKS scheme use it as the only leveled homomorphic encryption scheme because of the lack of the practicality of the bootstrapping operation of the RNS-CKKS scheme. One of the crucial problems of the bootstrapping operation is its poor precision. While other basic homomorphic operations ensure sufficiently high precision for practical use, the bootstrapping operation only supports about 20-bit fixed-point precision at best, which is not high precision enough to be used for the reliable large-depth homomorphic computations until now. In this paper, we improve the message precision in the bootstrapping operation of the RNS-CKKS scheme. Since the homomorphic modular reduction process is one of the most important steps in determining the precision of the bootstrapping, we focus on the homomorphic modular reduction process. Firstly, we propose a fast algorithm of obtaining the optimal minimax approximate polynomial of modular reduction function and the scaled sine/cosine function over the union of the approximation regions, called an improved multi-interval Remez algorithm. In fact, this algorithm derives the optimal minimax approximate polynomial of any continuous functions over any union of the finite number of intervals. Next, we propose the composite function method using the inverse sine function to reduce the difference between the scaling factor used in the bootstrapping and the default scaling factor. With these methods, we reduce the approximation error in the bootstrapping of the RNS-CKKS scheme by 1/1176∼1/42 (5.4∼10.2-bit precision improvement) for each parameter setting. While the bootstrapping without the composite func- ⋆This work is supported by Samsung Advanced Institute of Technology. 2 J. Lee et al. tion method has 27.2∼30.3-bit precision at maximum, the bootstrapping with the composite function method has 32.6∼40.5-bit precision.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | improved multi-interval Remez algorithm for optimal minimax polynomial approximation over unions of intervals | llm | 0.85 |
| contribution | composite function method with inverse sine to reduce bootstrapping approximation error | llm | 0.85 |
| contribution | precision analysis of RNS-CKKS bootstrapping measured in the SEAL library | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| schemes | RNS-CKKS | llm | 0.85 |
| libraries | SEAL | llm | 0.85 |
| tasks | CKKS bootstrapping | llm | 0.85 |
| tasks | polynomial approximation of modular reduction | llm | 0.85 |
| security level | 128-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| llm relevance | low | llm | 0.85 |
| key result | bootstrapping message precision: 32.6-40.5 bits (vs 27.2-30.3 bits without composite function method) (RNS-CKKS in SEAL, per parameter set) | llm | 0.85 |
| key result | bootstrapping approximation error reduction: 1/1176 to 1/42 (5.4-10.2 bits precision improvement) (per parameter setting) | llm | 0.85 |
System card: High-precision bootstrapping (minimax + inverse sine)¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | Higher bootstrapping precision. |
| Note | Optimal minimax EvalMod approximations, important for deep LLM circuits. |
| Systems page | High-precision bootstrapping (minimax + inverse sine) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 111 [p.1]
- library: Microsoft SEAL 10 [p.2], PALISADE 3 [p.2], nGraph-HE 2 [p.40]
- model: CNN 4 [p.3]
- dataset: MNIST 3 [p.3]
- hardware: Intel Xeon 1 [p.33]
- technique: Bootstrapping 143 [p.1], RNS 96 [p.1], Remez 92 [p.1], Minimax approximation 83 [p.1], Rescaling 15 [p.6], Chebyshev 10 [p.5], Newton iteration 3 [p.27], Polynomial approximation 2 [p.1], Rotations 2 [p.6], Convolution 2 [p.3]
- assumption: Lattice-based 2 [p.40]
- task: Language modeling / generation 2 [p.8]
- topic: Homomorphic encryption 26 [p.1], Privacy-preserving machine learning 5 [p.3]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-036_high-precision-bootstrapping-of-rns-ckks-homomorphic-encrypt.pdf |
catalogue | 42 | 538.6 KB | ea4bdc2564a8 |
Database key: high-precision-bootstrapping-of-rns-ckks-homomorphic-encryption-using · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set high-precision-bootstrapping-of-rns-ckks-homomorphic-encryption-using COLUMN VALUE