Cryptology ePrint Archive: Report 2020/1107

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

Shuichi Katsumata and Kris Kwiatkowski and 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.

Category / Keywords: public-key cryptography / multi-recipient encryption scheme, post-quantum assumption, Fujisaki-Okamoto transform, NIST candidates

Original Publication (with major differences): IACR-ASIACRYPT-2020

Date: received 14 Sep 2020, last revised 1 Dec 2020

Contact author: shuichi katsumata000 at gmail com,federico pintore@gmail com,thomas prest@pqshield com,kris kwiatkowski@pqshield com

Available format(s): PDF | BibTeX Citation

Note: Fixed the affiliations and added a comment on implicit/explicit rejections.

Version: 20201202:004706 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]