Multi-Designated Receiver Signed Public Key Encryption

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 Signature (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).

Donald to be able to create a ciphertext c such that when Bob decrypts c, it obtains some triple (spk Donald , (pk Bob , pk Charlie ), m), but when Charlie decrypts c it obtains some different triple (or does not even decrypt). Instead, we want that if Bob obtains a triple (spk Donald , (pk Bob , pk Charlie ), m), then so will Charlie (and vice-versa). Unforgeability We do not want that Eve can forge a ciphertext as if it were from an honest sender, say Alice, to a vector of receivers Bob and Charlie. Confidentiality If an honest sender Alice encrypts a message m to Bob and Charlie (who are both honest), we do not want Eve, who is dishonest, to find out what m is. Anonymity Suppose there is another honest sender, say Heidi. If Alice encrypts a message m to Bob, and letting c be the corresponding ciphertext, we do not want Eve to find out that Alice is the sender or that Bob is the receiver; Eve should at most learn that someone sent a message to a single receiver. Off-The-Record Suppose Alice sends a message to Bob, Charlie and Donald.

Donald, being dishonest, might be enticed to try convincing Eve that Alice sent some message. However, we do not want Donald to have this capability.