Fiat-Shamir Heuristic

Example

For the algorithm specified below, readers should be familiar with the laws of modular arithmetic, especially with multiplicative groups of integers modulo n with prime n.

Here is an interactive proof of knowledge of a discrete logarithm.<ref>Template:Cite journal</ref>

1. Peggy wants to prove to Victor the verifier that she knows \(x\): the discrete logarithm of \(y = g^x\) to the base \(g\) (mod n).
2. She picks a random \(v\in \Z^*_q\), computes \(t = g^v\) and sends \(t\) to Victor.
3. Victor picks a random \(c\in \Z^*_q\) and sends it to Peggy.
4. Peggy computes \(r = v - cx\) and returns \(r\) to Victor.
5. He checks whether \(t \equiv g^ry^c\). This holds because \(g^ry^c = g^{v - cx}g^{xc} = g^v = t\).

Fiat–Shamir heuristic allows to replace the interactive step 3 with a non-interactive random oracle access. In practice, we can use a cryptographic hash function instead.<ref>Template:Cite journal</ref>

1. Peggy wants to prove that she knows \(x\): the discrete logarithm of \(y = g^x\) to the base \(g\).
2. She picks a random \(v\in\Z^*_q\) and computes \(t = g^v\).
3. Peggy computes \(c = H(g,y,t)\), where \(H()\) is a cryptographic hash function.
4. She computes \(r = v - cx\). The resulting proof is the pair \((t,r)\). As \(r\) is an exponent of \(g\), it is calculated modulo \(q-1\), not modulo \(q\).
5. Anyone can check whether \(t \equiv g^ry^c\).

If the hash value used below does not depend on the (public) value of y, the security of the scheme is weakened, as a malicious prover can then select a certain value x so that the product cx is known.<ref>Template:Cite book</ref>