### Scalable Ciphertext Compression Techniques for Post-Quantum KEMs and their Applications

Shuichi Katsumata, Kris Kwiatkowski, Federico Pintore, and Thomas Prest

##### Abstract

A $\mathit{multi\text{-}recipient}$ key encapsulation mechanism, or $\mathsf{mKEM}$, provides a scalable solution to securely communicating to a large group, and offers savings in both bandwidth and computational cost compared to the trivial solution of communicating with each member individually. All prior works on $\mathsf{mKEM}$ are only limited to classical assumptions and, although some generic constructions are known, they all require specific properties that are not shared by most post-quantum schemes. In this work, we first provide a simple and efficient generic construction of $\mathsf{mKEM}$ that can be instantiated from versatile assumptions, including post-quantum ones. We then study these $\mathsf{mKEM}$ instantiations at a practical level using 8 post-quantum $\mathsf{mKEM}$s (which are lattice and isogeny-based NIST candidates), and CSIDH, and show that compared to the trivial solution, our $\mathsf{mKEM}$ offers savings of at least one order of magnitude in the bandwidth, and make encryption time shorter by a factor ranging from 1.92 to 35. Additionally, we show that by combining $\mathsf{mKEM}$ with the TreeKEM protocol used by MLS $-$ an IETF draft for secure group messaging $-$ we obtain significant bandwidth savings.

Note: 1 Dec 2020: Fixed the affiliations and added a comment on implicit/explicit rejections. 20 Nov 2021: A typo founded by Marta Mularczyk in the definition of correctness in Def. 3.2 was fixed.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
multi-recipient encryption schemepost-quantum assumptionFujisaki-Okamoto transformNIST candidates
Contact author(s)
shuichi katsumata000 @ gmail com
federico pintore @ gmail com
thomas prest @ pqshield com
kris kwiatkowski @ pqshield com
History
2021-11-20: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/1107

CC BY

BibTeX

@misc{cryptoeprint:2020/1107,
author = {Shuichi Katsumata and Kris Kwiatkowski and Federico Pintore and Thomas Prest},
title = {Scalable Ciphertext Compression Techniques for Post-Quantum KEMs and their Applications},
howpublished = {Cryptology ePrint Archive, Paper 2020/1107},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1107}},
url = {https://eprint.iacr.org/2020/1107}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.