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

A multi-recipient key encapsulation mechanism, or \(\mathsf {m}\mathsf {KEM}\), 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 {m}\mathsf {KEM}\) 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 {m}\mathsf {KEM}\) that can be instantiated from versatile assumptions, including post-quantum ones. We then study these \(\mathsf {m}\mathsf {KEM}\) instantiations at a practical level using 8 post-quantum \(\mathsf {KEM}\)s (which are lattice and isogeny-based NIST candidates), and CSIDH, and show that compared to the trivial solution, our \(\mathsf {m}\mathsf {KEM}\) 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 {m}\mathsf {KEM}\) with the TreeKEM protocol used by MLS – an IETF draft for secure group messaging – we obtain significant bandwidth savings.