Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


How Multi-Recipient KEMs can help the Deployment of Post-Quantum Cryptography

April 12, 2024


Thomas Prest - PQShield


The main purpose of this work is to raise awareness about a primitive that can provide large efficiency gains in post-quantum cryptography: multi-recipient KEMs, or mKEMs. In a nutshell, when encapsulating a key to \(N\) parties, an mKEM generates a single ciphertext that can be decapsulated by all parties. The size of an mKEM ciphertext can be significantly smaller than the sum of the sizes of \(N\) KEM ciphertexts. Moreover, individual receivers only need a small part of the mKEM ciphertext to run decapsulation. We then propose mKyber, a very compact mKEM based on Kyber. Asymptotically, the size of an mKyber multi-recipient ciphertext is 16 times smaller than the sum of the sizes of N Kyber ciphertexts. The algorithmic description and parameters of mKyber and Kyber are very similar, which facilitates the re-use of existing security analyses, implementations, and formal verification tools that have been developed for Kyber.

Finally, we showcase some selected applications. mKEMs can be used to greatly reduce the bandwidth cost of the group key agreement protocol underlying the Message Layer Security (MLS) secure group messaging standard. Reducing bandwidth is one of the primary design considerations for MLS. More fundamentally, mKEMs reduce the cost of broadcasting private information to groups of recipients (e.g. a fleet of Cloud Hardware Security Modules).

Presented at

5th PQC Standardization Conference (2024) [in-person]

Event Details


    The NIST PQC conference will be held at the:
    Hilton Washington DC/Rockville Hotel
    1750 Rockville Pike
    Rockville, MD 20852

Related Topics

Security and Privacy: post-quantum cryptography

Created April 11, 2024, Updated April 15, 2024