Skip to content

Grafting: Decoupled Scale Factors and Modulus in RNS-CKKS

Authors: Jung Hee Cheon; Hyeongmin Choe; Minsik Kang; Jaehyung Kim; Seonghak Kim; Johannes Mono; Taeyeong Noh
Year: 2024
Venue: IACR ePrint 2024/1014

type: technique collection: catalogue, schemes status: auto

Links: DOI · ePrint 2024/1014

Visual lesson: Grafting (decoupled scale and modulus) · Scheme table row: Grafting (decoupled scale and modulus)

Summary

Auto-extracted summary (unreviewed)

Grafting decouples the CKKS scale factor from the ciphertext modulus by introducing reusable (universal) 'sprout' modulus factors, allowing word-sized RNS packing, rescaling by arbitrary bit-lengths and key switching at any modulus bit-length without extra switching keys. A C++ RNS-CKKS implementation shows up to 1.83x faster key switching, 2.01x faster multiplication and 1.92x faster bootstrapping for ring dimensions 2^14-2^16, with public-key and ciphertext sizes reduced by up to 62%; applications include a 1.89x speed-up of Bit-CKKS gate bootstrapping and up to 27% (204-bit) less modulus consumption for homomorphic comparison without precision loss.

Abstract

The CKKS Fully Homomorphic Encryption (FHE) scheme enables approximate arithmetic on encrypted complex numbers for a desired precision. Most implementations use RNS with carefully chosen parameters to balance precision, efficiency, and security. However, a key limitation in RNS-CKKS is the rigid coupling between the scale factor, which determines numerical precision, and the modulus, which ensures security. Since these parameters serve distinct roles—one governing arithmetic correctness and the other defining cryptographic structure—this dependency imposes design constraints, such as a lack of suitable NTT primes and limited precision flexibility, ultimately leading to inefficiencies. We propose Grafting, a novel approach to decouple scale factors from the modulus by introducing (universal) sprouts, reusable modulus factors that optimize word-sized packing while allowing flexible rescaling. The universal sprouts allow rescaling by arbitrary bit-lengths and key-switching at any modulus bit-length without requiring additional key-switching keys, and thus enable universal use of the underlying parameters. Decoupling the scale factor from the modulus in Grafting yields significant efficiency gains: (1) Optimized RNS packing by decomposing the modulus into machine word-sized components, accelerating computations and reducing the ciphertext and encryption/evaluation key sizes; and (2) A freely adjustable scale factor independent of the modulus, unifying the ring structure across applications and reducing modulus consumption through adaptive scalings. Our experiments demonstrate that Grafting improves performance across standard SHE/FHE parameter sets for ring dimensions 214-216 by up to 1.83× and 2.01× for key-switchings and multiplications, respectively, and up to 1.92× for bootstrapping. Grafting also reduces public key and ciphertext sizes by up to 62% without compression, maintaining the same number of public keys as before. As an application, we showcase the CKKS gate bootstrapping for bits (Bae et al; Eurocrypt’24), achieving 1.89× speed-up due to the reduced number of RNS factors. Finally, we revisit the homomorphic comparison (Cheon et al; Asiacrypt’20), evaluating it with carefully chosen scale factors for each iteration, reporting up to 204-bit fewer modulus consumption (27% reduction) in the standard parameter set, without precision loss.
Source: pdf

Extracted details

Field Value Source Confidence
contribution Grafting: decoupling scale factors from the modulus in RNS-CKKS via (universal) sprouts llm 0.85
contribution word-sized RNS packing that accelerates computation and shrinks keys and ciphertexts llm 0.85
contribution freely adjustable scale factors enabling adaptive scaling and lower modulus consumption llm 0.85
contribution C++ implementation and evaluation on standard SHE/FHE parameter sets llm 0.85
contribution applications to Bit-CKKS gate bootstrapping, homomorphic comparison, Tuple-CKKS and arbitrary-precision arithmetic llm 0.85
schemes CKKS llm 0.85
schemes RNS-CKKS llm 0.85
schemes Bit-CKKS llm 0.85
libraries custom C++ RNS-CKKS implementation llm 0.85
libraries OpenFHE (parameter sets revisited) llm 0.85
tasks CKKS bootstrapping llm 0.85
tasks homomorphic comparison llm 0.85
tasks arbitrary-precision homomorphic arithmetic llm 0.85
security level lambda >= 128 llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/homenc/HElib (URL found in the full text) regex 0.50
code url https://github.com/tuneinsight/lattigo (URL found in the full text) regex 0.50
code url https://github.com/Microsoft/SEAL (URL found in the full text) regex 0.50
llm relevance low llm 0.85
key result key-switching speed-up: up to 1.83x (standard SHE/FHE parameter sets, N = 2^14-2^16) llm 0.85
key result multiplication speed-up: up to 2.01x (standard SHE/FHE parameter sets, N = 2^14-2^16) llm 0.85
key result bootstrapping speed-up: up to 1.92x (standard FHE parameter sets) llm 0.85
key result public key and ciphertext size reduction: up to 62% (without compression, same number of public keys) llm 0.85
key result Bit-CKKS gate bootstrapping speed-up: 1.89x (N=2^14), 1.81x (N=2^15) (Bae et al. Eurocrypt'24 parameters, grafted) llm 0.85
key result modulus consumption for homomorphic comparison: up to 204 bits fewer (27% reduction), 1.5x fewer bootstraps (standard parameter set, no precision loss) llm 0.85

Scheme card: Grafting (decoupled scale and modulus)

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 Active SOTA
Fit for LLM inference Allows word-sized primes with arbitrary scales, which suits 32/64-bit GPU arithmetic.
Follow-ups Used by Zephyr (2026/932) for 32-bit GPU CKKS.
Follow-up papers in the archive Zephyr: GPU-Efficient Homomorphic Encryption for Privacy-Preserving Transformer Inference

System card: Grafting (CKKS modulus engineering)

Group 3. CKKS bootstrapping and operation advances
Family CKKS parameterization
Arithmetic -
Interaction -
Model scale -
Status Active SOTA
Relation to the SoK Decouples scale factors from RNS primes.
Note Uses word-sized primes with arbitrary scale. Reduces wasted modulus and speeds GPU implementations.
Systems page Grafting (CKKS modulus engineering)

Keyword mentions

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

  • scheme: CKKS 102 [p.1], Leveled / somewhat HE 17 [p.1], BGV 6 [p.2], BFV 2 [p.4], RSA 2 [p.15]
  • library: OpenFHE 8 [p.11], HEaaN (library) 6 [p.11], Lattigo 5 [p.11], HElib 3 [p.15], Microsoft SEAL 2 [p.16]
  • model: CNN 1 [p.15]
  • hardware: ARM 1 [p.15], GPU 1 [p.2]
  • technique: RNS 127 [p.1], Rescaling 96 [p.1], NTT 80 [p.1], Bootstrapping 59 [p.1], Key switching 52 [p.1], Relinearization 21 [p.2], Modulus switching 12 [p.2], Chebyshev 6 [p.19], Matrix multiplication 4 [p.15], Rotations 3 [p.2], Convolution 2 [p.15], Fine-tuning 2 [p.2]
  • assumption: RLWE 5 [p.1], Lattice-based 2 [p.6]
  • task: Language modeling / generation 2 [p.18]
  • topic: Homomorphic encryption 56 [p.1], Open source 4 [p.15]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/3-041_grafting-decoupled-scale-factors-and-modulus-in-rns-ckks.pdf catalogue 20 811.4 KB 2797907f049e
references/schemes/s07-0_grafting-decoupled-scale-factors-and-modulus-in-rns-ckks.pdf schemes 20 811.4 KB 2797907f049e byte-identical to references/catalogue/3-041_grafting-decoupled-scale-factors-and-modulus-in-rns-ckks.pdf

Database key: grafting-decoupled-scale-factors-and-modulus-in-rns-ckks · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set grafting-decoupled-scale-factors-and-modulus-in-rns-ckks COLUMN VALUE