Score:1

Is it possible to forge valid proofs in this Schnorr signature-based ZKP system for proving knowledge about discrete logarithms?

pl flag

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

Score:1
my flag

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.

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.