Suppose I have a file server running ZFS with file deduplication enabled, and I have two users that are sharing files: Alice and Carol. If Alice uploads huge_file.tgz to her www/ directory, and Carol uploads the same huge_file.tgz to her www/ directory, then they are only stored on disk once, and both files are available to the world.

Now, instead of Alice and Carol wanting to share huge_file.tgz with everybody, Alice only wants to share it with Bob, and Carol only wants to share with Dan, and we want this sharing to be enforced with public keys, and we want the sharing to work with ZFS's deduplication. We obviously want to abandon Semantic Security here, since the same plaintext must encrypt to the same cyphertext.

Given that, does the following make sense: both Alice and Carol encrypt huge_file.tgz using a symmetric algorithm with deterministic nonce (all null, perhaps?) and a key derived from the file's contents (a sha hash?). They will both then generate the same ciphertext, and then Alice can encrypt the (deterministic) symmetric encryption key to Bob's public key, and Carol can encrypt the key to Dan's public key. So, Alice's www/ directory will hold huge_file.tgz.encrypted as well as encrypted_key_for_bob.bin, while Carol's www/ directory will hold huge_file.tgz.encrypted as well as encrypted_key_for_dan.bin . Now, we have the bulk of the data being deduplicated, and a tiny file specific to each recipient, which is only readable by that recipient.

Is this method at all sane? Aside from abandoning semantic security (basically a prereq here), the only weakness that I (somebody with basically no crypto knowledge) can see is that using a straightforward sha for the key is dangerous because that's information that a user could reasonably publicly leak; doing something like using the MD5 of the SHA doesn't increase the "strength" of the system at all, but it does decrease the likelihood that the symmetric "secret" would be innocently leaked.

Even better than poking holes in what I've written here, could somebody point me to a legitimate, publicly reviewed, public key cryptosystem that allows deduplication? I'd love to simply use something that an expert has created, if such a thing exists.

  • $\begingroup$ This is known as convergent encryption. Unless your question has any aspects not covered by that question, we could close it as a duplicate ;) $\endgroup$ – CodesInChaos Mar 19 '13 at 18:17
  • $\begingroup$ No, I don't think my question adds anything to that discussion. Somehow I didn't see that post when looking for questions similar to mine. Thanks for the link! $\endgroup$ – tsuraan Mar 19 '13 at 18:22
  • $\begingroup$ Here's one published this year: eprint.iacr.org/2012/631.pdf $\endgroup$ – David Cash Mar 19 '13 at 18:43