Introduction
The CKKS (Cheon-Kim-Kim-Song) scheme has emerged as the standard for approximate homomorphic encryption (HE), enabling complex computations on encrypted data. To achieve practical performance, modern implementations rely on the Residue Number System (RNS), which decomposes large cryptographic moduli into smaller, machine-word-sized prime factors. However, standard RNS-CKKS suffers from a rigid coupling: the size of these RNS factors must match the desired numerical precision (the scale factor).
This coupling is inherently inefficient on 64-bit architectures. For instance, if an application requires only 30 bits of precision, the RNS factors are typically constrained to 30 bits. This wastes half of the 64-bit word's capacity, doubling the number of required RNS factors to maintain security. Consequently, the computational overhead for Number Theoretic Transforms (NTTs) and key-switching operations doubles, and public key sizes balloon.
The Grafting Framework
To address these inefficiencies, we introduce Grafting, a novel framework that decouples numerical precision from the cryptographic modulus structure. Grafting leverages two primary innovations to maximize hardware utilization regardless of the required precision.
- Rational Rescaling: Unlike standard rescaling, which requires dividing the modulus by an existing integer RNS factor, rational rescaling allows for adjustments by a rational number ($Q/Q'$). This flexibility enables the scale factor to be tuned independently of the specific primes in the RNS base.
- Universal Sprouts: Efficient key-switching—the most computationally intensive HE operation—requires specific divisibility properties. Grafting introduces "sprouts," which are small, reusable modulus components (such as powers of two or small NTT primes). These sprouts are "grafted" onto standard, 60-bit RNS primes, ensuring the necessary mathematical structure is maintained without sacrificing word-size efficiency.
- Modulus Resurrection: This technique allows the scheme to "bring back" previously discarded modulus factors. This ensures the current ciphertext modulus remains a divisor of the switching key modulus, preventing the need for multiple, massive public key sets.
Performance Evaluation
The Grafting framework was evaluated against established benchmarks, including the Homomorphic Encryption Security Standard [BCC+24] and parameters from major libraries like HEaaN and OpenFHE. Experiments were conducted on an AMD Ryzen 7 3700X CPU.
The results demonstrate substantial gains across all metrics. By utilizing 60-bit primes on 64-bit hardware instead of smaller, precision-matched primes, the computational workload is effectively halved for core operations. Key results include:
- Speedups: The framework achieved up to a 2.07× speedup for homomorphic multiplications, 1.92× for key-switching, and 1.92× for bootstrapping (BTS).
- Key Size Reduction: Public key and ciphertext sizes were reduced by up to 62%, as fewer RNS factors are required to achieve the same security level.
- Adaptive Precision: In homomorphic comparison tasks, Grafting reduced modulus consumption by 27%, leading to fewer bootstrapping operations and a 1.5× overall execution speedup.
- High Precision Support: The framework successfully supports multiplications with up to 113-bit precision using quadruple-precision data types, a feat difficult to achieve in standard RNS-CKKS.
Conclusion and Future Work
Grafting represents a significant step forward in making RNS-CKKS more efficient and flexible. By treating the modulus as a flexible pool and using sprouts to handle mathematical requirements, developers can maximize machine efficiency.
While Grafting introduces some implementation complexity—particularly in handling power-of-two sprouts which require specialized modular arithmetic—the performance benefits are compelling. Future work includes applying Grafting to other RNS-based schemes like BGV and exploring its integration with hardware accelerators like FPGAs and ASICs, where word-size optimization is even more critical.
Summary updated