Is there a form of cryptography where the key is derived from the plaintext

Question

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.

Answer 1

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.