Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Sep 30 '11 at 14:10

This question came from our site for professional and enthusiast programmers.

    
Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Sep 30 '11 at 14:27

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
1  
Another suggestion: see how GPG works about sending encrypt email to more than one person, it'll be very close to that approach. –  woliveirajr Sep 30 '11 at 14:46
1  
GPG's approach is essentially the same as the approach in my last paragraph. The main reason you may not want to do it exactly that way is that it would mean a keyring for each object, and you may have a large number of objects with the same access permissions. –  David Schwartz Oct 1 '11 at 0:48
    
This is just what I need! It's almost embarassing that I didn't get that idea earlier. Thanks! –  denisw Jan 3 '12 at 19:40

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$.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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