Approximate Homomorphic Encryption with Reduced Approximation Error¶
Authors: Kim, Papadimitriou, Polyakov
Year: 2022
Venue: CT-RSA 2022
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2020/1118
Visual lesson: Reduced-error CKKS (exact rescaling) · Scheme table row: Reduced-error CKKS (exact rescaling)
Summary¶
Auto-extracted summary (unreviewed)
Presents a reduced-error variant of CKKS that eliminates the approximation errors caused by LWE noise in encryption and key switching, together with an RNS instantiation that removes the approximate-scaling error of prior RNS CKKS by computing level-specific scaling factors, with rescaling and scaling-factor adjustment performed automatically. Implemented in PALISADE, the reduced-error RNS variant is typically 6 to 9 bits more precise for computations with multiplications under uniform ternary secrets, and up to 12 bits more precise under sparse secrets, than the prior RNS CKKS variant.
Abstract¶
The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is currently the most efficient method to perform approximate homomorphic computations over real and complex numbers. Although the CKKS scheme can already be used to achieve practical performance for many advanced applications, e.g., in machine learning, its broader use in practice is hindered by several major usability issues, most of which are brought about by relatively high approximation errors and the complexity of dealing with them. We present a reduced-error CKKS variant that removes the approximation errors due to the Learning With Errors (LWE) noise in the encryption and key switching operations. We propose and implement its Residue Number System (RNS) instantiation that has a lower error than the original CKKS scheme implementation based on multiprecision integer arithmetic. While formulating the RNS instantiation, we also develop an intermediate RNS variant that has a smaller approximation error than the prior RNS variant of CKKS. The high-level idea of our main RNS-related improvements is to remove the approximate scaling error using a novel procedure that computes level-specific scaling factors. The rescaling operations and scaling factor adjustments in our implementation are done automatically. We implement both RNS variants in PALISADE and compare their approximation error and efficiency to the prior RNS variant. Our results for uniform ternary secret key distribution, which is the most efficient setting included in the community homomorphic encryption security standard, show that the reduced-error CKKS RNS implementation typically has an approximation error that is 6 to 9 bits smaller for computations with multiplications than the prior RNS variant. The results for the sparse secret setting, which was used for the original CKKS scheme, imply that our reduced-error CKKS RNS implementation has an approximation error up to 12 bits smaller than the prior RNS variant. ∗Corresponding author; e-mail: ypolyakov@dualitytech.com 1 Contents
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | reduced-error CKKS variant removing LWE approximation errors from encryption and key switching | llm | 0.85 |
| contribution | RNS CKKS variant with level-specific scaling factors eliminating the approximate rescaling error | llm | 0.85 |
| contribution | automatic rescaling and scaling-factor adjustment in the implementation | llm | 0.85 |
| contribution | PALISADE implementation and error/efficiency comparison against prior RNS CKKS | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| libraries | PALISADE | llm | 0.85 |
| tasks | approximate real/complex homomorphic arithmetic | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/KyoohyungHan/FullRNS-HEAAN (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/homenc/HElib (URL found in the full text) | regex | 0.50 |
| llm relevance | low | llm | 0.85 |
| key result | approximation error reduction: 6 to 9 bits smaller than prior RNS CKKS (computations with multiplications, uniform ternary secret key) | llm | 0.85 |
| key result | approximation error reduction: up to 12 bits smaller than prior RNS CKKS (sparse secret key setting) | llm | 0.85 |
Scheme card: Reduced-error CKKS (exact rescaling)¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Approximate real/complex, higher precision |
| SIMD packing | Yes |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Widely used |
| Fit for LLM inference | Several extra bits of precision at the same parameters. This is the OpenFHE default. |
| Libraries | OpenFHE |
System card: Reduced-error CKKS (FLEXIBLEAUTO)¶
| Group | 2. CKKS core and variants |
| Family | RNS-CKKS with exact rescaling |
| Arithmetic | Approximate real/complex, higher precision |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Widely used |
| Relation to the SoK | Default precision-management mode in OpenFHE. |
| Note | Removes rescaling error from prime approximation. Gains several bits of precision at the same parameters. |
| Code | https://github.com/openfheorg/openfhe-development |
| Systems page | Reduced-error CKKS (FLEXIBLEAUTO) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 238 [p.1], RSA 3 [p.30], BFV 2 [p.29], Leveled / somewhat HE 2 [p.4]
- library: PALISADE 15 [p.1], Microsoft SEAL 4 [p.7], HElib 4 [p.7]
- model: Logistic regression 3 [p.29]
- technique: RNS 123 [p.1], Rescaling 117 [p.1], Key switching 38 [p.1], Bootstrapping 11 [p.7], Modulus switching 5 [p.4], Polynomial approximation 2 [p.28], Minimax approximation 2 [p.7], Rotations 2 [p.14], NTT 2 [p.10]
- assumption: LWE 29 [p.1], RLWE 4 [p.3], Lattice-based 2 [p.13]
- task: Language modeling / generation 6 [p.4], Genomics 6 [p.3], Medical / healthcare 3 [p.30]
- topic: Homomorphic encryption 30 [p.1], Benchmark 4 [p.5], Open source 3 [p.30]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-024_approximate-homomorphic-encryption-with-reduced-approximatio.pdf |
catalogue | 34 | 580.7 KB | 548be161a5fe |
|
references/schemes/s03-0_approximate-homomorphic-encryption-with-reduced-approximatio.pdf |
schemes | 34 | 580.7 KB | 548be161a5fe |
byte-identical to references/catalogue/2-024_approximate-homomorphic-encryption-with-reduced-approximatio.pdf |
Database key: approximate-homomorphic-encryption-with-reduced-approximation-error · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set approximate-homomorphic-encryption-with-reduced-approximation-error COLUMN VALUE