Encryption scheme for social-network-like data sharing data via untrusted server?

Question

I am thinking quite a lot lately abut the problem of secure, privacy-preserving social networking. Distributing the network among trusted, preferably self-hosted servers (like Diaspora, GNU Social etc. attempt to do) is obviously not a good solution for the the large majority of non-technical users, so my thoughts currently focus on cryptography-based approaches that allow the secure sharing of data even if it hosted on "unstrusted" servers. However, I am stuck with the following problem:

Suppose that Alice has three picture albums - A, B and C - and likes to share them with Bob and Carol. Album A should be accessible with both Bob and Carol, while albums B and C are for Bob only. For several reasons, she needs to do this with webspace hosted by a suspicious friend of a friend named Chuck, which Alice doesn't trust at all and thus wants to protect the pictures from.

Now, Alice could do the most obvious thing and encrypt the data before storing it on Chuck's server. Now she could give Bob and Carol the encryption key and configure her webspace to serve album A to both and albums B and C to Bob only (distinguishing both by e.g. password-based authentication). That way, Chuck couldn't view the pictures, and Bob and Carol can view the appropiate sets of pictures.

However, there are serious problems with this approach: If Chuck decides to be stupid and send picture albums B and C to Carol for the fun of it, she is able to view them because all albums are encrypted with the same key.

The only solution to this problem I can see is to give Bob and Carol two different keys and encrypt B and C with Bob's key. However this means that there need to be two versions of album A, one encrypted with Bob's key and one with Carol's. This wastes space, though, especially if more peers come into play; a combinatorial explosion of copies could be the consequence.

Is there any encryption scheme that can remove these problems?

Answer 1

Yes, it's trivial. You encrypt each item with its own random key. You then need only encrypt the key to each album for Bob and Carol.

A typical way to do this is to publish an encrypted per-user keyring -- one for Bob and one for Carol. Bob and Carol can each decrypt their keyrings to get the keys to all the objects they are supposed to access.

The reverse way of doing this is to attach to each group of objects with common permissions a per-group keyring. This is usually used in conjunction with a public key for each user. The key to the group of objects is encrypted with the public keys of every user authorized to access it and those encrypted keys are stored with the group of objects.

Answer 2

The usual solution to this problem would be to use separate session keys for each file (or album), and then encrypt these session keys separately with the long-term keys of the intended recipients.

You could use asymmetric encryption (RSA or other public-key encryption schemes) for the second step, then Alice would only need to know the public keys of Bob and Carol.

With symmetric schemes, Alice would have to negotiate one secret key with Bob, and another one with Carol.

Formally:

1. Alice generates random symmetric keys $K_A$, $K_B$, $K_C$.
2. Alice encrypts $C_A := E_{K_A}(A)$, $C_B := E_{K_B}(B)$, $C_C := E_{K_C}(C)$.
3. Alice uploads $C_A$, $C_B$, $C_C$ to Chuck.
4. Alice obtains public keys $e_B$ for Bob and $e_C$ for Carol.
5. Alice encrypts (asymmetrically) $K^C_A := \tilde E_{e_C}(K_A)$ for Carol, and $K^B_A := \tilde E_{e_B}(K_A)$, $K^B_B := \tilde E_{e_B}(K_B)$, $K^B_C := \tilde E_{e_B}(K_C)$ for Bob.
6. Alice uploads $K^C_A$, $K^B_A$, $K^B_B$, $K^B_C$ to Chuck.
7. Bob now can decrypt $K^B_A$, $K^B_B$, $K^B_C$ to $K_A$, $K_B$, $K_C$, while Carol can only decrypt $K^C_A$ to $K_A$.
8. With these keys, Bob can decrypt $C_A$, $C_B$, $C_C$ to $A$, $B$, $C$, while Carol can only decrypt $C_A$ to $A$.