Encrypting a message for multiple recipients - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:50:34Z http://mathoverflow.net/feeds/question/62095 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62095/encrypting-a-message-for-multiple-recipients Encrypting a message for multiple recipients Balaji 2011-04-18T07:31:12Z 2011-04-18T12:08:09Z <p>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\$?</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/62095/encrypting-a-message-for-multiple-recipients/62105#62105 Answer by Adrien for Encrypting a message for multiple recipients Adrien 2011-04-18T10:08:08Z 2011-04-18T10:08:08Z <p>This is an interesting question. But it seems to me that in practical cases, you don't encrypt the whole message with the public key of the recipient. Usually, you encrypt it with a fast symmetric algorithm (eg AES) using a random key \$K\$, and encrypt \$K\$ with the public key.</p> <p>The size of \$K\$ is clearly negligible compared to the size of the message. Hence, if you have to send the same message to several recipients, you just have to encrypt \$K\$ several time and to append the result to the encrypted message, which doesn't increase its size too much.</p> <p>Another advantage of this method is that if you want to add a new recipient, you don't have to encrypt the whole message again. Just encrypt \$K\$ with the public key of your new friend and append the result to the old message.</p> http://mathoverflow.net/questions/62095/encrypting-a-message-for-multiple-recipients/62111#62111 Answer by Henry Cohn for Encrypting a message for multiple recipients Henry Cohn 2011-04-18T12:08:09Z 2011-04-18T12:08:09Z <p>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.</p> <p>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.</p>