# Fiat–Shamir heuristic

Jump to navigation Jump to search

The Fiat–Shamir heuristic is a technique in cryptography 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 number secret to the public) can be proven without revealing underlying information. The technique is due to Fiat and Shamir (1986). The original interactive proof must have the property of being public-coin, for the method to work. For the algorithm specified below, a reader should be familiar with the laws of modular arithmetic, especially with multiplicative groups of integers modulo n with prime n.

The heuristic was originally presented without a proof of security; later, Pointcheval and Stern  proved its security against chosen message attacks in the random oracle model, that is, under the assumption that random oracles exist. In the case that random oracles don't exist, the Fiat–Shamir heuristic has been proven insecure by Shafi Goldwasser and Yael Tauman Kalai. The Fiat–Shamir heuristic thus demonstrates a major application of random oracles. 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.

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 an identification protocol, then the non-interactive version can be used directly as a digital signature.

## Example

Here is an interactive proof of knowledge of a discrete logarithm.

1. Peggy wants to prove to Victor the verifier that she knows $x$ : the discrete logarithm of $y=g^{x}$ to the base $g$ .
2. She picks a random $v\in \mathbb {Z} _{q}^{*}$ , computes $t=g^{v}$ and sends $t$ to Victor.
3. Victor picks a random $c\in \mathbb {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^{r}y^{c}$ . This holds because $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.

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 \mathbb {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^{r}y^{c}$ .

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