Score:2

Pedersen Commitment and Computational Zero Knowledge

yt flag

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?

Score:2
cn flag

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.

Sean avatar
yt flag
Great. Thanks for the clarification.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.