# Provable Encryption

Is it possible to encrypt data in a way that it can be proven that the data is encrypted, without revealing the key?

1. Alice chooses some plaintext, then she encrypts it with a certain scheme. She also creates a proof that she the cypher text was produced with that encryption scheme.
2. When she hands that proof+cypher text to bob, he can verify the proof without contacting Alice again.
3. The proof must not allow decryption of the data, in particular it must not reveal the key
4. The scheme must not allow Alice to influence the generated cypher text in better than brute-force way.

As an example, most convergent encryption schemes satisfy all properties except 3:

1. Alice uses the hash(which doubles as key) as proof
2. Bob can decrypt the data, and verify if the hash matches the decrypted data. He doesn't need to contact anyone that knows the plaintext to do this.
3. Fail
4. The coupling of key and plain-text hash doesn't allow Alice to influence the cypher-text directly.

My intuition tells me such a scheme is impossible, but it has been wrong often enough.

Why do I want such a scheme?

There are hosting systems(such as Tahoe Least-Authority Filesystem) where the client encrypts the data before uploading. One nice property would be if the hoster can claim that he could not have known which data he hosted, because it was encrypted.

-
Can you elaborate on exactly what the proof is about? One way to state that would be to list what behavior(s) of Alice should be caught. Does this include submitting something random as the ciphertext? Ciphertext for which there exist plaintext, but it is random nonsense? Ciphertext for which there exist plaintext, but it is not known to Alice? –  fgrieu Jan 26 '12 at 13:55

There are a number of zero-knowledge proofs for proving knowledge of a plaintext. These work with public key cryptosystems but not block ciphers. For example, with Elgamal: $\langle g^r, m\cdot y^r \rangle$ it is sufficient to prove knowledge of $r$ in $g^r$. This can be done with a Schnorr proof (and made non-interactive with Fiat-Shamir). As the name zero-knowledge implies, it leaks no information about the ciphertext or key. For a filesystem, encrypting each block with a public key cryptosystem is inefficient.

For block ciphers, no efficient proofs of plaintext knowledge are known. You can generate one from general techniques (akin to this proof of a SHA1 preimage) but it will not be efficient.

-