Paper 2022/256

Multi-Designated Receiver Signed Public Key Encryption

Abstract

This paper introduces a new type of public-key encryption scheme, called Multi-Designated Receiver Signed Public Key Encryption (MDRS-PKE), which allows a sender to select a set of designated receivers and both encrypt and sign a message that only these receivers will be able to read and authenticate (confidentiality and authenticity). An MDRS-PKE scheme provides several additional security properties which allow for a fundamentally new type of communication not considered before. Namely, it satisfies consistency---a dishonest sender cannot make different receivers receive different messages---off-the-record---a dishonest receiver cannot convince a third party of what message was sent (e.g., by selling their secret key), because dishonest receivers have the ability to forge signatures---and anonymity---parties that are not in the set of designated receivers cannot identify who the sender and designated receivers are. We give a construction of an MDRS-PKE scheme from standard assumptions. At the core of our construction lies yet another new type of public-key encryption scheme, which is of independent interest: Public Key Encryption for Broadcast (PKEBC) which provides all the security guarantees of MDRS-PKE schemes, except authenticity. We note that MDRS-PKE schemes give strictly more guarantees than Multi-Designated Verifier Signatures (MDVS) schemes with privacy of identities. This in particular means that our MDRS-PKE construction yields the first MDVS scheme with privacy of identities from standard assumptions. The only prior construction of such schemes was based on Verifiable Functional Encryption for general circuits (Damgård et al., TCC '20).

Note: The Off-The-Record security proof of the MDRS-PKE construction given in the prior full version of this paper as well as in the published version is wrong. To fix the issue, in this new version we modify the construction by adding a strongly unforgeable one-time signature scheme (that we use to bind MDVS signatures and PKEBC ciphertexts together) and update all the security proofs of the MDRS-PKE construction accordingly. We note that the security proof of our new construction relies on the unforgeability of the underlying MDVS; while the type of unforgeability we require the underlying MDVS scheme is stronger than the notion considered by Damgard et al. (TCC '20) (in particular, our notion provides adversaries with access to a signature verification oracle, which we use to handle decryption queries), the MDVS construction given in (Chakraborty et al., Eurocrypt '23) does satisfy this new stronger notion (and is based on standard assumptions). In this new version we also assume perfect correctness from the PKE scheme underlying the PKEBC construction, and updated the security analysis of our PKEBC construction accordingly. While the two changes mentioned above are the main ones, there are other minor updates in this new full version.