For this background, the prover knows a secret $x$ for $h=gx$. Prove to the verifier that he knows $x$.

(I know $h=gx$ is not a NP problem, I just want to practice the Sigma Protocol)

Step 1 : $P \rightarrow V $ $$r \leftarrow Z$$ $$u = g^r \bmod p$$ Send $u$ to Verifier

Step 2 : $V \rightarrow P$ $$t \leftarrow Z$$ Select a random $t$ as a challenge, and send $t$ to Prover.

Step 3 : $P \rightarrow V$

Prover creates a response back to Verifier,

$$z = g^{t-r} x^t$$

Send $z$ to Verifier,

Step 4 Verifier verify the result by checking $h^t = zu$

Here is the proof,

$$h^t = zu$$ For $z = g^{t-r}x^t$ $$h^t = ug^{t-r}x^t$$ $$h^t g^r = u g^t x^t$$ For $u=g^r$ $$h^t u = u g^t x^t$$ $$u h^t = u (gx)^t$$ $$u h^t = u h^t$$

Am I doing it correctly?

Does it mean for any NP problem, I can use Sigma-protocol to construct the zero-knowledge proof?


Your Answer

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

Browse other questions tagged or ask your own question.