Provable Encryption

Question

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.

Answer 1

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.

Answer 2

In addition to that, there has been specific proof systems whose one of the motivating argument was such a protocol, now more commonly known as Proof of Knowledge. Goldreich in Chapter 4 of his book, Foundation of Cryptography I has even mentioned why in such a scenario, you prefer to have a Proof of Knowledge rather than Zero Knowledge Proof. That said, I am not aware of many efficient Proof of Knowledge protocols that does what you require and in practice, crytographers tend to use Zero-Knowledge proofs, the likes of which are mentioned by PulpSpy.

On related note, you might find the second last paragraph of section 1.2 of the paper by Bellare and Goldreich, On Defining Proof of Knowledge which settled the definitional issue of such proofs, defining your problem in more concrete fashion and giving further reference to this issue.