Secure Deduplication and Encryption in a data store

Question

Assume:

• We have a centralized data store that can store whatever we need
• Every user is online
• Function $f : File \to Key$ gets access to the store, and is the same for all users.
• $g : Key \to File$ should retrieve the file so that $g \circ f = id$.
• Eve can't break modern algorithms.

Then:

1. Eve wants to know who inserts file $A$, and has a copy of file $A$ as well as read access to the whole store and connection sniffing on all other users
2. Alice inserts file $A$ with function $f(A)$
3. Bob inserts file $A$ with function $f(A)$

Is there a suitable definition for $f$ and $g$ that:

• Doesn't store $A$ multiple times
• Doesn't let Eve know that Alice and Bob inserted file A.

What if we let $f$ store $A$ multiple times but then after:

• Joe gets Alice and Bob's output from $f$ as well as access to the store

Can Joe deduplicate the two copies of $A$:

• Without Eve knowing who has $A$?
• Without causing future retrievals of $A$ by Alice or Bob reveal that they have $A$.

Answer 1

If Alice, Bob et al. can share a secret, for example, using some sort of key exchange protocol, it is possible to use convergent encryption in a way that fulfills the requirements. Otherwise it probably isn't.

---

First, assume the users know a secret key $s$. They use convergent encryption with the key derived using $s$. For example, $k = \operatorname{HMAC}_s(\operatorname{HMAC}_s(p))$ and $c = (\operatorname{HMAC}_s(p), E_k(p))$ to encrypt plaintext $p$. $E$ could be AES in a suitable mode.

To upload a file, Alice calculates $\operatorname{HMAC}_s(p)$ and checks if the store has it. If it does, no need to transfer again, she is done. If it isn't, she uploads the encrypted file so that it can be queried using $\operatorname{HMAC}_s(p)$ which she stores as $key$. Bob goes through the same process.

Eve knows they have uploaded the same file, but knows nothing else. She cannot test if the file is $A$ because she does not know $s$. Neither can she decrypt it.

---

Now, assuming sharing $s$ is not possible:

Eve wants to know who inserts file A, and has a copy of file A as well as read access to the whole store and connection sniffing on all other users

This implies that $f$ must not send the same thing over to the store when Eve sends $A$ as when Alice does. Otherwise Eve could simulate $f$ and compare the traffic to Alice's. The store can also not deduplicate the data in any way, because it has no more information than Eve does.

Thus, this is impossible:

Is there a suitable definition for f and g that:

• Doesn't store A multiple times
• Doesn't let Eve know that Alice and Bob inserted file A.

So $f$ must store duplicate copies, and must give each user a different access key. Now, assuming that's the case and Joe has Alice and Bob's keys:

Can Joe deduplicate the two copies of A:

• Without Eve knowing who has A?
• Without causing future retrievals of A by Alice or Bob reveal that they have A.

Joe could be allowed to say replace one of the copies with a pointer to the other + some token that allows that user to decrypt the first copy (e.g. $E_b(a)$ where $a$ is Alice's key to $A$ and $b$ Bob's). However, Eve would now know at least that the two files match.

In this case $f$ would just be encryption with a random key $r$, and $key$ would include both that key and some identifier that $g$ would use to request for the data.