Scalable Ciphertext Compression Techniques for Post-Quantum KEMs and their Applications (original) (raw)

Paper 2020/1107

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

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

Abstract

A mathitmultitext−recipient\mathit{multi\text{-}recipient}mathitmultitext−recipient key encapsulation mechanism, or mathsfmKEM\mathsf{mKEM}mathsfmKEM, 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 mathsfmKEM\mathsf{mKEM}mathsfmKEM 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 mathsfmKEM\mathsf{mKEM}mathsfmKEM that can be instantiated from versatile assumptions, including post-quantum ones. We then study these mathsfmKEM\mathsf{mKEM}mathsfmKEM instantiations at a practical level using 8 post-quantum mathsfmKEM\mathsf{mKEM}mathsfmKEMs (which are lattice and isogeny-based NIST candidates), and CSIDH, and show that compared to the trivial solution, our mathsfmKEM\mathsf{mKEM}mathsfmKEM 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 mathsfmKEM\mathsf{mKEM}mathsfmKEM 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.

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}, url = {https://eprint.iacr.org/2020/1107} }