28
$\begingroup$

To give some foreground information: I acknowledge that I am a cryptography newb and not by any means an expert (and probably never will be).

In a recent CS class we had several assignments writing and implementing RSA and Diffie-Hellman. It was fun but it was exclusively two party encryption. I want to implement multi-party encryption. For example, a chatroom or IRC scenario where all parties involved send cyphertext to each other simultaneously. Looking around, I've seen that there are several libraries that accomplish this in other questions. But not just algorithms in general.

I can imagine something like this implemented in RSA and sending out public keys to everyone and simultaneously encrypting and decrypting messages multiple for every other member. For example, 3 people are in a chat room. Person A sends out "Hello guys" two unique cyphertext message that Person B and Person C receive and individually decrypt with their own private keys. This would work, but this seems inefficient and somewhat haphazard.

Is there a generally accepted algorithm that allows multiple parties to use public key encryption at once?

(Once again, this won't go to any production level system. This is just for my own academic curiosity.)

$\endgroup$
3
  • 1
    $\begingroup$ I use an encrypted IRC system, for channel chat it generates a key based on the channel password, and thus uses pre-shared key scheme. Invitations to the encrypted channel are done over a user-to-user channel secured with DH, and include the password. It is simple and breaks the problem down to one of key distribution $\endgroup$ Dec 18, 2013 at 5:57
  • $\begingroup$ I think I get what you mean. A naive solution is to give everyone the group public/private keypair and use that to de/encrypt messages to/from the group, along with their personal signature. The problem is the key needs to be recalculated every time a member exits (or gets kicked out) of the group (i'm actually working on something similar) $\endgroup$
    – rath
    Dec 18, 2013 at 14:02
  • $\begingroup$ "Is there a generally accepted algorithm that allows multiple parties to use public key encryption at once?" - Yes, but it depends on the application. A chat application has different requirements than a cloud storage application. For the chat application, messages have a bounded TTL. For the cloud storage application, files have an unbounded TTL. That little observation can create big problems because revocation/re-keying can become a pain point. $\endgroup$
    – user10496
    Apr 24, 2015 at 1:01

1 Answer 1

39
$\begingroup$

What is usually meant by "group encryption" is not what you are after. Group encryption algorithms strive to achieve the following: a given message is encrypted, and may be decrypted only if sufficiently many group members collaborate. This is not what you seek; what you want is a system such that a given message can be encrypted once and every member of the recipient group can decrypt it independently of all others.

The technical term for what you want is broadcast encryption. A specific and quite challenging case is what is done in Blu-ray discs, and is called AACS. Namely:

  • Each Blu-ray reading device has its own private key.
  • Disc contents ought be readable only by allowed devices (this is the "recipient group") but there are billions of them.
  • It is impractical to include in the disc some data specific to each target device (same disc for everybody, and too many target devices).
  • Communication is one-way only (devices are offline, so the disc contents must be sufficient).
  • Media producers wish to retain some "revocation capability" so that the contents of new discs cannot be read by some known "cracked" devices, while still being readable by other devices which (that's the crucial point) cannot be "updated" in any way (since they have no network capability).

For small groups (as a chat server, with only a few dozen recipients), the problem is rather easy:

  • Have each group member own a public/private key pair.
  • Make a symmetric group key K, known to all members by virtue of sending to each member the encryption of K with his public key.
  • To add a group member, just send him K encrypted with his public key.
  • To remove a group member, since forgetfulness cannot be enforced, you have to create a new group key K' and send it to all remaining members.

The biggest cost in that system is group key renewal, which is necessary only when a member must be removed, and the cost is proportional to the size of the group (an RSA-encrypted value with 2048-bit keys is 256 bytes, which is very tolerable as long as groups are no larger than, say, a few hundreds of people).

$\endgroup$
5
  • $\begingroup$ Nice answer. I think the last paragraph could be improved by giving some comment on how frequently such a process could reasonably handle key refresh, since surely the key exchange cost is a function of both number of people and rate? I can put up with terrible key renewal rates if they not frequent, but if people are leaving every few minutes i wouldn't want several hundred encryptions of the key to send out? $\endgroup$ Dec 18, 2013 at 16:00
  • 7
    $\begingroup$ Well, you do not need to renew the group key if someone merely exits. You need to renew the group key only when you want a former group member to become unable to read subsequent messages -- i.e. not really when someone decides to get some sleep; you renew the key when you want to evict a group member. This should be as frequent as banning/kicking participants (i.e. quite rare). $\endgroup$ Dec 18, 2013 at 16:03
  • $\begingroup$ Good point (and I'm glad you managed to understand my rambling!) {as usual with my +1/thanks answers, this message will be self-destructed in not very many minutes to keep the comments neat} $\endgroup$ Dec 18, 2013 at 16:04
  • $\begingroup$ @Thomas - if you change the chat message (bounded TTL) to doc in storage (unbounded TTL), then a member leaving the group can cause considerable pain. In this case, it seems the work will be bounded by docs in storage, and not members in the group. $\endgroup$
    – user10496
    Apr 23, 2015 at 23:51
  • $\begingroup$ @ThomasPornin, I am not sure if my question is exactly same as this one here (I feel my problem is a slightly simpler problem than this one). Could you please take a look at security.stackexchange.com/questions/194555/…, and see if there exist a simpler solution (or essentially the solution is same)? $\endgroup$
    – chen
    Sep 27, 2018 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.