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.
Here is an interactive proof of knowledge of a discrete logarithm in
, based on
Schnorr signature.[6] The public values are
and a generator g of
, while the secret value is the discrete logarithm of y to the base g.
Lena wants to prove to Ole, the verifier, that she knows satisfying without revealing .
Lena picks a random , computes and sends to Ole.
Ole picks a random and sends it to Lena.
Lena computes and returns to Ole.
Ole checks whether . This holds because and .
Fiat–Shamir heuristic allows to replace the interactive step 3 with a non-interactiverandom oracle access. In practice, we can use a
cryptographic hash function instead.[7]
Lena wants to prove that she knows such that without revealing .
Lena picks a random and computes .
Lena computes , where is a cryptographic hash function.
Lena computes . The resulting proof is the pair .
Anyone can use this proof to calculate and check whether .
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]
^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.
ISBN978-3-540-18047-0.
^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.
ISBN978-3-540-61186-8.
^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.
ISBN978-3-030-26950-0.
S2CID75135227.
^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.
ISBN0-7695-2040-5.
S2CID295289.