Is it possible to have a shared secret between an unlimited number of parties asynchronously?

Question

Let's say I encrypt a message with some secret and store it in a database. Later, I want to securely share that secret with someone, so that they can read the message as well. Even later, I want to further expand the group of people who know the secret by adding another person.

Basically, I want end-to-end encryption, but with two differences:

• New parties can be spontaneously added
• Those parties have to be able to share the secret asynchronously

As far as I know, Diffie-Hellman can be applied to situations where there are more than two parties, but:

• All of them have to actively participate it the secret creation process (exchange variables), i.e. one of them can't be offline
• With the entry of each participant, a new secret must be generated, which would render obsolete all messages encrypted with the previous secret(s)
• As the number of participants grows very large, e.g. 1000000, my guess is that the key generation process would get way too slow

Basically, I want a chat room where new people can enter at random.

---

What I thought of, with my very limited knowledge in cryptography, is to have a private key that is encrypted with some temporary secret that is sent over an already secure channel. In other words:

1. Private key is encrypted with the secret X and temporarily stored in a database with ID 123
2. The recipient receives a link somewhere with E2EE already established, like Telegram, with the link and the secret, e.g. https://example.com/key?id=123#X
3. Because browsers don't send anything after the hash # to the server, the server sees only https://example.com/key?id=123, finds the encrypted key with ID 123, returns it to the user, then the user can use X, which has not left their device, to decrypt the key locally
4. The server removes the encrypted key with ID 123 from its database, so even if the E2EE channel gets compromised and someone finds out the secret X - they wouldn't be able to get the encrypted key that it belongs to

Alternatively, if the person you want to share with is physically close, you could present them with a QR code containing that ID 123 and the secret, then they could request the encrypted key from https://example.com/key?id=123, use the secret they've scanned, and decrypt the key.

---

There's a question on Quora, How does group messaging work with end-to-end encryption?, which seems to be very similar to what I'm talking about. However, as the top answer points out:

To generalize even further, you need one additional group exponentiation per party, so if you have 15 parties, it may be a bit tedious to program a generalization for this many parties. The numbers will reach a point of exponentiation where they are no longer computable by your machine.

If you want something that generalizes to 100+ machines, create a client-server model. [...]

In my case, I want to have way more than 15 or even 100 parties, so it seems that Diffie-Hellman won't be reasonable and I would need that "client-server model". I think that what I've described above is exactly such a model, but would it work and be secure enough?

Answer 1

Not sure if I understand your requirements right. Assuming that you need end-to-end encryption, so the encryption key cannot be stored on a server.

Approach with hybrid encryption:

1. secret is encrypted with an ad-hoc generated symmetric data encryption key (DEK)

2. the symmetric key is encrypted (one by one) with the participants asymmetric public key encryption keys (KEK)

3. cipher text and encrypted DEKs are sent to participants

4. each participant can decrypt the DEK using their private KEK

5. DEK can be used to decrypt the secret

Now if a new participant wants to join, any of the existing participants can

1. decrypt the DEK using their private KEK
2. re-encrypt the DEK using the new participant's public KEK
3. send the encrypted DEK to the new participant
4. participant can decrypt DEK with their private KEK and join the conversation