How to construct a strong Fiat-Shamir in zero-knowledge proof?

Question

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?

Answer 1

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.