Paper 2024/1638
Modular Reduction in CKKS
Abstract
The Cheon-Kim-Kim-Song (CKKS) scheme is renowned for its efficiency in encrypted computing over real numbers. However, it lacks an important functionality that most exact schemes have, an efficient modular reduction. This derives from the fundamental difference in encoding structure. The CKKS scheme encodes messages to the least significant bits, while the other schemes encode to the most significant bits (or in an equivalent manner). As a result, CKKS could enjoy an efficient rescaling but lost the ability to modular reduce inherently.
Our key observation is that at the very bottom modulus, plaintexts encoded in the least significant bits can still enjoy the inherent modular reduction of RLWE. We suggest incorporating modular reduction as a primary operation for CKKS and exploring its impact on efficiency. We constructed a novel homomorphic modular reduction algorithm using the discrete bootstrapping from Bae et al. [Asiacrypt'24] and a new discretization algorithm from modulus switching. One of the key advantages of our modular reduction is that its computational complexity grows sublinearly (
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Homomorphic EncryptionCKKSModular Reduction
- Contact author(s)
-
jaehk @ stanford edu
tynoh0219 @ cryptolab co kr - History
- 2024-10-17: revised
- 2024-10-11: received
- See all versions
- Short URL
- https://ia.cr/2024/1638
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1638, author = {Jaehyung Kim and Taeyeong Noh}, title = {Modular Reduction in {CKKS}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1638}, year = {2024}, url = {https://eprint.iacr.org/2024/1638} }