Просмотр кода страницы Английская Википедия:Fiat–Shamir heuristic

{{Английская Википедия/Панель перехода}}
In [[cryptography]], the '''Fiat–Shamir heuristic''' is a technique for taking an [[Proof of knowledge|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).<ref>{{cite book |last1=Fiat |first1=Amos |last2=Shamir |first2=Adi |title=Advances in Cryptology — CRYPTO' 86 |chapter=How to Prove Yourself: Practical Solutions to Identification and Signature Problems |volume=263 |date=1987 |pages=186–194 |doi=10.1007/3-540-47721-7_12 |publisher=Springer Berlin Heidelberg |language=en|series=Lecture Notes in Computer Science |isbn=978-3-540-18047-0 |doi-access=free }}</ref>
For the method to work, the original interactive proof must have the property of being [[Interactive proof system#Public coin protocol versus private coin protocol|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, [[David Pointcheval|Pointcheval]] and [[Jacques Stern|Stern]]<ref>{{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 }}</ref> proved its security against [[Chosen-plaintext attack|chosen message attacks]] in the ''random oracle model'', that is, assuming [[random oracle]]s exist. This result was generalized to the [[Random oracle#Quantum-accessible Random Oracles|quantum-accessible random oracle (QROM)]] by Don, Fehr, Majenz and Schaffner,<ref>{{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 }}</ref> and concurrently by Liu and Zhandry.<ref>{{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 }}</ref> In the case that random oracles do not exist, the Fiat–Shamir heuristic has been proven insecure by [[Shafi Goldwasser]] and [[Yael Tauman Kalai]].<ref>{{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 }}</ref> 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 zero-knowledge proof|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 [[Multiplicative group of integers modulo n|multiplicative groups <math>\Z^*_q</math>]], where ''q'' is a prime number, and [[Euler's theorem|Euler's totient theorem]] on the [[Euler's totient function]] ''φ''.

Here is an '''interactive''' proof of knowledge of a discrete logarithm in [[Multiplicative group of integers modulo n|<math>\Z^*_q</math>]], based on [[Schnorr signature]].<ref>{{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}}</ref> The public values are [[Multiplicative group of integers modulo n|<math>y \in \Z^*_q</math>]] and a generator ''g'' of  [[Multiplicative group of integers modulo n|<math>\Z^*_q</math>]], while the secret value is the discrete logarithm of ''y'' to the base ''g''.

# Peggy wants to prove to Victor, the verifier, that she knows <math>x</math> satisfying <math>y \equiv g^x</math> without revealing <math>x</math>.
# She picks a random <math>v\in \Z^*_q</math>, computes <math>t = g^v</math> and sends <math>t</math> to Victor.
# Victor picks a random <math>c\in \Z^*_q</math> and sends it to Peggy.
# Peggy computes <math>r = v - cx \bmod \varphi(q)</math> and returns <math>r</math> to Victor.
# He checks whether <math>t \equiv g^ry^c</math>. This holds because <math>g^ry^c \equiv g^{v - cx}g^{xc} \equiv g^v \equiv t</math> and <math>g^{\varphi(q)} \equiv 1</math>.

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.<ref>{{cite journal |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 }}</ref>

# Peggy wants to prove that she knows <math>x</math> such that  <math>y \equiv g^x</math> without revealing <math>x</math>.
# She picks a random <math>v\in\Z^*_q</math> and computes <math>t = g^v</math>.
# Peggy computes <math>c = H(g,y,t)</math>, where <math>H</math> is a cryptographic hash function.
# She computes <math>r = v - cx \bmod \varphi(q)</math>. The resulting proof is the pair <math>(t,r)</math>.
# Anyone can use this proof to calculate <math>c</math> and check whether <math>t \equiv g^ry^c</math>.

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.<ref>{{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}}</ref>

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

== See also ==

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

== References ==
<references/>

{{DEFAULTSORT:Fiat-Shamir heuristic}}
[[Category:Theory of cryptography]]
[[Category:Digital signature]]
{{Навигационная таблица/Портал/Английская Википедия}}
[[Категория:Английская Википедия]]
[[Категория:Википедия]]
[[Категория:Статья из Википедии]]
[[Категория:Статья из Английской Википедии]]