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.

Overview

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.^[6]

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.^[7] 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.^[8]

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.^[9]

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

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

References

1. Fiat, Amos; Shamir, Adi (1987). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Vol. 263. Springer Berlin Heidelberg. pp. 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0.
2. Pointcheval, David; Stern, Jacques (1996). "Security Proofs for Signature Schemes". Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. Vol. 1070. Springer Berlin Heidelberg. pp. 387–398. doi:10.1007/3-540-68339-9_33. ISBN 978-3-540-61186-8.
3. Don, Jelle; Fehr, Serge; Majenz, Christian; Schaffner, Christian (2019). "Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model". Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. Vol. 11693. Springer Cham. pp. 356–383. arXiv:1902.07556. Bibcode:2019arXiv190207556D. doi:10.1007/978-3-030-26951-7_13. ISBN 978-3-030-26950-0. S2CID 67769879.
4. Liu, Qipeng; Zhandry, Mark (2019). "Revisiting Post-quantum Fiat-Shamir". Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. Vol. 11693. Springer Cham. pp. 326–355. doi:10.1007/978-3-030-26951-7_12. ISBN 978-3-030-26950-0. S2CID 75135227.
5. Goldwasser, S.; Kalai, Y. T. (October 2003). "On the (In)security of the Fiat-Shamir paradigm". 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp. 102–113. doi:10.1109/SFCS.2003.1238185. ISBN 0-7695-2040-5. S2CID 295289.
6. "Inserting electronic signature to Word document". Retrieved 2025-02-16.
7. Camenisch, Jan; Stadler, Markus (1997). "Proof Systems for General Statements about Discrete Logarithms" (PDF). Dept. Of Computer Science, ETH Zurich. Archived from the original (PDF) on 2020-08-17.
8. Bellare, Mihir; Rogaway, Phillip (1995), Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Press, pp. 62–73, CiteSeerX 10.1.1.50.3345
9. Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios" (PDF). In Wang, Xiaoyun; Sako, Kazue (eds.). Advances in Cryptology – ASIACRYPT 2012. pp. 626–643.|https://eprint.iacr.org/2016/771.pdf