Let $m$ be a secret message that needs to be sent to $n >1$ recipients. Let each recipient $r\_i$ have a public key $p\_i$ and private key $s\_i$. Is there a scheme such that we can encrypt the message $m$ using the $n$ public keys and produce a encrypted message $E(m)$ such that only the $n$ intended recipients can decipher the message $m$?


One method could be to encrypt the message $n$ times, using each recipients public key, and append them all. That is, if $e\_i$ is the encrypted message $m$ using the public key $p\_i$, then the encrypted message sent to all the recipients could be $E(m) = p\_1|e\_1|p\_2|e\_2 \dots p\_n|e\_n$, where $|$ is the concatenation operation. But this will increase the size of the encrypted message by $O(n)$. So my question really is – can we keep the message length manageable and simultaneously allow multiple recipients to securely decrypt the message.


Is there a special name given to this kind of cryptography problem? The problem seems natural and perhaps has been investigated. I will be grateful for pointers to literature in this area.



Encrypting a message for multiple recipients 
This problem is often called broadcast encryption: how can you set up a system that will enable transmission of an encrypted message to an arbitrarily chosen subset of the people involved? There's a trade-off between two difficulties. If you just give each user an individual key in a generic public key cryptosystem, without setting up some sort of special system, then there's nothing you can do except to append all the encryptions, which is a problem if the number of users is huge. (Imagine broadcasting an event to a billion subscribers. Adrien's observation is an important point, but it doesn't change the scaling.) In the other extreme, you could assign a different key to each subset you might ever want to broadcast to. This works fine if you care only about a few subsets, but if you want a lot of flexibility then you get too many keys for the users to keep track of. It turns out that there are nontrivial solutions to this problem. The original paper is by Fiat and Naor (in Crypto '93), and searching for "broadcast encryption" online will give tons of follow-up papers offering extensions and improvements.


You might also be interested in "attribute-based encryption", in which each user is associated with a list of different attributes and you can encrypt messages so they can be decrypted by just the users with desired combinations of attributes. This is a somewhat different approach, but it has some beautiful consequences. The original paper is by Sahai and Waters (Eurocrypt 2005), and again there have been many further papers.


