Paper 2024/1014

Grafting: Complementing RNS in CKKS

Abstract

The Residue Number System (RNS) variant of the Cheon-Kim-Kim-Song (CKKS) scheme (SAC 2018) has been widely implemented due to its computational efficiency. However, state-of-the-art implementations fail to use the machine word size tightly, creating inefficiency. As rescaling moduli are chosen to be approximately equal to the scaling factors, the machine's computation budget can be wasted when the scaling factors are not close to the machine's word size. To solve this problem, we present a novel moduli management system called Grafting, that fills the ciphertext moduli with word-sized factors while allowing arbitrary rescaling. Grafting speeds up computations, reduces memory footprints, and makes universal parameters that can be used regardless of target precision. The key ingredient of Grafting is the sprout, which can repeatedly used as a part of the ciphertext modulus. In general, when using an arbitrary ciphertext modulus, several copies of evaluation keys in various moduli are required. However, sprout allows rescaling by various amounts with the same keys, which can be extended to universal sprout that accommodates rescaling by an arbitrary amount. By breaking the dependency of the rescaling amount, scale factors, and RNS modulus, Grafting resolves restrictions in previous RNS-CKKS implementations. We revisit the polynomial approximation and multiplication techniques to reduce the modulus consumption or improve the performance, respectively. We grafted a parameter preset in the HEaaN library and implemented a grafted and non-grafted RNS-CKKS library to measure the improvements with concrete experiments. Benchmark results demonstrate the significance of Grafting, showing a speed-up of $$ for homomorphic multiplications and $$ for bootstrapping compared to the non-grafted variant. The ciphertext and evaluation key sizes are also reduced at a similar rate, while the precision remains the same.