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 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]

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

1. Peggy wants to prove that she knows ${\displaystyle x}$: the discrete logarithm of ${\displaystyle y=g^{x}}$ to the base ${\displaystyle g}$.
2. She picks a random ${\displaystyle v\in \mathbb {Z} _{q}^{*}}$ and computes ${\displaystyle t=g^{v}}$.
3. Peggy computes ${\displaystyle c=H(g,y,t)}$, where ${\displaystyle H()}$ is a cryptographic hash function.
4. She computes ${\displaystyle r=v-cx{\bmod {\lambda }}(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}}$.

As ${\displaystyle r}$ is an exponent of ${\displaystyle g}$ and we're using cyclic groups with order ${\displaystyle q}$, it can be calculated modulo ${\displaystyle \lambda (q)}$, not modulo ${\displaystyle q}$. ${\displaystyle \lambda (q)}$ is ${\displaystyle q-1}$ in the case when ${\displaystyle 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 x 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 also[]

• Random oracle model
• Non-interactive zero-knowledge proof
• an application in anonymous veto network
• Forking lemma

References[]