<p>For symmetric-key encryption:</p>

<p>If Alice and Bob know a proof that $D_K(E_K(x))=x$ for all $x,K$, then they should be able to prove this fact in zero knowledge.  In particular, they can produce boolean circuits for $D_\cdot(\cdot)$ and $E_\cdot(\cdot)$, publish a commitment to each boolean circuit, and then turn their proof into a zero-knowledge proof.  In particular, verifying that $D_K(E_K(x))=x$ for all $x,K$ is in <strong>co-NP</strong>, and thus in <strong>IP</strong>, and there are zero-knowledge proofs for all of <strong>IP</strong> (and all of <strong>PSPACE</strong>).</p>

<p>Now if Alice wants to encrypt a message, she can give a zero-knowledge proof that she has encrypted some message correctly by doing the following: publish commitments $C(x),C(K)$ to her message $x$ and her key $K$; publish a commitment $C(y)$ to her ciphertext $y=E_K(x)$; and now give a zero-knowledge proof that all the commitments are consistent (the ciphertext corresponding to $C(y)$ is a correct encryption, under the boolean circuit for encryption that was committed to earlier, under the key corresponding to $C(K)$ of the message corresponding to $C(x)$).  Whether this is a useful thing to prove is another matter entirely -- it's not clear exactly what you are looking for or how you would use a solution to your problem, but hopefully this will give you some ideas.</p>

<p>For public-key encryption:</p>

<p>See Sadeq Dousti's comment.  The exposition above can be readily adjusted to fit the public-key encryption setting, along the lines Sadeq Dousti suggests.</p>

CC BY-SA 3.0
2013-08-26T02:56:48.263Z
2013-08-26T02:56:48.263Z
D.W.
<p>You can adapt the work of <a href="http://link.springer.com/chapter/10.1007%2F3-540-46416-6_8" rel="nofollow">Okamoto-Chaum-Ohta</a> to this case. Let $P$ be the prover, $V$ the verifier, $E$ the public encryption key + algorithm (common input to $P$ and $V$), and $D$ the secret decryption key + algorithm (private input to $P$). We assume that $E$ can be probabilistic (to satisfy semantic security, it <strong>has</strong> to be), and therefore it uses some randomness to encrypt a message: $c = E(x ; r)$</p>

<p>Further, assume that $Com$ is a commitment scheme.</p>

<p>The protocol is as follows (in the first step, $P$ commits to a random string $u$ using randomness $\rho$):</p>

<ol>
<li>$P \to V : Com(u ; \rho)$</li>
<li>$V \to P : c = E(x ; r)$</li>
<li>$P \to V : Dec(c) \oplus u$</li>
<li>$V \to P : x, r$</li>
<li>$P \to V : \rho$</li>
</ol>

<p>The idea is that $P$ shows to $V$ that he can decrypt by committing to the decryption. However, he does not reveal the decryption until $V$ shows that he actually knows the plaintext.</p>

<p>Contrary to its simplicity, this protocol has lots of caveats. For instance, one can show that if $Com$ and $E$ are related in a <em>bizarre</em> way, the protocol is not zero-knowledge.
Another caveat is that if $E$ is in fact probabilistic, showing that the protocol is a proof of ability is very hard (if not impossible). However, if it is deterministic (say, merely a trapdoor one-way permutation), then the proof is rather easy. In any case, one can show that the protocol can be used for identification (in the smart-card model of Feige, Fiat, and Shamir).</p>

CC BY-SA 3.0
2013-08-27T12:43:55.563Z
@RickyDemer: I assume that $D$ always succeeds in decryption, but assuming that it only fails with negligible probability will also do the job. The initial commitment has nothing to do with the ZK property; it is used to show that the protocol is actually a proof: The knowledge extractor (or, more precisely, the "ability extractor") uses this initial commitment to later extract $x$ from a prover $P^*$.
Sadeq Dousti
CC BY-SA 3.0
2013-08-27T20:11:27.507Z
@RickyDemer: Yes, there are three interpretations for "for all $x$, D only fails with negligible probability," depending on what the probability is taken over: (1) only the randomness used by $D$, (2) the randomness used by $E$ and $D$, (3) the randomness used by $E$, $D$ and the key generation algorithm.
Sadeq Dousti
CC BY-SA 3.0
2013-08-27T20:24:34.130Z
@RickyDemer: Yes, you fixed the public/private key, as well as the randomness used by $E$ (i.e., interpretation 1).
Sadeq Dousti
CC BY-SA 3.0
2013-08-26T10:25:14.423Z
2013-08-26T10:47:39.377Z
2013-08-26T10:47:39.377Z
Sadeq Dousti
<p>This seems like a straightforward application of zero knowledge techniques, but an answer eludes me. </p>

<p>Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess functions $E()$ and $D()$ to encrypt and decrypt arbitrary $n$-bit messages. </p>

<p>Charlie wishes to verify this claim, but Alice and Bob don't want Charlie to learn anything about the method. </p>

<p>Can Charlie verify that Alice and Bob can indeed encrypt and decrypt in a zero knowledge fashion ? </p>

CC BY-SA 3.0
2013-08-25T07:38:24.373Z
It would mean that there should be some message x such that $D(E(x)) != x$, yes ?
Suresh Venkat
CC BY-SA 3.0
2013-08-25T17:24:40.873Z
In ZK proofs, the prover $P$ and the verifier $V$ have access to a common input $x$. Depending on the flavor of the ZK proof, various things are proven about $x$: (1) In a language-membership proof, $P$ proves that $x \in L$ for some language $L$. (2) In a proof of knowledge, $P$ proves the knowledge of some $w$ such that $(x,w) \in R$, where $R$ is typically an NP relation. (3) In a proof of ability, $P$ proves that for any $y$ chosen by $V$, he can find some $w$ such that some predicate $\pi(x,y,w)$ holds (this is my simplification).
Sadeq Dousti
CC BY-SA 3.0
2013-08-25T17:29:06.483Z
(Cont'd) If $(E, D)$ is a public-key encryption scheme, then $E$ is made public, and can be used as the common input $x$ in a ZK proof of ability. Then, $P$ can prove in ZK, that for any $y=E(m)$, he can find some message $w$, such that $D(E(m))=w$ holds. If this is what you want, i.e., if $(E, D)$ is a public-key encryption scheme, I think I might be able to write an answer for your question. Otherwise, i.e., if $(E, D)$ is a secret-key encryption scheme, I can't imagine the context for a proof. That is, I don't know what the common input between $P$ and $V$ is.
Sadeq Dousti
CC BY-SA 3.0
2013-08-25T17:48:31.607Z
@RickyDemer I'd want to prevent A and B from using the identity by positing that C should not be able to decrypt. I think Sadeq's distinction between PK and SK might be useful, and so let's assume that the encryption scheme is PK, and that E is public, and so the goal is to provide a ZK proof that decryption is possible.
Suresh Venkat
CC BY-SA 3.0
2013-08-25T23:07:54.303Z
@RobertRicci In retrospect, this question is more open-ended than I thought, so I'm flexible on how one defines it. I was thinking about it in a ZK way (i.e any information leakage of any kind is not permitted). so the latter would be a definite no-no.
Suresh Venkat
CC BY-SA 3.0
2013-08-26T00:34:34.773Z
I guess to prove that the protocol works they themselves should have a proof of this fact, simply having the protocol is not enough. And correctness of the protocol is not a finite statement and is not clear has a proof even in ZFC. So maybe you should put a restriction on the maximum size of input that the protocol works on. They you have two finite functions and you want to show that the composition of the two functions is identity without letting the adversary learn the functions.
Kaveh
CC BY-SA 3.0
2013-08-26T00:37:17.987Z
It might be possible to modify the following simple protocol to become zero knowledge by adding some random string to the message before its encryption by A: Adv. selects and sends a message to A, A encrypts it and sends it to B, B decrypts it and sends it to Adv. ps: I think for it the goal to be possible the Adv. should be able to observe all interactions between A and B.
Kaveh
<cr.crypto-security><zero-knowledge>
Zero knowledge verification of an encryption protocol
Suresh Venkat
# Zero knowledge verification of an encryption protocol

(Asked by: username_0 on 2013-08-25)

This seems like a straightforward application of zero knowledge techniques, but an answer eludes me.

Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess functions $E()$ and $D()$ to encrypt and decrypt arbitrary $n$-bit messages.

Charlie wishes to verify this claim, but Alice and Bob don't want Charlie to learn anything about the method.

Can Charlie verify that Alice and Bob can indeed encrypt and decrypt in a zero knowledge fashion ?

**Tags:** cr.crypto-security, zero-knowledge
> **Comments:**
> **username_0**: It would mean that there should be some message x such that $D(E(x)) != x$, yes ?  
> **username_1**: In ZK proofs, the prover $P$ and the verifier $V$ have access to a common input $x$. Depending on the flavor of the ZK proof, various things are proven about $x$: (1) In a language-membership proof, $P$ proves that $x \in L$ for some language $L$. (2) In a proof of knowledge, $P$ proves the knowledge of some $w$ such that $(x,w) \in R$, where $R$ is typically an NP relation. (3) In a proof of ability, $P$ proves that for any $y$ chosen by $V$, he can find some $w$ such that some predicate $\pi(x,y,w)$ holds (this is my simplification).  
> **username_1**: (Cont'd) If $(E, D)$ is a public-key encryption scheme, then $E$ is made public, and can be used as the common input $x$ in a ZK proof of ability. Then, $P$ can prove in ZK, that for any $y=E(m)$, he can find some message $w$, such that $D(E(m))=w$ holds. If this is what you want, i.e., if $(E, D)$ is a public-key encryption scheme, I think I might be able to write an answer for your question. Otherwise, i.e., if $(E, D)$ is a secret-key encryption scheme, I can't imagine the context for a proof. That is, I don't know what the common input between $P$ and $V$ is.  
> **username_0**: @RickyDemer I'd want to prevent A and B from using the identity by positing that C should not be able to decrypt. I think Sadeq's distinction between PK and SK might be useful, and so let's assume that the encryption scheme is PK, and that E is public, and so the goal is to provide a ZK proof that decryption is possible.  
> **username_0**: @RobertRicci In retrospect, this question is more open-ended than I thought, so I'm flexible on how one defines it. I was thinking about it in a ZK way (i.e any information leakage of any kind is not permitted). so the latter would be a definite no-no.  
> **username_2**: I guess to prove that the protocol works they themselves should have a proof of this fact, simply having the protocol is not enough. And correctness of the protocol is not a finite statement and is not clear has a proof even in ZFC. So maybe you should put a restriction on the maximum size of input that the protocol works on. They you have two finite functions and you want to show that the composition of the two functions is identity without letting the adversary learn the functions.  
> **username_2**: It might be possible to modify the following simple protocol to become zero knowledge by adding some random string to the message before its encryption by A: Adv. selects and sends a message to A, A encrypts it and sends it to B, B decrypts it and sends it to Adv. ps: I think for it the goal to be possible the Adv. should be able to observe all interactions between A and B.  

---

## 2 answers

### Answer by username_3 on 2013-08-26. Score: 3

For symmetric-key encryption:

If Alice and Bob know a proof that $D\_K(E\_K(x))=x$ for all $x,K$, then they should be able to prove this fact in zero knowledge. In particular, they can produce boolean circuits for $D\_\cdot(\cdot)$ and $E\_\cdot(\cdot)$, publish a commitment to each boolean circuit, and then turn their proof into a zero-knowledge proof. In particular, verifying that $D\_K(E\_K(x))=x$ for all $x,K$ is in **co-NP**, and thus in **IP**, and there are zero-knowledge proofs for all of **IP** (and all of **PSPACE**).

Now if Alice wants to encrypt a message, she can give a zero-knowledge proof that she has encrypted some message correctly by doing the following: publish commitments $C(x),C(K)$ to her message $x$ and her key $K$; publish a commitment $C(y)$ to her ciphertext $y=E\_K(x)$; and now give a zero-knowledge proof that all the commitments are consistent (the ciphertext corresponding to $C(y)$ is a correct encryption, under the boolean circuit for encryption that was committed to earlier, under the key corresponding to $C(K)$ of the message corresponding to $C(x)$). Whether this is a useful thing to prove is another matter entirely -- it's not clear exactly what you are looking for or how you would use a solution to your problem, but hopefully this will give you some ideas.

For public-key encryption:

See Sadeq Dousti's comment. The exposition above can be readily adjusted to fit the public-key encryption setting, along the lines Sadeq Dousti suggests.


---

### Answer by username_1 on 2013-08-26. Score: 1

You can adapt the work of [Okamoto-Chaum-Ohta](http://link.springer.com/chapter/10.1007%2F3-540-46416-6_8) to this case. Let $P$ be the prover, $V$ the verifier, $E$ the public encryption key + algorithm (common input to $P$ and $V$), and $D$ the secret decryption key + algorithm (private input to $P$). We assume that $E$ can be probabilistic (to satisfy semantic security, it **has** to be), and therefore it uses some randomness to encrypt a message: $c = E(x ; r)$

Further, assume that $Com$ is a commitment scheme.

The protocol is as follows (in the first step, $P$ commits to a random string $u$ using randomness $\rho$):

1. $P \to V : Com(u ; \rho)$
2. $V \to P : c = E(x ; r)$
3. $P \to V : Dec(c) \oplus u$
4. $V \to P : x, r$
5. $P \to V : \rho$

The idea is that $P$ shows to $V$ that he can decrypt by committing to the decryption. However, he does not reveal the decryption until $V$ shows that he actually knows the plaintext.

Contrary to its simplicity, this protocol has lots of caveats. For instance, one can show that if $Com$ and $E$ are related in a *bizarre* way, the protocol is not zero-knowledge.
Another caveat is that if $E$ is in fact probabilistic, showing that the protocol is a proof of ability is very hard (if not impossible). However, if it is deterministic (say, merely a trapdoor one-way permutation), then the proof is rather easy. In any case, one can show that the protocol can be used for identification (in the smart-card model of Feige, Fiat, and Shamir).

> **Comments:**
> **username_1**: @RickyDemer: I assume that $D$ always succeeds in decryption, but assuming that it only fails with negligible probability will also do the job. The initial commitment has nothing to do with the ZK property; it is used to show that the protocol is actually a proof: The knowledge extractor (or, more precisely, the "ability extractor") uses this initial commitment to later extract $x$ from a prover $P^*$.  
> **username_1**: @RickyDemer: Yes, there are three interpretations for "for all $x$, D only fails with negligible probability," depending on what the probability is taken over: (1) only the randomness used by $D$, (2) the randomness used by $E$ and $D$, (3) the randomness used by $E$, $D$ and the key generation algorithm.  
> **username_1**: @RickyDemer: Yes, you fixed the public/private key, as well as the randomness used by $E$ (i.e., interpretation 1).  

---

