Paper 2022/1046

Post-Quantum Multi-Recipient Public Key Encryption

Joël Alwen, AWS Wickr
Dominik Hartmann, Ruhr University Bochum
Eike Kiltz, Ruhr University Bochum
Marta Mularczyk, AWS Wickr
Peter Schwabe, Max Planck Institute for Security and Privacy, Radboud University Nijmegen

A multi-message multi-recipient PKE (mmPKE) encrypts a batch of messages, in one go, to a corresponding set of independently chosen receiver public keys. The resulting "multi-recipient ciphertext" can be then be reduced (by any 3rd party) to a shorter, receiver specific, "invidual ciphertext". Finally, to recover the $i$-th message in the batch from their indvidual ciphertext the $i$-th receiver only needs their own decryption key. A special case of mmPKE is multi-recipient PKE where all receivers are sent the same message. By treating (m)mPKE and their KEM counterparts as a stand-alone primitives we allow for more efficient constructions than trivially composing individual PKE/KEM instances. This is especially valuable in the post-quantum setting, where PKE/KEM ciphertexts and public keys tend to be far larger than their classic counterparts. In this work we describe a collection of new results around batched KEMs and PKE. We provide both classic and post-quantum proofs for all results. Our results are geared towards practical constructions and applications (for example in the domain of PQ-secure group messaging). Concretely, our results include a new non-adaptive to adaptive compiler for CPA-secure mKEMs resulting in public keys roughly half the size of the previous state-of-the-art [Hashimoto, CCS'21]. We also prove their FO transform for mKEMs to be secure in the quantum random oracle model. We provide the first mKEM combiner as well as two mmPKE constructions. The first is an arbitrary message-length black-box construction from an mKEM (e.g. one produced by combining a PQ with a classic mKEM). The second is optimized for short messages and achieves hybrid PQ/classic security more directly. When encrypting $n$ short messages (e.g. as in several recent mmPKE applications) at 256-bits of security the mmPKE ciphertext are $144 n$ bytes shorter than the generic construction. Finally, we provide an optimized implementation of the (CCA secure) mKEM construction based on the NIST PQC winner Kyber and report benchmarks showing a significant speedup for batched encapsulation and up to 79% savings in ciphertext size compared to a naive solution.

Available format(s)
Public-key cryptography
Publication info
combiners mmPKE mKEM post quantum cryptography
Contact author(s)
alwenjo @ amazon com
dominik hartmann @ rub de
eike kiltz @ rub de
mulmarta @ amazon ch
peter @ cryptojedi org
2022-08-17: approved
2022-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joël Alwen and Dominik Hartmann and Eike Kiltz and Marta Mularczyk and Peter Schwabe},
      title = {Post-Quantum Multi-Recipient Public Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1046},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.