2
$\begingroup$

I am curious at how "good" is computational zero knowledge? Consider Pedersen Commitment $z = g^x h^y$. There exists perfect ZK protocol (based on Schnorr's) to prove that one knows the secret $x$ and $y$. But how about the following "relaxed" one:

(1) The prover sends $G = g^x$ and $H = h^y$ (and the verifier needs to verify $G\times H = z$); (2) The prover runs two instance of Schnorr's protocol to prove that she knows the logarithm of $G$ and $H$

It seems that this protocol is computational ZK, as the simulator could simply pick a random pair ($G'$, $H'$) such that $G' \times H' = z$. Since $(G',H')$ would be indistinguishable from the real $(G,H)$, then the simulator's conversation will be indistinguishable from the real ones (computationally). [Can you verify that this claim is correct? Thanks!]

But then the protocol indeed leaks something - as an example, think about the case where $x=1$. The pedersen commitment then loses its perfect hiding here.

So the question is: when computational ZK is used, is it regarded as satisfactory (if used alone?) Should some additional properties such as witness indistinguisability be required?

$\endgroup$
2
$\begingroup$

The protocol is not computationally zero-knowledge. Computational ZK is satisfactory even when "used alone", and in particular implies (computational) witness indistinguishability.

The mistake is in the sentence

It seems that this protocol is computational ZK, as the simulator could simply pick a random pair ($G'$, $H'$) such that $G' \times H' = z$. Since $(G',H')$ would be indistinguishable from the real $(G,H)$, then the simulator's conversation will be indistinguishable from the real ones (computationally).

The simulator can indeed pick $(G',H')$ at random conditioned on $G'H' = z$, but this is not indistinguishable from the real $(G,H)$ in general. Recall that $z$ (the Pedersen commitment) is the word: no assumption is made about its distribution. Taking the same example as in your question, when $x=1$, then the real protocol communicates $(g^x, h^y) = (g, h^y)$. On the other hand, the simulator communicates a random $G'$ instead of $g$, which can be easily distinguished from the honest protocol.

$\endgroup$
1
  • $\begingroup$ Great. Thanks for the clarification. $\endgroup$
    – Sean
    Jul 5 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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