Skip to content

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