<p>First, I think the CCA-security is not enough, and the encryption scheme must be at least IND-CCA2-secure.</p>

<p>Second, I believe the protocol is not zero-knowledge, at least in the auxiliary-input model. The reasoning is as follows: Let z be the auxiliary input to the malicious verifier V*. It's safe to assume that $z = Enc_{p_k}(m)$, where m is unknown to V*. Then, V* can deviate from the original protocol: Instead of choosing a random m and computing c (as prescribed in the protocol), she lets c = z, and sends c to the prover. This way, V* exploits P as a "decryption oracle," and obtains knowledge beyond what she could possibly compute.</p>

<p>One piece of advice: Read the paper <a href="http://www.springerlink.com/content/pecu04f221rn4p0r/" rel="nofollow">Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks</a>, specially section 4. It suggests a protocol similar to yours; one which has never been realized. It also proposes the now-famous "knowledge-of-exponent" assumption (KEA), one which was later used to construct a non-black-box ZK protocol. (The reason why you can't find a simulator, beyond the line of reasoning above, is that you try to imagine a black-box simulator. That's impossible by the result of <a href="http://dx.doi.org/10.1137/S0097539791220688" rel="nofollow">Goldreich and Krawczyk</a>). For more info on the use of the KEA in constructing non-black-box ZK, see [<a href="http://eprint.iacr.org/1999/009.ps.gz" rel="nofollow">Hada and Tanaka</a>] and the more recent [<a href="http://cseweb.ucsd.edu/~mihir/papers/eka.ps" rel="nofollow">Bellare and Palacio</a>].</p>

<p><strong>--Edit--</strong> @cyker: I'm working on a similar issue as (presumably) you're doing: The (right) definition of simulators. A partial result of mine, closely related to the protocol you offered, can be found at <a href="http://eprint.iacr.org/2010/150" rel="nofollow">http://eprint.iacr.org/2010/150</a>. The latest results are submitted but not published online yet.</p>

CC BY-SA 3.0
2011-06-05T11:31:33.667Z
Thanks, but I'm still a bit confused that, in the classic quadratic residue ZK proof system ([GMR89]), the verifier also learns something she didn't know before: the square root of some quadratic residue. So why is this proof system recognized as ZK? Why isn't the square root regared as additional knowledge?
Cyker
CC BY-SA 3.0
2011-06-05T19:04:45.630Z
@cyker: In the proof of the quadratic residuosity, the verifier learns nothing beyond a *random* root of some *random* number, something that she can find by herself (this is shown via simulation). V* can never find the root of her *desired* number. In other words, P does not act as a **root-finding oracle** for V*. This is in sharp contrast to the protocol you suggested.
Sadeq Dousti
CC BY-SA 3.0
2011-07-10T07:00:08.150Z
The prover would only have to answer with a few of the bits in the decrypted string to make the proof work, not the entire string. The prover could also ask the verifier to supply some of the bits from the string it encrypted to check that it really knows what string was encrypted. These changes should get around the problem Sadeq pointed out.
Dave
CC BY-SA 3.0
2011-07-10T08:15:15.737Z
@Dave: "only have to answer with a few of the bits...": Unless the number of "answer" bits is superlogarithmic in the security parameter, the proof won't provide enough confidence for the verifier; i.e. the soundness error won't be negligibly small (where a quantity is called negligible if it vanishes faster than the reciprocal of any positive polynomial).
Sadeq Dousti
CC BY-SA 3.0
2011-07-10T16:55:24.283Z
@Sadeq: A constant fraction of the number of bits in the string should do the trick. The verifier would only learn anything with negligible probability if it is also required to send a constant fraction of the bits in the string along with its encryption to prove it knows what the string is.
Dave
CC BY-SA 3.0
2011-07-10T22:47:54.197Z
@Dave: A constant fraction of bits does not harm ZK, rather, it hurts soundness: say V checks just 10 bits. The soundness error will be $2^{-10}$. This is by no means enough for security purposes; since in crypto, we need the error to be negligibly small in security parameter (say, $2^{-n}$).
Sadeq Dousti
CC BY-SA 3.0
2011-07-11T15:26:48.717Z
@Sadeq: By a constant fraction of the bits, I meant something like $n/2$ of the $n$ bits (giving an error probability exponentially small in $n$), not $10$ bits. Perhaps a better solution would be to have the prover commit to an answer, then show the committed answer after the verifier reveals his answer. This leaves the error probability at $2^{-n}$.
Dave
CC BY-SA 3.0
2011-06-05T10:32:09.633Z
2011-06-06T07:11:14.493Z
2011-06-06T07:11:14.493Z
Sadeq Dousti
<p>This protocol is "honest-verifier" ZK, just like the classic two-move graph isomorphism protocol:  The simulator (acting on behalf of the honest verifier) picks m at random, encrypts it, and then "simulates" sending m back to itself.</p>

<p>However, just like with all known ZK protocols, to get the ZK property to hold against cheating verifiers, one has to some kind of simulation trick.  A typical such trick is to have the verifier provide some kind of proof of knowledge of the message m, that the simulator could "break" and use to extract the message m.</p>

CC BY-SA 3.0
2011-07-10T05:56:42.280Z
2011-07-10T05:56:42.280Z
ZK-man
<p>Say there's a public encryption scheme whose public key is $p_k$ and secret key is $s_k$. Prover $P$ wants to convince verifier $V$ that he knows $s_k$. The protocol is:</p>

<ol>
<li>$V$ uniformly generates $m$ and sends $c = Enc_{p_k}(m)$ to $P$</li>
<li>$P$, receiving $c$, sends $m&#39; = Dec_{s_k}(c)$ to $V$</li>
<li>$V$ checks whether $m = m&#39;$. If so, accept. Else, reject.</li>
</ol>

<p>Completeness and soundness are obvious. Intuitively decryption shouldn't leak information about the secret key $s_k$ if this scheme is CCA-secure. But I just haven't come up with a proper simulator to argue this. If $V$ cheats, it's hard to get the correct plaintext without knowledge of $s_k$. If the simulator just guess, the probability is so low that exponentially many rounds are required. So the question is:</p>

<p>Is this protocol really zero knowledge? If so, how to construct the simulator?</p>

<cr.crypto-security><zero-knowledge>
Zero knowledgeness of a simple protocol
Cyker
# Zero knowledgeness of a simple protocol

(Asked by: username_0 on 2011-06-05)

Say there's a public encryption scheme whose public key is $p\_k$ and secret key is $s\_k$. Prover $P$ wants to convince verifier $V$ that he knows $s\_k$. The protocol is:

1. $V$ uniformly generates $m$ and sends $c = Enc\_{p\_k}(m)$ to $P$
2. $P$, receiving $c$, sends $m' = Dec\_{s\_k}(c)$ to $V$
3. $V$ checks whether $m = m'$. If so, accept. Else, reject.

Completeness and soundness are obvious. Intuitively decryption shouldn't leak information about the secret key $s\_k$ if this scheme is CCA-secure. But I just haven't come up with a proper simulator to argue this. If $V$ cheats, it's hard to get the correct plaintext without knowledge of $s\_k$. If the simulator just guess, the probability is so low that exponentially many rounds are required. So the question is:

Is this protocol really zero knowledge? If so, how to construct the simulator?

**Tags:** cr.crypto-security, zero-knowledge


---

## 2 answers

### Answer by username_1 on 2011-06-05. Score: 6 | Accepted answer

First, I think the CCA-security is not enough, and the encryption scheme must be at least IND-CCA2-secure.

Second, I believe the protocol is not zero-knowledge, at least in the auxiliary-input model. The reasoning is as follows: Let z be the auxiliary input to the malicious verifier V\*. It's safe to assume that $z = Enc\_{p\_k}(m)$, where m is unknown to V\*. Then, V\* can deviate from the original protocol: Instead of choosing a random m and computing c (as prescribed in the protocol), she lets c = z, and sends c to the prover. This way, V\* exploits P as a "decryption oracle," and obtains knowledge beyond what she could possibly compute.

One piece of advice: Read the paper [Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks](http://www.springerlink.com/content/pecu04f221rn4p0r/), specially section 4. It suggests a protocol similar to yours; one which has never been realized. It also proposes the now-famous "knowledge-of-exponent" assumption (KEA), one which was later used to construct a non-black-box ZK protocol. (The reason why you can't find a simulator, beyond the line of reasoning above, is that you try to imagine a black-box simulator. That's impossible by the result of [Goldreich and Krawczyk](http://dx.doi.org/10.1137/S0097539791220688)). For more info on the use of the KEA in constructing non-black-box ZK, see [[Hada and Tanaka](http://eprint.iacr.org/1999/009.ps.gz)] and the more recent [[Bellare and Palacio](http://cseweb.ucsd.edu/~mihir/papers/eka.ps)].

**--Edit--** @cyker: I'm working on a similar issue as (presumably) you're doing: The (right) definition of simulators. A partial result of mine, closely related to the protocol you offered, can be found at <http://eprint.iacr.org/2010/150>. The latest results are submitted but not published online yet.

> **Comments:**
> **username_0**: Thanks, but I'm still a bit confused that, in the classic quadratic residue ZK proof system ([GMR89]), the verifier also learns something she didn't know before: the square root of some quadratic residue. So why is this proof system recognized as ZK? Why isn't the square root regared as additional knowledge?  
> **username_1**: @cyker: In the proof of the quadratic residuosity, the verifier learns nothing beyond a *random* root of some *random* number, something that she can find by herself (this is shown via simulation). V* can never find the root of her *desired* number. In other words, P does not act as a **root-finding oracle** for V*. This is in sharp contrast to the protocol you suggested.  
> **username_2**: The prover would only have to answer with a few of the bits in the decrypted string to make the proof work, not the entire string. The prover could also ask the verifier to supply some of the bits from the string it encrypted to check that it really knows what string was encrypted. These changes should get around the problem Sadeq pointed out.  
> **username_1**: @username_2: "only have to answer with a few of the bits...": Unless the number of "answer" bits is superlogarithmic in the security parameter, the proof won't provide enough confidence for the verifier; i.e. the soundness error won't be negligibly small (where a quantity is called negligible if it vanishes faster than the reciprocal of any positive polynomial).  
> **username_2**: @Sadeq: A constant fraction of the number of bits in the string should do the trick. The verifier would only learn anything with negligible probability if it is also required to send a constant fraction of the bits in the string along with its encryption to prove it knows what the string is.  
> **username_1**: @username_2: A constant fraction of bits does not harm ZK, rather, it hurts soundness: say V checks just 10 bits. The soundness error will be $2^{-10}$. This is by no means enough for security purposes; since in crypto, we need the error to be negligibly small in security parameter (say, $2^{-n}$).  
> **username_2**: @Sadeq: By a constant fraction of the bits, I meant something like $n/2$ of the $n$ bits (giving an error probability exponentially small in $n$), not $10$ bits. Perhaps a better solution would be to have the prover commit to an answer, then show the committed answer after the verifier reveals his answer. This leaves the error probability at $2^{-n}$.  

---

### Answer by username_3 on 2011-07-10. Score: 1

This protocol is "honest-verifier" ZK, just like the classic two-move graph isomorphism protocol: The simulator (acting on behalf of the honest verifier) picks m at random, encrypts it, and then "simulates" sending m back to itself.

However, just like with all known ZK protocols, to get the ZK property to hold against cheating verifiers, one has to some kind of simulation trick. A typical such trick is to have the verifier provide some kind of proof of knowledge of the message m, that the simulator could "break" and use to extract the message m.


---

