1
$\begingroup$

I am currently reading the paper "A 2-round anonymous veto protocol" and have run into some trouble verifying the claims made about the zero knowledge proofs presented within. My knowledge of ZKPs is relatively elementary so I am looking for guidance as to where I may be going wrong in my understanding.

The relevant quote from the paper:

"Schnorr’s signature is a suitable choice because it is short, non-interactive, and reveals nothing except the one bit information about the truth of the statement: “the sender knows the discrete logarithm”. For example, let $H$ be a publicly known secure hash function. To prove the knowledge of the exponent for $g^{x_i}$, one can send {$g^v, r = v − x_i h$} where $v \in_R \mathbb{Z}_q$ and $h = H(g, g^v , g^{x_i},$ $i)$. This signature can be verified by anyone through checking whether $g^v$ and $g^r g^{x_i h}$ are equal."

It seems straightforward to forge a counterfeit proof for this scheme without having explicit knowledge of $x_i$. E.g. let $r\in_R \mathbb{Z}_q$, we can construct a "proof" {$g^v, r$} by taking $g^v = g^r(g^{x_i})^h = g^r g^{x_i h}$ despite not knowing the value of $v$ or $x_i$. It is easy to see this counterfeit proof will be accepted by a third party verifier based on the check proposed in the quoted section.

My question is: Is my understanding here correct? If not, what is the mistake I'm making?

(N.B. Reading this paper is part of an effort I'm making to read several other papers on similar topics, and I noticed in "SEAL: Sealed-Bid Auction without Auctioneers" a similar technique to the one I described in this question to construct a counterfeit proof is used to compute the "simulated" proofs for the false clauses in the more hefty one-out-of-$n$ proof schemes provided in the paper's appendix. This raises the further question: why can't this technique be used to just create synthetic (i.e. counterfeit) proofs for all the statements ZKPs are required for? Obviously, this would render the ZKP system here totally useless.)

$\endgroup$

1 Answer 1

1
$\begingroup$

E.g. let $r\in_R \mathbb{Z}_q$, we can construct a "proof" {$g^v, r$} by taking $g^v = g^r(g^{x_i})^h = g^r g^{x_i h}$ despite not knowing the value of $v$ or $x_i$.

That doesn't work. What value do you use for $h$?

Remember, $h$ is computed as $h = H(g, g^v , g^{x_i})$, that is, it depends on $g^v$ and you haven't selected the value for $g^v$ yet.

Selecting $r$ and $g^v$ first also doesn't work - you can then compute $h$, but then the value $g^v$ you selected is unlikely to happen to be $g^r(g^{x_i})^h$

Thirdly, we could try selecting $g^v$ first, computing $h$, and then computing the value $g^r = g^v(g^{x_i})^{-h}$, which would make the relation work, however the signature requires us to supply the value of $r$, and recovering that would require us to compute a discrete log.

$\endgroup$

Your Answer

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

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