Multi-recipient encryption, revisited

A variant of public key encryption that promises efficiency gains due to batch processing is multi-recipient public key encryption (MR-PKE). Precisely, in MR-PKE, a dedicated encryption routine takes a vector of messages and a vector of public keys and outputs a vector of ciphertexts, where the latter can be decrypted individually, as in regular PKE. In this paper we revisit the established security notions of MR-PKE and the related primitive MR-KEM. We identify a subtle flaw in a security model by Bellare, Boldyreva, and Staddon, that also appears in later publications by different authors. We further observe that these security models rely on the knowledge-of-secret-key (KOSK) assumption---a requirement that is rarely met in practice. We resolve this situation by proposing strengthened security notions for MR-PKE and MR-KEMs, together with correspondingly secure yet highly efficient schemes. Importantly, our models abstain from restricting the set of considered adversaries in the way prior models did, and in particular do not require the KOSK setting. We prove our constructions secure assuming hardness of the static Diffie-Hellman problem, in the random oracle model.