13
$\begingroup$

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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you for your answer. It answers my question, but I am curious about one thing. You say that "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" Des it mean that it is an open problem to construct a better scheme or is it a proven result that it is impossible to construct some such system? $\endgroup$
    – Balaji
    Commented Apr 18, 2011 at 16:17
  • $\begingroup$ Hmm, I should have thought a little harder. I'm almost sure it is true, and it ought to be provable, but it depends on how you formulate it. Given black-box access to a public key cryptosystem, you could ask whether there's any way to come up with a shorter string than the concatenated encryptions, such that each recipient could recover the message, and such that if anyone else could break this system, it would break the original public key cryptosystem. I think you should be able to prove this is impossible, but it would be foolish to be too certain without actually proving it. $\endgroup$
    – Henry Cohn
    Commented Apr 18, 2011 at 16:56
  • $\begingroup$ In any case, I don't know of a reference offhand. It seems like something that must have been thought about before. Maybe it is in the literature somewhere, maybe it is not published because it can be done by pretty standard techniques, maybe it is harder than I expect, and maybe I am just wrong about whether it is possible. $\endgroup$
    – Henry Cohn
    Commented Apr 18, 2011 at 16:58
12
$\begingroup$

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.

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.

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ From the practical point of view, I agree that it solves the problem. You can even create a new private/public key, send it encrypted once to each of your friends, and from now on you will have a new key for the "group" that you can use how many times you want with the cost of a single encryption. From the theoretical point of view, it is still interesting if you don't trust symmetric encryption, which as far as I know, for the available fast algorithms, never proven to be equivalent to a known hard problem (such as factorization or discrete logarithm). $\endgroup$
    – KotelKanim
    Commented Apr 18, 2011 at 11:12
  • 4
    $\begingroup$ I don't think that factorization or discrete logarithm are known to be hard. $\endgroup$
    – Laurent Berger
    Commented Apr 18, 2011 at 11:23
  • $\begingroup$ Indeed they aren't known to be hard. In fact, from my perspective the comparison between public and private key crypto goes the other way: people should be much more suspicious of public key crypto. It's based on the miracle that there are a handful of useful number-theoretic constructions, and all of them have subtle structure that may very plausibly allow much better attacks than what's currently known. (I'd be very surprised if the number field sieve is the best possible factoring algorithm.) By contrast, building secure private-key ciphers appears to be much more doable. $\endgroup$
    – Henry Cohn
    Commented Apr 18, 2011 at 12:34
  • $\begingroup$ So it's true that private-key ciphers aren't (in practice) backed up with reductions to other hard problems, but the evidence that we can build secure ciphers is arguably more compelling than the evidence that any of the hard problems used in public key cryptography is actually hard. $\endgroup$
    – Henry Cohn
    Commented Apr 18, 2011 at 12:41
  • $\begingroup$ But the size of the message still grows as $O(n)$. $\endgroup$
    – Nate Eldredge
    Commented Nov 12, 2011 at 21:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .