7
$\begingroup$

Imagine you are building a shared remote storage system where you send everyones files to a central storage, but you want to de-dup the files between multiple users so we don't store the same file more than once. At the same time you want to encrypt the data so the service provider or anyone who doesn't have the file can't decrypt the file.

In this case you can imagine deriving a symmetric encryption key from the contents of the file (say by taking some cryptographic hash of the file) such that everyone who owns the file can compute the key easily, but people without access to the file can't discover it.

Then users encrypt the file with this key and send us the encyrpted blob. We can internally check against a dictionary of hashes of encrypted blobs to determine if we already have the blob or not and either store it or drop it.

I imagine that deriving a key from the plaintext is a terrible idea for most encryption schemes, but I'm wondering if there is a scheme out there, or if there is a known technique for doing this.

$\endgroup$
9
  • 4
    $\begingroup$ If the goal is simply to de-dub, why not make the protocol such that the identifier of a file is its hash, and let that be totally separate about how users encrypt it? E.g. let users choose whatever passwords they like, but expect them to supply the hash of the plaintext along with the ciphertext? $\endgroup$
    – caveman
    Aug 19 at 20:40
  • $\begingroup$ Sure, but I need to encrypt everyones file with the same key, without actually knowing the key, that's the part I'm interested in. How can my users share an encryption key for this blob? My idea is, the thing they all know is the contents of the file, if they already know the contents, then it's safe for them to decrypt the file. If they all choose different passwords, I wouuld have to store a copy for each of them since the ciphertext will all be different? $\endgroup$
    – Matt
    Aug 19 at 21:21
  • 1
    $\begingroup$ "I need to encrypt everyones file with the same key," Why? That's a very weird requirement. $\endgroup$ Aug 19 at 21:31
  • 3
    $\begingroup$ If I use two keys, wouldn't I have to store the encrypted blob twice? I don't want to do that. To be clear, I mean the same file so if alice has foo.mp3 and bob has foo.mp3, I want both of them to upload the same encrypted blob so I can realize they are the same and only store one copy, but without the central service being able to know what is in the file. $\endgroup$
    – Matt
    Aug 19 at 21:41
  • 1
    $\begingroup$ Do you want users to give you ability to decrypt their files which you host for them? $\endgroup$
    – caveman
    Aug 19 at 22:32
16
$\begingroup$

Encrypting $M$ using $H(M)$ as the key is a natural and well-studied approach to deduplication. It is known in the literature as convergent encryption or message-locked encryption.

The natural problem with this approach is that it cannot achieve the standard notions of security for encryption (IND-CPA, IND-CCA, etc). Indeed, anyone who knows $M$ will be able to verify whether a candidate ciphertext decrypts to $M$. The question then becomes: what is the "best possible" level of security that one could hope for, and can we achieve it?

The most thorough analysis of message-locked encryption that I know of is:

Mihir Bellare, Sriram Keelveedhi, Thomas Ristenpart: Message-Locked Encryption and Secure Deduplication, Eurocrypt 2013.

They define relevant security notions, and give corresponding constructions & proofs. They also consider some other security goals closely related to the deduplication application, separate from standard secrecy and integrity.

You can search ePrint and find many other papers with "message-locked" or "deduplication" (for other approaches) in the title. Note that message-locked encryption is non-interactive, but the problem of deduplication becomes a little easier when you allow interaction. Hence, many of the techniques that you find may be interactive.

$\endgroup$
2
  • $\begingroup$ After removing duplications of different encryptions of the same cleartext, will distinct users be able to decrypt the unique deduplicated copy by using their own password? As far as I understood, with OP's scenario, different users upload copies of the same file, except that each is encrypted by user's own password. $\endgroup$
    – caveman
    Aug 21 at 0:52
  • $\begingroup$ If $M$ is encrypted with $H(M)$ then it is not encrypted with the user's password. If you want a user to be able to decrypt, then you must store $H(M)$ encrypted under that user's password. Note that this is a very short ciphertext. $\endgroup$
    – Mikero
    Aug 21 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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