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

Metadata
Available format(s)
PDF
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
2020-09-15: received
See all versions
Short URL
https://ia.cr/2020/1107
License
Creative Commons Attribution
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},
      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.