Fiat-Shamir Heuristic - Revision history

Srikar: /* Security */

2020-07-01T00:08:33Z

Security

Srikar: /* References */

2020-07-01T00:08:23Z

References

Srikar: /* Assumptions */

2020-07-01T00:07:45Z

Assumptions

Srikar: /* Assumptions */

2020-06-30T23:17:53Z

Assumptions

Srikar: /* Assumptions */

2020-06-30T23:17:11Z

Assumptions

Srikar at 23:15, 30 June 2020

2020-06-30T23:15:58Z

Srikar at 23:14, 30 June 2020

2020-06-30T23:14:42Z

Srikar: /* Example */

2020-06-30T23:14:30Z

Example

Srikar at 23:13, 30 June 2020

2020-06-30T23:13:42Z

Srikar at 23:13, 30 June 2020

2020-06-30T23:13:26Z

← Older revision		Revision as of 00:08, 1 July 2020
Line 32:		Line 32:

	===Security===		===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===		===Useful Links and Notes===

← Older revision		Revision as of 00:08, 1 July 2020
Line 36:		Line 36:

	===References===		===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.

	== References ==		== References ==

@@ Line 29: / Line 29: @@
 ===Assumptions===
 #The first assumption is that the original interactive proof must be [[Public Coin Protocols|public coin]]
 ===Security===

@@ Line 28: / Line 28: @@
 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|Public Coin Protocols]]
+#The first assumption is that the original interactive proof must be [[Public Coin Protocols|public coin]]
 ===Security===

@@ Line 28: / Line 28: @@
 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
+#The first assumption is that the original interactive proof must be [[public-coin|Public Coin Protocols]]
 ===Security===

@@ Line 12: / Line 12: @@
 # 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>.
 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 2: / Line 2: @@
 ==Example==
 '''Interactive Version'''
 We have a prime <math>n</math>.
 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 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.
 ==Example==
-We have a prime <math>n</math>
+'''Interactive Version'''
 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 34: / Line 35: @@
 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.
 == References ==