Welcome to the resource topic for 2022/1046
Title:
Post-Quantum Multi-Recipient Public Key Encryption
Authors: Joël Alwen, Dominik Hartmann, Eike Kiltz, Marta Mularczyk, Peter Schwabe
Abstract: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 et.al., 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.
ePrint: https://eprint.iacr.org/2022/1046
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .