[Cryptography] End-to-End, One-to-Many, Encryption Question

[Jerry Leichter]

On Jun 11, 2014, at 8:49 PM, Kent Borg <kentborg at borg.org> wrote:
> Alice lives on the far end of a single DSL line, and produces data on a regular basis, she encrypts it with a key only she knows, and she sends it to Bob.
> 
> Bob lives in the cloud (and so has lots of bandwidth), but Bob is in the cloud, and therefore is only partially trusted, so he is given no ability to directly decrypt the data. There is also lot of data accumulated, he doesn't can't store unique copies for each client.
> 
> Charley is a client, one of many (Charley-1, Charley-2, Charley-3, etc., clients can come and go), he lives in a smart phone, say. He asks Bob for a specific piece of data, Bob encrypts it with a Charley-1-specific key and sends it off.
> 
> Charley-1 decrypts the data with a key that Bob does not know.
> 
> If Alice discovers Charley-1 is compromised, she can instruct Bob to delete Charley-1-specific data, destroying his ability to read data from Bob. Alice probably knows everyone's keys, but Bob and Charley do not know each other's keys, and again only Alice knows her key....
The problem as describe to this point has an easy solution:  Alice encrypts the data with a key K.  She then appends to it a bunch of pairs of the form (Charley-1, Enc(C1, K)) (Charley-2, Enc(C2, K)), and so on, where Cn is a key unique to Charley-n and known to him and Alice (but not Bob).  Charley-n can look for a pair with his name on it, decrypt it using Cn, then use the resulting key K to decrypt all the data.

Bob learns nothing about the data.

To remove Charley-n's access, simply remove the name/encrypted key pair with his name on it.

If the data has a reasonably small number of subpieces not all of which are necessarily accessible to all the Charley's, they can be encrypted with unique Ki's and then there will be multiple pairs for a given Charley giving him access to exactly those subpieces he is allowed to see.  (Of course, you can add a level of indirection and have keys for groups, with membership being granted to the group by giving someone a key for the group pair.)

There are more sophisticated protocols for related but distinct problems, e.g., granting the ability to decrypt only certain fields of a database.  But for the problem you seem to be describing, this seems to be the best general solution.

                                                        -- Jerry