Paper 2023/1244

HERMES: Efficient Ring Packing using MLWE Ciphertexts and Application to Transciphering

Youngjin Bae, CryptoLab Inc.
Jung Hee Cheon, Seoul National University, CryptoLab Inc.
Jaehyung Kim, CryptoLab Inc.
Jai Hyun Park, Seoul National University
Damien Stehlé, CryptoLab Inc.
Abstract

Most of the current fully homomorphic encryption (FHE) schemes are based on either the learning-with-errors (LWE) problem or on its ring variant (RLWE) for storing plaintexts. During the homomorphic computation of FHE schemes, RLWE formats provide high throughput when considering several messages, and LWE formats provide a low latency when there are only a few messages. Efficient conversion can bridge the advantages of each format. However, converting LWE formats into RLWE format, which is called ring packing, has been a challenging problem. We propose an efficient solution for ring packing for FHE. The main improvement of this work is twofold. First, we accelerate the existing ring packing methods by using bootstrapping and ring switching techniques, achieving practical runtimes. Second, we propose a new method for efficient ring packing, HERMES, by using ciphertexts in Module-LWE (MLWE) formats, to also reduce the memory. To this end, we generalize the tools of LWE and RLWE formats for MLWE formats. On a single-thread implementation, HERMES consumes $10.2$s for the ring packing of $2^{15}$ LWE-format ciphertexts into an RLWE-format ciphertext. This gives $41$x higher throughput compared to the state-of-the-art ring packing for FHE, PEGASUS [S&P'21], which takes $51.7$s for packing $2^{12}$ LWE ciphertexts with similar homomorphic capacity. We also illustrate the efficiency of HERMES by using it for transciphering from LWE symmetric encryption to CKKS fully homomorphic encryption, significantly outperforming the recent proposals HERA [Asiacrypt'21] and Rubato [Eurocrypt'22].

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Keywords
Fully Homomorphic EncryptionRing PackingTransciphering
Contact author(s)
youngjin bae @ cryptolab co kr
jhcheon @ snu ac kr
jaehyungkim @ cryptolab co kr
jhyunp @ snu ac kr
damien stehle @ cryptolab co kr
History
2023-08-21: approved
2023-08-17: received
See all versions
Short URL
https://ia.cr/2023/1244
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1244,
      author = {Youngjin Bae and Jung Hee Cheon and Jaehyung Kim and Jai Hyun Park and Damien Stehlé},
      title = {HERMES: Efficient Ring Packing using MLWE Ciphertexts and Application to Transciphering},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1244},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1244}},
      url = {https://eprint.iacr.org/2023/1244}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.