# Fiat-Shamir heuristic

###### tags: `Templates` `Book` `Ethereum` `Math` `Computer Science`

In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact (for example, knowledge of a certain secret number) can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986).[1] For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.

The heuristic was originally presented without a proof of security; later, Pointcheval and Stern[2] proved its security against chosen message attacks in the random oracle model, that is, assuming random oracles exist. This result was generalized to the quantum-accessible random oracle (QROM) by Don, Fehr, Majenz and Schaffner,[3] and concurrently by Liu and Zhandry.[4] In the case that random oracles do not exist, the Fiat–Shamir heuristic has been proven insecure by Shafi Goldwasser and Yael Tauman Kalai.[5] The Fiat–Shamir heuristic thus demonstrates a major application of random oracles. More generally, the Fiat–Shamir heuristic may also be viewed as converting a public-coin interactive proof of knowledge into a non-interactive proof of knowledge. If the interactive proof is used as an identification tool, then the non-interactive version can be used directly as a digital signature by using the message as part of the input to the random oracle.

## Examples

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 q.

Here is an interactive proof of knowledge of a discrete logarithm.[6]

Peggy wants to prove to Victor the verifier that she knows {\displaystyle x}x: the discrete logarithm of {\displaystyle y=g^{x}}y=g^{x} to the base {\displaystyle g}g (mod n).
She picks a random {\displaystyle v\in \mathbb {Z} _{q}^{*}}{\displaystyle v\in \mathbb {Z} _{q}^{*}}, computes {\displaystyle t=g^{v}}t=g^{v} and sends {\displaystyle t}t to Victor.
Victor picks a random {\displaystyle c\in \mathbb {Z} _{q}^{*}}c\in \mathbb{Z } _{q}^{*} and sends it to Peggy.
Peggy computes {\displaystyle r=v-cx{\bmod {\lambda }}(q)}{\displaystyle r=v-cx{\bmod {\lambda }}(q)} and returns {\displaystyle r}r to Victor.
He checks whether {\displaystyle t\equiv g^{r}y^{c}}t\equiv g^{r}y^{c}. This holds because {\displaystyle g^{r}y^{c}=g^{v-cx}g^{xc}=g^{v}=t}g^{r}y^{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.[7]

Peggy wants to prove that she knows {\displaystyle x}x: the discrete logarithm of {\displaystyle y=g^{x}}y=g^{x} to the base {\displaystyle g}g.
She picks a random {\displaystyle v\in \mathbb {Z} _{q}^{*}}{\displaystyle v\in \mathbb {Z} _{q}^{*}} and computes {\displaystyle t=g^{v}}t=g^{v}.
Peggy computes {\displaystyle c=H(g,y,t)}c=H(g,y,t), where {\displaystyle H()}H() is a cryptographic hash function.
She computes {\displaystyle r=v-cx{\bmod {\lambda }}(q)}{\displaystyle r=v-cx{\bmod {\lambda }}(q)}. The resulting proof is the pair {\displaystyle (t,r)}(t,r).
Anyone can use this proof to calculate {\displaystyle c}c and check whether {\displaystyle t\equiv g^{r}y^{c}}t\equiv g^{r}y^{c}.
As {\displaystyle r}r is an exponent of {\displaystyle g}g and we're using cyclic groups with order {\displaystyle q}q, it can be calculated modulo {\displaystyle \lambda (q)}{\displaystyle \lambda (q)}, not modulo {\displaystyle q}q. {\displaystyle \lambda (q)}{\displaystyle \lambda (q)} is {\displaystyle q-1}q-1 in the case when {\displaystyle q}q is prime order of group.

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 y so that the product cx is known.[8]

## Extension of this method

As long as a fixed random generator can be constructed with the data known to both parties, then any interactive protocol can be transformed into a non-interactive one.[citation needed]

## See more

- [Random oracle model](https://en.wikipedia.org/wiki/Random_oracle_model)
- [Non-interactive zero-knowledge proof](https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof)
- an application in [anonymous veto network](https://en.wikipedia.org/wiki/Anonymous_veto_network)
- [Forking lemma](https://en.wikipedia.org/wiki/Forking_lemma)

## References
- https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic