EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Modular Reduction in CKKS

Jaehyung Kim, Taeyeong Noh

IACR Communications in Cryptology · 07.07.2025 · 2 (2)

DOI: 10.62056/aevur-iuc ↗

Kurz gefasst

Fachartikel in der Zeitschrift IACR Communications in Cryptology, online erschienen am 07.07.2025. Verfasst von Jaehyung Kim und 1 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. Instead of homomorphically approximating the modular reduction function, we suggest to use the inherent modular reduction over ℤ q [ X ] / ( X N + 1 ) . We construct 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 ( O ( log k ) ) as we increase the input range [ 0 , k ) , which is asymptotically better than the state-of-the-art with ≥ O ( k ) . We checked our algorithms with concrete experiments. Notably, our modulo 1 function for input range [ 0 , 2 20 ) takes only 44.9 seconds with 13.3 bits of (mean) precision, in a single-threaded CPU. Recall that modular reduction over such a large range was almost infeasible in the previous works, as they need to evaluate a polynomial of degree > 2 20 (or equivalent). As an application of our method, we compared a bit decomposition based on our framework with the state-of-the-art method from Drucker et al. [J.Cryptol'24]. Our method is 7.1 × faster while reducing the failure probability by more than two orders of magnitude.

Zitieren

APA

Kim, J., & Noh, T. (2025). Modular Reduction in CKKS. IACR Communications in Cryptology, 2(2). https://doi.org/10.62056/aevur-iuc

Vancouver

Kim J, Noh T. Modular Reduction in CKKS. IACR Communications in Cryptology. 2025;2(2). doi:10.62056/aevur-iuc

BibTeX
@article{Kim2025,
  author = {Kim, Jaehyung and Noh, Taeyeong},
  title = {Modular Reduction in CKKS},
  journal = {IACR Communications in Cryptology},
  year = {2025},
  volume = {2},
  number = {2},
  doi = {10.62056/aevur-iuc}
}
Kostenlos starten →