International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Youngjin Bae , CryptoLab Inc.
Jung Hee Cheon , CryptoLab Inc. / Seoul National University
Jaehyung Kim , CryptoLab Inc.
Jai Hyun Park , Seoul National University
Damien Stehlé , CryptoLab Inc.
Download:
DOI: 10.1007/978-3-031-38551-3_2 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
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 \textit{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, \textsc{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, \textsc{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, \textsc{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 \textsc{HERMES} by using it for transciphering from LWE symmetric encryption to CKKS fully homomorphic encryption, significantly outperforming the recent proposals \textsc{HERA} [Asiacrypt'21] and \textsc{Rubato} [Eurocrypt'22].
BibTeX
@inproceedings{crypto-2023-33273,
  title={HERMES: Efficient Ring Packing using MLWE Ciphertexts and Application to Transciphering},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38551-3_2},
  author={Youngjin Bae and Jung Hee Cheon and Jaehyung Kim and Jai Hyun Park and Damien Stehlé},
  year=2023
}