3
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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, 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). For more info on the use of the KEA in constructing non-black-box ZK, see [Hada and Tanaka] and the more recent [Bellare and Palacio].

--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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Cyker
    Commented Jun 5, 2011 at 11:31
  • 2
    $\begingroup$ @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. $\endgroup$
    – Sadeq Dousti
    Commented Jun 5, 2011 at 19:04
  • $\begingroup$ 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. $\endgroup$
    – Dave
    Commented Jul 10, 2011 at 7:00
  • $\begingroup$ @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). $\endgroup$
    – Sadeq Dousti
    Commented Jul 10, 2011 at 8:15
  • $\begingroup$ @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. $\endgroup$
    – Dave
    Commented Jul 10, 2011 at 16:55
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.