A Full RNS Variant of Approximate Homomorphic Encryption¶
Authors: Cheon, Han, Kim, Kim, Song
Year: 2018
Venue: SAC 2018
type: scheme collection: catalogue, schemes status: auto
Links: ePrint 2018/931
Visual lesson: RNS-CKKS · Scheme table row: RNS-CKKS
Summary¶
Auto-extracted summary (unreviewed)
Cheon et al. present a full-RNS variant of the CKKS approximate homomorphic encryption scheme: a new ciphertext-modulus structure lets every RNS component use the NTT, and new approximate modulus-switching procedures avoid RNS composition, so all operations run on 64-bit words instead of multi-precision arithmetic. Compared with the earlier HEAAN implementation at ring dimension 32768, the new library is 17.3x, 6.4x and 8.3x faster for decryption, constant multiplication and homomorphic multiplication. As an application, a single-core run trains a logistic regression model on 575 encrypted samples in 1.8 minutes versus the previous best of 3.5 minutes on four cores.
Abstract¶
The technology of homomorphic encryption has improved rapidly in a few years. The cutting edge implementations are efficient enough to use in practical applications. Recently, Cheon et al. (ASI- ACRYPT’17) proposed a homomorphic encryption scheme which supports an arithmetic of approximate numbers over encryption. This scheme shows the current best performance in computation over the real numbers, but its implementation could not employ core optimization techniques based on the Residue Number System (RNS) decomposition and the Number Theoretic Transformation (NTT). In this paper, we present a variant of approximate homomorphic encryption which is optimal for implementation on standard computer system. We first introduce a new structure of ciphertext modulus which allows us to use both the RNS decomposition of cyclotomic polynomials and the NTT conversion on each of the RNS components. We also suggest new approximate modulus switching procedures without any RNS composition. Compared to previous exact algorithms requiring multi-precision arithmetic, our algorithms can be performed by using only word size (64-bit) operations. Our scheme achieves a significant performance gain from its full RNS implementation. For example, compared to the earlier implementation, our implementation showed speed-ups 17.3, 6.4, and 8.3 times for decryption, constant multiplication, and homomorphic multiplication, respectively, when the dimension of a cyclotomic ring is 32768. We also give experimental result for evaluations of some advanced circuits used in machine learning or statistical analysis. Finally, we demonstrate the practicability of our library by applying to machine learning algorithm. For example, our single core implementation takes 1.8 minutes to build a logistic regression model from encrypted data when the dataset consists of 575 samples, compared to the previous best result 3.5 minutes using four cores.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | full RNS variant of CKKS approximate homomorphic encryption | llm | 0.85 |
| contribution | new ciphertext modulus structure enabling RNS decomposition plus NTT on each RNS component | llm | 0.85 |
| contribution | approximate modulus switching (rescaling) without RNS composition | llm | 0.85 |
| contribution | implementation using only word-size (64-bit) operations | llm | 0.85 |
| contribution | evaluation of ML/statistics circuits and encrypted logistic regression training | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| libraries | HEAAN | llm | 0.85 |
| libraries | FullRNS-HEAAN | llm | 0.85 |
| models | logistic regression | llm | 0.85 |
| tasks | encrypted logistic regression training | llm | 0.85 |
| tasks | statistical analysis over encrypted data | llm | 0.85 |
| tasks | approximate arithmetic over real numbers | llm | 0.85 |
| hardware | 2.9 GHz CPU, single-threaded | llm | 0.85 |
| security level | at least 80-bit | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/HanKyoohyung/FullRNS-HEAAN.We (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/kimandrik/HEAAN.12 (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/HanKyoohyung/FullRNS-HEAAN | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | decryption speed-up: 17.3x (vs earlier HEAAN implementation, ring dimension N = 32768) | llm | 0.85 |
| key result | constant multiplication speed-up: 6.4x (vs earlier HEAAN implementation, N = 32768) | llm | 0.85 |
| key result | homomorphic multiplication speed-up: 8.3x (vs earlier HEAAN implementation, N = 32768) | llm | 0.85 |
| key result | logistic regression training time: 1.8 minutes (575 encrypted samples, single core (previous best 3.5 minutes on four cores)) | llm | 0.85 |
Scheme card: RNS-CKKS¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Approximate real/complex |
| SIMD packing | Yes |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Widely used |
| Fit for LLM inference | The form all libraries and GPU back-ends implement, using word-sized primes. |
| Follow-ups | Hybrid key switching (Han–Ki, CT-RSA 2020). |
| Libraries | OpenFHE, SEAL, Lattigo, Phantom, FIDESlib |
System card: RNS-CKKS (full RNS variant)¶
| Group | 2. CKKS core and variants |
| Family | RLWE, RNS/CRT |
| Arithmetic | Approximate real/complex |
| Interaction | Non-interactive |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | The form of CKKS implemented in every modern library. |
| Note | Removes multi-precision arithmetic by using a chain of word-sized primes. Enables GPU/ASIC acceleration. |
| Systems page | RNS-CKKS (full RNS variant) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 40 [p.2], BFV 5 [p.2], RSA 3 [p.17], Leveled / somewhat HE 3 [p.17], BGV 2 [p.2]
- library: Microsoft SEAL 2 [p.2], HElib 1 [p.2]
- model: Logistic regression 5 [p.15]
- technique: RNS 74 [p.1], Modulus switching 16 [p.1], Rescaling 14 [p.3], NTT 11 [p.1], Sigmoid 5 [p.3], Key switching 4 [p.5], Bootstrapping 3 [p.17], Rotations 2 [p.8], Encrypted training 2 [p.15]
- assumption: RLWE 3 [p.2], LWE 2 [p.6], Lattice-based 2 [p.17]
- task: Genomics 3 [p.16], Language modeling / generation 2 [p.6], Medical / healthcare 2 [p.18], Finance 2 [p.17]
- topic: Homomorphic encryption 41 [p.1], Open source 2 [p.13]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-022_a-full-rns-variant-of-approximate-homomorphic-encryption.pdf |
catalogue | 21 | 360.5 KB | 6aa1e1094f46 |
|
references/schemes/s01-0_a-full-rns-variant-of-approximate-homomorphic-encryption.pdf |
schemes | 21 | 360.5 KB | 6aa1e1094f46 |
byte-identical to references/catalogue/2-022_a-full-rns-variant-of-approximate-homomorphic-encryption.pdf |
Database key: a-full-rns-variant-of-approximate-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set a-full-rns-variant-of-approximate-homomorphic-encryption COLUMN VALUE