Difference between revisions of "Fiat-Shamir Heuristic"

From zkstacks
Jump to navigation Jump to search
 
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
The '''Fiat–Shamir heuristic''' is a technique for taking an [[Interactive Proof of Knowledge]] and creating a [[digital signature]] based on it.  
 
The '''Fiat–Shamir heuristic''' is a technique for taking an [[Interactive Proof of Knowledge]] and creating a [[digital signature]] based on it.  
−
===Example===
+
==Example==
−
 
+
'''Interactive Version'''
−
===Relevant papers===
 
−
It was first introduced in a paper by  [[Amos Fiat]] and [[Adi Shamir]] (1986).<ref>{{cite journal |last1=Fiat |first1=Amos |last2=Shamir |first2=Adi |title=How To Prove Yourself: Practical Solutions to Identification and Signature Problems |journal=Advances in Cryptology — CRYPTO' 86 |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>.
 
−
===Assumptions===
 
−
#The first assumption is that the original interactive proof
 
−
===Security===
 
−
 
 
−
===Useful Links and Notes===
 
−
 
 
−
===References===
 
−
 
 
−
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 journal |last1=Pointcheval |first1=David |last2=Stern |first2=Jacques |title=Security Proofs for Signature Schemes |journal=Advances in Cryptology — EUROCRYPT '96 |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 journal |last1=Don |first1=Jelle |last2=Fehr |first2=Serge|last3=Majenz |first3=Christian |last4=Schaffner |first4=Christian|title=Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model |journal=Advances in Cryptology — CRYPTO '19 |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 }}</ref>, and concurrently by Liu and Zhandry<ref>{{cite journal |last1=Liu |first1=Qipeng |last2=Zhandry |first2=Mark|title=Revisiting Post-quantum Fiat-Shamir |journal=Advances in Cryptology — CRYPTO '19 |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 }}</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 journal |last1=Goldwasser |first1=S. |last2=Kalai |first2=Y. T. |title=On the (In)security of the Fiat-Shamir paradigm |journal=44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. |date=October 2003 |pages=102–113 |doi=10.1109/SFCS.2003.1238185 |isbn=0-7695-2040-5 }}</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==
+
We have a prime <math>n</math>.  
−
For the algorithm specified below, readers should be familiar with the laws of [[modular arithmetic]], especially with [[Multiplicative group of integers modulo n|multiplicative groups of integers modulo n]] with prime ''n''.
 
  
 
Here is an '''interactive''' proof of knowledge of a discrete logarithm.<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}}</ref>
 
Here is an '''interactive''' proof of knowledge of a discrete logarithm.<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}}</ref>
Line 27: Line 12:
 
# Peggy computes <math>r = v - cx</math> and returns <math>r</math> to Victor.
 
# Peggy computes <math>r = v - cx</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 = g^{v - cx}g^{xc} = g^v = t</math>.
 
# He checks whether <math>t \equiv g^ry^c</math>. This holds because <math>g^ry^c = g^{v - cx}g^{xc} = g^v = t</math>.
 +
 +
'''Non-Interactive Version'''
  
 
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>
 
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>
Line 37: Line 24:
  
 
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.<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>
 
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.<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>
 +
 +
===Relevant papers===
 +
It was first introduced in a paper by  [[Amos Fiat]] and [[Adi Shamir]] (1986).<ref>{{cite journal |last1=Fiat |first1=Amos |last2=Shamir |first2=Adi |title=How To Prove Yourself: Practical Solutions to Identification and Signature Problems |journal=Advances in Cryptology — CRYPTO' 86 |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>.
 +
===Assumptions===
 +
#The first assumption is that the original interactive proof must be [[Public Coin Protocols|public coin]]
 +
#The second assumption is the existence of Random Oracles i.e. the heuristic only holds in the [[Random Oracle Model]]
 +
 +
===Security===
 +
The heuristic was originally presented without a proof of security; later, [[David Pointcheval|Pointcheval]] and [[Jacques Stern|Stern]]<ref>{{cite journal |last1=Pointcheval |first1=David |last2=Stern |first2=Jacques |title=Security Proofs for Signature Schemes |journal=Advances in Cryptology — EUROCRYPT '96 |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 journal |last1=Don |first1=Jelle |last2=Fehr |first2=Serge|last3=Majenz |first3=Christian |last4=Schaffner |first4=Christian|title=Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model |journal=Advances in Cryptology — CRYPTO '19 |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 }}</ref>, and concurrently by Liu and Zhandry<ref>{{cite journal |last1=Liu |first1=Qipeng |last2=Zhandry |first2=Mark|title=Revisiting Post-quantum Fiat-Shamir |journal=Advances in Cryptology — CRYPTO '19 |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 }}</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 journal |last1=Goldwasser |first1=S. |last2=Kalai |first2=Y. T. |title=On the (In)security of the Fiat-Shamir paradigm |journal=44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. |date=October 2003 |pages=102–113 |doi=10.1109/SFCS.2003.1238185 |isbn=0-7695-2040-5 }}</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.
 +
 +
===Useful Links and Notes===
 +
 +
===References===
  
 
== References ==
 
== References ==

Latest revision as of 00:08, 1 July 2020

The Fiat–Shamir heuristic is a technique for taking an Interactive Proof of Knowledge and creating a digital signature based on it.

Example

Interactive Version

We have a prime \(n\).

Here is an interactive proof of knowledge of a discrete logarithm.<ref>Template:Cite journal</ref>

  1. Peggy wants to prove to Victor the verifier that she knows \(x\): the discrete logarithm of \(y = g^x\) to the base \(g\) (mod n).
  2. She picks a random \(v\in \Z^*_q\), computes \(t = g^v\) and sends \(t\) to Victor.
  3. Victor picks a random \(c\in \Z^*_q\) and sends it to Peggy.
  4. Peggy computes \(r = v - cx\) and returns \(r\) to Victor.
  5. He checks whether \(t \equiv g^ry^c\). This holds because \(g^ry^c = g^{v - cx}g^{xc} = g^v = t\).

Non-Interactive Version

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>Template:Cite journal</ref>

  1. Peggy wants to prove that she knows \(x\): the discrete logarithm of \(y = g^x\) to the base \(g\).
  2. She picks a random \(v\in\Z^*_q\) and computes \(t = g^v\).
  3. Peggy computes \(c = H(g,y,t)\), where \(H()\) is a cryptographic hash function.
  4. She computes \(r = v - cx\). The resulting proof is the pair \((t,r)\). As \(r\) is an exponent of \(g\), it is calculated modulo \(q-1\), not modulo \(q\).
  5. Anyone can check whether \(t \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 x so that the product cx is known.<ref>Template:Cite book</ref>

Relevant papers

It was first introduced in a paper by Amos Fiat and Adi Shamir (1986).<ref>Template:Cite journal</ref>.

Assumptions

  1. The first assumption is that the original interactive proof must be public coin
  2. The second assumption is the existence of Random Oracles i.e. the heuristic only holds in the Random Oracle Model

Security

The heuristic was originally presented without a proof of security; later, Pointcheval and Stern<ref>Template:Cite journal</ref> 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<ref>Template:Cite journal</ref>, and concurrently by Liu and Zhandry<ref>Template:Cite journal</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>Template:Cite journal</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 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.

Useful Links and Notes

References

References

<references/>

Retrieved from "http://161.35.113.184/index.php?title=Fiat-Shamir_Heuristic&oldid=36"