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]
Related papers¶
- Zephyr: GPU-Efficient Homomorphic Encryption for Privacy-Preserving Transformer Inference follow up of this paper — follow-up listed for scheme "Grafting (decoupled scale and modulus)"
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