Fiat–Shamir heuristic

The heuristic was originally presented without a proof of security; later, Pointcheval and Stern{{cite book |last1=Pointcheval |first1=David |last2=Stern |first2=Jacques |title=Advances in Cryptology — EUROCRYPT '96 |chapter=Security Proofs for Signature Schemes |volume=1070 |date=1996 |pages=387–398 |doi=10.1007/3-540-68339-9_33 |publisher=Springer Berlin Heidelberg |language=en|series=Lecture Notes in Computer Science |isbn=978-3-540-61186-8 |doi-access=free }} 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,{{cite book |last1=Don |first1=Jelle |last2=Fehr |first2=Serge|last3=Majenz |first3=Christian |last4=Schaffner |first4=Christian|title=Advances in Cryptology – CRYPTO 2019 |chapter=Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model |volume=11693 |pages=356–383 |date=2019 |doi=10.1007/978-3-030-26951-7_13 |publisher=Springer Cham|language=en|series=Lecture Notes in Computer Science |isbn=978-3-030-26950-0 |bibcode=2019arXiv190207556D |arxiv=1902.07556 |s2cid=67769879 }} and concurrently by Liu and Zhandry.{{cite book |last1=Liu |first1=Qipeng |last2=Zhandry |first2=Mark|title=Advances in Cryptology – CRYPTO 2019 |chapter=Revisiting Post-quantum Fiat-Shamir |volume=11693 |pages=326–355 |date=2019 |doi=10.1007/978-3-030-26951-7_12 |publisher=Springer Cham|language=en|series=Lecture Notes in Computer Science |isbn=978-3-030-26950-0 |s2cid=75135227 }} In the case that random oracles do not exist, the Fiat–Shamir heuristic has been proven insecure by Shafi Goldwasser and Yael Tauman Kalai.{{cite book |last1=Goldwasser |first1=S. |last2=Kalai |first2=Y. T. |title=44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. |chapter=On the (In)security of the Fiat-Shamir paradigm |date=October 2003 |pages=102–113 |doi=10.1109/SFCS.2003.1238185 |isbn=0-7695-2040-5 |s2cid=295289 }} 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.{{Cite web |title=Inserting electronic signature to Word document |url=https://signmydocument.com/blog/how-to-insert-esignature-to-word |access-date=2025-02-16}}

For the algorithm specified below, readers should be familiar with the multiplicative groups $\backslash 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 $\backslash Z^*\_q$, based on Schnorr signature.{{cite journal |last1=Camenisch |first1=Jan |last2=Stadler |first2=Markus |title=Proof Systems for General Statements about Discrete Logarithms |journal=Dept. Of Computer Science, ETH Zurich |date=1997 |url=ftp://ftp.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf |archive-url=https://web.archive.org/web/20200817160710/ftp://ftp.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf|url-status=dead|archive-date=2020-08-17}} The public values are $y\; \backslash in\; \backslash Z^*\_q$ and a generator g of $\backslash 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 $x$ satisfying $y\; \backslash equiv\; g^x$ without revealing $x$.
2. Lena picks a random $v\backslash in\; \backslash Z^*\_q$, computes $t\; =\; g^v$ and sends $t$ to Ole.
3. Ole picks a random $c\backslash in\; \backslash Z^*\_q$ and sends it to Lena.
4. Lena computes $r\; =\; v\; -\; cx\; \backslash bmod\; \backslash varphi(q)$ and returns $r$ to Ole.
5. Ole checks whether $t\; \backslash equiv\; g^ry^c$. This holds because $g^ry^c\; \backslash equiv\; g^\{v\; -\; cx\}g^\{xc\}\; \backslash equiv\; g^v\; \backslash equiv\; t$ and $g^\{\backslash varphi(q)\}\; \backslash 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.{{cite |last1=Bellare |first1=Mihir |last2=Rogaway |first2=Phillip |title=Random Oracles are Practical: A Paradigm for Designing Efficient Protocols |date=1995 |pages=62–73 |publisher=ACM Press|citeseerx=10.1.1.50.3345 }}

1. Lena wants to prove that she knows $x$ such that $y\; \backslash equiv\; g^x$ without revealing $x$.
2. Lena picks a random $v\backslash in\backslash Z^*\_q$ and computes $t\; =\; g^v$.
3. Lena computes $c\; =\; H(g,y,t)$, where $H$ is a cryptographic hash function.
4. Lena computes $r\; =\; v\; -\; cx\; \backslash bmod\; \backslash varphi(q)$. The resulting proof is the pair $(t,r)$.
5. Anyone can use this proof to calculate $c$ and check whether $t\; \backslash equiv\; g^ry^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.{{cite book|editor-first1=Xiaoyun|editor-last1=Wang|editor-first2=Kazue|editor-last2=Sako|first1=David|last1=Bernhard|first2=Olivier|last2=Pereira|first3=Bogdan|last3=Warinschi|title=Advances in Cryptology – ASIACRYPT 2012|chapter=How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios|chapter-url=http://www.uclouvain.be/crypto/services/download/publications.pdf.87e67d05ee05000b.6d61696e2e706466.pdf|pages=626–643}}|https://eprint.iacr.org/2016/771.pdf

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|date=January 2020|reason=This is not obvious, and I have no idea where such a claim is proven.}}

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

{{DEFAULTSORT:Fiat-Shamir heuristic}}

Category:Digital signature

Category:Theory of cryptography