# Fiat–Shamir heuristic

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.

## Example

For the algorithm specified below, readers should be familiar with the multiplicative groups ${\displaystyle \mathbb {Z} _{q}^{*}}$ , where q is a prime number, and Euler's totient theorem on the Euler's totient function φ.

Here is an interactive proof of knowledge of a discrete logarithm in ${\displaystyle \mathbb {Z} _{q}^{*}}$ , based on Schnorr signature.[6] The public values are ${\displaystyle y\in \mathbb {Z} _{q}^{*}}$  and a generator g of ${\displaystyle \mathbb {Z} _{q}^{*}}$ , while the secret value is the discrete logarithm of y to the base g.

1. Lena wants to prove to Ole, the verifier, that she knows ${\displaystyle x}$  satisfying ${\displaystyle y\equiv g^{x}}$  without revealing ${\displaystyle x}$ .
2. Lena picks a random ${\displaystyle v\in \mathbb {Z} _{q}^{*}}$ , computes ${\displaystyle t=g^{v}}$  and sends ${\displaystyle t}$  to Ole.
3. Ole picks a random ${\displaystyle c\in \mathbb {Z} _{q}^{*}}$  and sends it to Lena.
4. Lena computes ${\displaystyle r=v-cx{\bmod {\varphi }}(q)}$  and returns ${\displaystyle r}$  to Ole.
5. Ole checks whether ${\displaystyle t\equiv g^{r}y^{c}}$ . This holds because ${\displaystyle g^{r}y^{c}\equiv g^{v-cx}g^{xc}\equiv g^{v}\equiv t}$  and ${\displaystyle g^{\varphi (q)}\equiv 1}$ .

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]

1. Lena wants to prove that she knows ${\displaystyle x}$  such that ${\displaystyle y\equiv g^{x}}$  without revealing ${\displaystyle x}$ .
2. Lena picks a random ${\displaystyle v\in \mathbb {Z} _{q}^{*}}$  and computes ${\displaystyle t=g^{v}}$ .
3. Lena computes ${\displaystyle c=H(g,y,t)}$ , where ${\displaystyle H}$  is a cryptographic hash function.
4. Lena computes ${\displaystyle r=v-cx{\bmod {\varphi }}(q)}$ . The resulting proof is the pair ${\displaystyle (t,r)}$ .
5. Anyone can use this proof to calculate ${\displaystyle c}$  and check whether ${\displaystyle t\equiv g^{r}y^{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 t 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]

7. ^ Bellare, Mihir; Rogaway, Phillip (1995). "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols". ACM Press: 62–73. CiteSeerX 10.1.1.50.3345. {{cite journal}}: Cite journal requires |journal= (help)