4
$\begingroup$

I'm reading about the Schnorr's zero-knowledge proof for DLOG and the Sigma protocol for DH tuple proof, and I want to know how one applies Fiat-Shamir transform to both of them, to turn them into NIZK proofs.

enter image description here

enter image description here

I know that Prover would need to hash some public parameters to get the challenge, and then compute a proof for that challenge, so that the Verifier can also compute the same challenge using the hash from the public values, and can verify the proof, and there is no interaction between them. But, which of the public parameters one needs to hash to get a challenge? More precisely, how does the challenge look in NIZK proof, and is the proving and verification steps left the same? Also is the security guaranteed due to the random oracle model and usage of hash functions or there is something else going on in the NIZK proofs?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The idea is that the hash function replaces the random pick of the verifier at step 2. So you must hash the public statement ($h$ for protocol 6.1.1, $(u,v)$ for protocol 6.2.2) with the commitment sent by the prover at step one ($a$ for protocol 6.1.1, $(a,b)$ for protocol 6.2.2).

The prover cannot guess the challenge $e$ before he generates the commitment $a$, because the commitment is used to generate the challenge. The intuition is that since the random oracle act as an honest verifier, it is equivalent to interact with an honest player or with the random oracle. There is no other change.

If the prover hashes only the public parameter, then he can choose the challenge $e$ before he generates the commitment $a$. For instance, in protocol 6.1.1, the prover can forge a proof $(a,z)$ such that $g^z=ah^e$ by computing $e=H(h)$, choosing $z$ at random and computing $a=g^z / h^e$.

On the other hand, hashing the public parameters prevent the attacks where an adversary has access to a proof oracle that forges proofs for chosen statements. For instance, for any chosen $x$, knowing a proof $(a=g^r,z=r+H(a)w)$ for the statement $h'=hg^x=g^{w+x}$ (where the statement is not used in the hash) for the non-interactive version of protocol 6.1.1, you can forge a proof $(a, z + H(a)x = r+H(a)(w+x))$ for the statement $h$.

Finally, the non-interactive proof for protocol 6.1.1 can be defined as follows:

  1. chose $r$ and compute $a=g^r$

  2. compute $e=H(a||h),$ where $H$ is a hash function and $||$ denotes the concatenation.

  3. compute $z=r + ew$

  4. return the proof $(a,z)$

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Note that you can do this more communication efficiently by sending $(e,z)$ and then having the verifier compute $a = g^z/h^e$, hash the result (with the statement), and compare to $e$. This is slightly more communication efficient for DLOG and significantly more communication efficient for DH tuples. $\endgroup$
    – Yehuda Lindell
    Nov 21, 2018 at 6:24

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.