Future-Proof Encrypt for Multiple Independent Parties

Question

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely locally without a network. In short I want two functions

encrypt(message, key1, key2, key3, ...) -> code
decrypt(code, keyX) -> message                   for keyX in (key1, key2, key3...)
decrypt(code, keyY) -> random                    for keyY not (key1, key2, key3...)

Ideally these functions would also have the property that

encrypt(message, key1) -> code1   decrypt(code1, key1) -> message
encrypt(code1, key2) -> code2     decrypt(code2, key1) -> message, decrypt(code2, key2) -> message

This seems like it should be relatively possible to do but I can't figure out how to do it yet. In my research I came across similar problems which many people were calling broadcast encryption but when I read up on it, it seems like for most broadcast encryption schemes require that you broadcast some information about what set of people are allowed to unlock the content and this is used by everyone to calculate their new keys. This isn't want I want. I need that the "locks" can't change and that adding a new lock doesn't invalidate the old ones.

A physical metaphor would be if you were locking a box lid to bottom using some number of padlocks. The system I am looking for would be like a chain of padlocks so that opening any of them separates the top from the bottom of the box. Furthermore, if you add another new padlock on the end of the chain somehow, any of the original keys are still just as useful at opening the whole box. Anyone have some ideas or links to read up on? Thanks.

Answer 1

Given some encryption, $encr$, keys, ${k_1, k_2, ..., k_n}$, what if you took your message $m$, generate a unique key specific to this message $K$, then send:

• $encr(m, K)$
• $encr(K, K_1)$, ... , $encr(K, K_n)$

That is, send your message encrypted with a master key, and add in the master key encrypted $n$ times for each potential destination. Anyone with one of they key can figure the master key and read the message.

Caveat: you'll have to add some extra bits to your key size as some information will leak. Someone trying to break your encryption will rely on the fact that the same master K is encrypted multiple times. So, you'll need the encryption to be extra solid as the number of destination increases. By having keys large enough and a solid enough $encr$ encryption it should hold. You can also throw in just as many random block of data alongside the encrypted keys, for extra security.