Fiat-Shamir Heuristic

The Fiat–Shamir heuristic is a technique for taking an Interactive Proof of Knowledge and creating a digital signature based on it.

Example

Interactive Version

We have a 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\).

Non-Interactive Version

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>

Relevant papers

It was first introduced in a paper by Amos Fiat and Adi Shamir (1986).<ref>Template:Cite journal</ref>.

Assumptions

1. The first assumption is that the original interactive proof must be public coin
2. The second assumption is the existence of Random Oracles i.e. the heuristic only holds in the Random Oracle Model

References

<references/>