Encrypting messages for multiple recipients

Question

With hybrid cryptography, I want to encrypt a message intended for multiple recipients.

This can be archived (as described here by creating a symmetric secret key, encrypt the message with this key, and then include an encrypted version of the secret key, encrypted with all of the recipients' public keys.

I wonder if it is possible to have a "master recipient" who can decrypt all messages, and then have less privileged recipients who can only decrypt messages encrypted with their specific public key. Will it be possible by some sort of hierarchical keys, to enable a master recipient able to encrypt the secret key even though the secret key is not encrypted the master recipient's own key and added to the message?

Maybe I ought to look into "attribute-based encryption"?

Answer 1

Yes, this is possible. The most natural option is to look at identity-based encryption (I point to the wikipedia page, as it gather some links to various schemes), such as the Boneh-Franklin IBE. An IBE allows to encrypt a message with the identity of the user. After interacting with some trusted authority once in a setup phase, each user can receive the secret key associated to this identity, and decrypt all messages encrypted for their identity. The owner of the master secret key (which is used to derive identity-based secret keys) can decrypt all messages, for any identity. Your intuition about looking into attribute-based encryption is essentially correct, as IBE is a special case of attribute-based encryption.

In fact, you do not need the full power of IBE here, so there is an alternative possibility. The exact feature that you are looking for is enjoyed by the Bresson-Catalano-Pointcheval cryptosystem. Close variants of this scheme were invented simultaneously the same year, by Damgа̊rd and Jurik, and by Cramer and Shoup. It allows to perform the following operation:

• Generate a pair (master public key, master secret key) $= (\mathsf{mpk},\mathsf{msk})$
• Given the master public key $\mathsf{mpk}$, any user $P_i$ can generate a pair public key / secret key $(\mathsf{pk}_i,\mathsf{sk}_i)$
• A message encrypted with $\mathsf{pk}_i$ can be decrypted either with the corresponding secret key $\mathsf{sk}_i$, or with the master secret key $\mathsf{msk}$.

Note that unlike IBE, you cannot simply encrypt using the identity of a user in this system. However, generating a pair $(\mathsf{pk}_i,\mathsf{sk}_i)$ can be done by any user, using only the master public key (while in IBE, the mastersecret key is needed to derive the secret key associated to an identity), so you do not need to have a trusted authority at this step. This might make this scheme more suited than IBE for your exact application.

If you are familiar with the Paillier cryptosystem and the ElGamal cryptosystem (otherwise, ignore what follows), the idea of the scheme is quite natural: a ciphertext is of the form $(g^r \bmod n^2,(1+n)^mh^r \bmod n^2)$, where $n$ is a product of two safe prime, and $(g,h)$ is some specific public key. Given the factorization of $n$, one can decrypt this ciphertext exactly as a Paillier ciphertext, by ignoring the first part of the ciphertext (the second part is exactly a Paillier ciphertext). Alternatively, given $s$ such that $h = g^s$, the ciphertext can be decrypted with a standard ElGamal decryption.

Answer 2

I'd keep it simple. The previous answer is indeed very deep and very complete, this answer is more like an addition :)

Depends on what/why you want to achieve, what is often used in enterprise systems is "key escrow" service. You can see it as a "system/master" user (or multiple sytem users in your case). Every message (or document) encrypted for multiple recepients is as well addressed for these system users having their own keys.

Advantage of this approach is - you can use existing and out-of-box implementations. The issue with this approach is that the keys of the key escrow service become very critical.

As a note - seems I will have to study the mentioned "double trapdoor schemas" mentioned in the other answer, it looks vey interesting :)