I'm new to zero-knowledge proof. Recently, I'm implementing a non-interactive zero-knowledge proof using the Schnorr scheme. I understand the non-interactive zero-knowledge proof needs random oracle for a prover to generate a proof along with a hash. Others suggested that I need to use Strong Fiat-Shamir to generate the hash.

Could you please give me some points about how to use and implement the strong Fiat-Shamir? What should be included in this Hash?


Quick remarks:

  • the Fiat-Shamir transform is implemented with a standard hash function (e.g. SHA-256 or SHA-3). Random oracles do not exist in the real world: it is only in the security analysis that the real hash function is modeled as a random oracle to get heuristic guarantees about its real-world security.
  • In most $\Sigma$-protocols (Schnorr included), the prover first generate a commitment (in Schnorr, this is something like $g^r$). Fiat-Shamir is then used to generate the verifier challenge non interactively by hashing something the prover has. Strong and weak Fiat-Shamir usually refer to the following alternatives: either the prover hashes only the commitment (e.g. $g^r$, this is the weak Fiat-Shamir - avoid it) or she hashes both the commitment and the statement (e.g. $(g^r || g^x)$ if you use Schnorr to prove knowledge of the discrete logarithm of $g^x$, this is the strong Fiat-Shamir - use it).

As for why these differences matters: in some scenarios (typically, when the prover can choose the statement adaptively in the larger context where the zero-knowledge proof is used), the weak Fiat-Shamir transform is provably insecure. This is discussed for example in this paper.

  • $\begingroup$ Thanks for your explanation. I think I basically understand it. Many thanks. $\endgroup$
    – Chao Liu
    Feb 1 at 19:23

Your Answer

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

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