Homomorphic Encryption for Large Integers from Nested Residue Number Systems

Dan Boneh; Jaehyung Kim

Paper 2025/346

Homomorphic Encryption for Large Integers from Nested Residue Number Systems

Dan Boneh

, Stanford University

Jaehyung Kim

, Stanford University

Abstract

Existing fully homomorphic encryption (FHE) schemes primarily support a plaintext space defined over a relatively small prime. However, in some important applications of FHE one needs arithmetic over a large prescribed prime. In this paper we construct a new FHE system that is specifically designed for this purpose. Our system composes three layers of residue systems to enable much better performance than was previously possible. Our experiments show that for arithmetic modulo a 256-bit integer, when compared to the TFHE-rs implementation of 256-bit arithmetic, our new system achieves a factor of a thousand better multiplication throughput and a factor of ten better latency. Moreover, for a 2048-bit prime modulus we achieve far better performance than was previously possible.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Fully Homomorphic Encryption
Contact author(s): dabo @ cs stanford edu
jaehk @ stanford edu
History: 2025-02-25: approved; 2025-02-25: received; See all versions
Short URL: https://ia.cr/2025/346
License: CC BY

BibTeX

@misc{cryptoeprint:2025/346,
      author = {Dan Boneh and Jaehyung Kim},
      title = {Homomorphic Encryption for Large Integers from Nested Residue Number Systems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/346},
      year = {2025},
      url = {https://eprint.iacr.org/2025/346}
}