Editing Provable security (section)

=== Controversies ===

Several researchers have found mathematical fallacies in proofs that had been used to make claims about the security of important protocols.  In the following partial list of such researchers, their names are followed by first a reference to the original paper with the purported proof and then a reference to the paper in which the researchers reported on flaws:
V. Shoup;<ref>{{cite book|last1=Bellare|first1=Mihir|last2=Rogaway|first2=Phillip|title=Advances in Cryptology — EUROCRYPT'94 |chapter=Optimal asymmetric encryption |volume=950|pages=92–111|doi=10.1007/BFb0053428|series=Lecture Notes in Computer Science|year=1995|isbn=978-3-540-60176-0|doi-access=free}}</ref><ref>{{citation|last=Shoup|first=Victor|title=OAEP reconsidered|journal=Journal of Cryptology|volume=15|issue=4|year=2002|pages=223–249|doi=10.1007/s00145-002-0133-9|s2cid=26919974|doi-access=free}}</ref>
A. J. Menezes;<ref>{{cite book|last=Krawczyk|first=Hugo|title=Advances in Cryptology – CRYPTO 2005 |chapter=HMQV: A High-Performance Secure Diffie-Hellman Protocol |volume=3621|pages=546–566|doi=10.1007/11535218_33|series=Lecture Notes in Computer Science|year=2005|isbn=978-3-540-28114-6|doi-access=free}}</ref><ref>{{citation|last=Menezes|first=Alfred J.|title=Another look at HMQV|journal=Journal of Mathematical Cryptology|volume=1|year=2007|pages=47–64|doi=10.1515/JMC.2007.004|s2cid=15540513|doi-access=free}}</ref>
A. Jha and M. Nandi;<ref>{{cite book|last1=Bellare|first1=Mihir|last2=Pietrzak|first2=Krzysztof|last3=Rogaway|first3=Phillip|title=Advances in Cryptology – CRYPTO 2005 |chapter=Improved Security Analyses for CBC MACs |series=Lecture Notes in Computer Science|year=2005|volume=3621|pages=527–545|doi=10.1007/11535218_32|isbn=978-3-540-28114-6|doi-access=free}}; and {{citation|last=Pietrzak|first=Krzysztof |title=Automata, Languages and Programming |chapter=A Tight Bound for EMAC |volume=4052|pages=168–179|doi=10.1007/11787006_15|series=Lecture Notes in Computer Science|year=2006|isbn=978-3-540-35907-4}}</ref><ref>{{citation|last1=Jha|first1=Ashwin|last2=Nandi|first2=Mridul|title=Revisiting structure graphs: Applications to CBC-MAC and EMAC|journal=Journal of Mathematical Cryptology|volume=10|issue=3–4|year=2016|pages=157–180|doi=10.1515/jmc-2016-0030|s2cid=33121117}}</ref>
D. Galindo;<ref>{{citation|last1=Boneh|first1=Dan|last2=Franklin|first2=Matthew|title=Identity-based encryption from the Weil pairing|journal=SIAM Journal on Computing|volume=32|issue=3|year=2003|pages=586–615|doi=10.1137/S0097539701398521}}</ref><ref>{{citation|last=Galindo|first=David |title=Automata, Languages and Programming |chapter=Boneh-Franklin Identity Based Encryption Revisited |volume=3580|pages=[https://archive.org/details/automatalanguage2005inte/page/791 791–802]|doi=10.1007/11523468_64|series=Lecture Notes in Computer Science|year=2005|hdl=2066/33216|isbn=978-3-540-27580-0|s2cid=605011 |url=https://archive.org/details/automatalanguage2005inte/page/791|hdl-access=free}}</ref>
T. Iwata, K. Ohashi, and K. Minematsu;<ref>{{citation|last1=McGrew|first1=David A.|last2=Viega|first2=John|title=Progress in Cryptology - INDOCRYPT 2004 |chapter=The Security and Performance of the Galois/Counter Mode (GCM) of Operation |volume=3348|pages=343–355|doi=10.1007/978-3-540-30556-9_27|series=Lecture Notes in Computer Science|year=2004|isbn=978-3-540-24130-0}}</ref><ref>{{cite book|last1=Iwata|first1=Tetsu|last2=Ohashi|first2=Keisuke|last3=Minematsu|first3=Kazuhiko|title=Advances in Cryptology – CRYPTO 2012 |chapter=Breaking and Repairing GCM Security Proofs |volume=7417|pages=31–49|doi=10.1007/978-3-642-32009-5_3|series=Lecture Notes in Computer Science|year=2012|isbn=978-3-642-32008-8|doi-access=free}}</ref>
M. Nandi;<ref>{{citation|last1=Ristenpart|first1=Thomas|last2=Rogaway|first2=Phillip |title=Fast Software Encryption |chapter=How to Enrich the Message Space of a Cipher |volume=4593|pages=101–118|doi=10.1007/978-3-540-74619-5_7|series=Lecture Notes in Computer Science|year=2007|isbn=978-3-540-74617-1|doi-access=free}}</ref><ref>{{cite book|last=Nandi|first=Mridul|title=Advances in Cryptology – ASIACRYPT 2014 |chapter=XLS is Not a Strong Pseudorandom Permutation |volume=8874|pages=478–490|doi=10.1007/978-3-662-45611-8_25|series=Lecture Notes in Computer Science|year=2014|isbn=978-3-662-45607-1|doi-access=free}}</ref>
J.-S. Coron and D. Naccache;<ref>{{cite book|last1=Bellare|first1=Mihir|last2=Garray|first2=Juan A.|last3=Rabin|first3=Tal|title=Advances in Cryptology — EUROCRYPT'98 |chapter=Fast batch verification for modular exponentiation and digital signatures |volume=1403|pages=236–250|doi=10.1007/BFb0054130|series=Lecture Notes in Computer Science|year=1998|isbn=978-3-540-64518-4|doi-access=free}}</ref><ref>{{citation|last1=Coron|first1=Jean-Sébastien|last2=Naccache|first2=David |title=Public Key Cryptography |volume=1560|pages=197–203|doi=10.1007/3-540-49162-7|series=Lecture Notes in Computer Science|year=1999|isbn=978-3-540-65644-9|s2cid=11711093}}</ref>
D. Chakraborty, V. Hernández-Jiménez, and P. Sarkar;<ref>{{citation|last1=McGrew|first1=David A.|last2=Fluhrer|first2=Scott R. |title=Selected Areas in Cryptography |chapter=The Security of the Extended Codebook (XCB) Mode of Operation |volume=4876|pages=311–327|doi=10.1007/978-3-540-77360-3_20|series=Lecture Notes in Computer Science|year=2007|isbn=978-3-540-77359-7|doi-access=free}}</ref><ref>{{citation|last1=Chakraborty|first1=Debrup|last2=Hernández-Jiménez|first2=Vicente|last3=Sarkar|first3=Palash|title=Another look at XCB|journal=Cryptography and Communications|volume=7|number=4|year=2015|pages=439–468|doi=10.1007/s12095-015-0127-8|s2cid=17251595}}</ref>
P. Gaži and U. Maurer;<ref>{{cite book|last1=Bellare|first1=Mihir|last2=Rogaway|first2=Phillip|title=Advances in Cryptology - EUROCRYPT 2006 |chapter=The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs |series=Lecture Notes in Computer Science|year=2006|volume=4004|pages=409–426|doi=10.1007/11761679_25|isbn=978-3-540-34546-6|doi-access=free}}</ref><ref>{{cite book|last1=Gaži|first1=Peter|last2=Maurer|first2=Ueli|title=Advances in Cryptology – ASIACRYPT 2009 |chapter=Cascade Encryption Revisited |volume=5912|pages=37–51|doi=10.1007/978-3-642-10366-7_3|series=Lecture Notes in Computer Science|year=2009|isbn=978-3-642-10365-0|doi-access=free}}</ref>
S. A. Kakvi and E. Kiltz;<ref>{{cite book|last=Coron|first=Jean-Sébastien|title=Advances in Cryptology — EUROCRYPT 2002 |chapter=Optimal Security Proofs for PSS and Other Signature Schemes |volume=2332|pages=272–287|doi=10.1007/3-540-46035-7_18|series=Lecture Notes in Computer Science|year=2002|isbn=978-3-540-43553-2|doi-access=free}}</ref><ref>{{cite book|last1=Kakvi|first1=Saqib A.|last2=Kiltz|first2=Eike|title=Advances in Cryptology – EUROCRYPT 2012 |chapter=Optimal Security Proofs for Full Domain Hash, Revisited |volume=7237|pages=537–553|doi=10.1007/978-3-642-29011-4_32|series=Lecture Notes in Computer Science|year=2012|isbn=978-3-642-29010-7|doi-access=free}}</ref>
and T. Holenstein, R. Künzler, and S. Tessaro.<ref>{{cite book|last1=Coron|first1=Jean-Sébastien|last2=Patarin|first2=Jacques|last3=Seurin|first3=Yannick|title=Advances in Cryptology – CRYPTO 2008 |chapter=The Random Oracle Model and the Ideal Cipher Model Are Equivalent |volume=5157|pages=1–20|doi=10.1007/978-3-540-85174-5_1|series=Lecture Notes in Computer Science|year=2008|isbn=978-3-540-85173-8|doi-access=free}}</ref><ref>{{citation|last1=Holenstein|first1=Thomas|last2=Künzler|first2=Robin|last3=Tessaro|first3=Stefano|title=Proceedings of the forty-third annual ACM symposium on Theory of computing |chapter=The equivalence of the random oracle model and the ideal cipher model, revisited |date=2011 |pages=89–98|doi= 10.1145/1993636.1993650|arxiv=1011.1264|isbn=9781450306911|s2cid=2960550}}</ref>

[[Neal Koblitz|Koblitz]] and Menezes have written that provable security results for important cryptographic protocols frequently have fallacies in the proofs; are often interpreted in a misleading manner, giving false assurances; typically rely upon strong assumptions that may turn out to be false; are based on unrealistic models of security; and serve to distract researchers' attention from the need for "old-fashioned" (non-mathematical) testing and analysis.  Their series of papers supporting these claims<ref>{{cite journal|title=Critical perspectives on provable security: Fifteen years of 'Another look' papers |journal=Advances in Mathematics of Communications |volume=13 |year=2019 |pages=517–558 |doi=10.3934/amc.2019034 |doi-access=free |last1=Koblitz|first1=Neal |last2=Menezes|first2=Alfred |issue=4}}</ref><ref>These papers are all available at {{cite web|title=Another look at provable security|url=http://anotherlook.ca|access-date=12 April 2018}}</ref> have been controversial in the community.  Among the researchers who have rejected the viewpoint of Koblitz–Menezes is [[Oded Goldreich]], a leading theoretician and author of ''Foundations of Cryptography''.<ref>{{cite book|last=Goldreich|first=Oded|title=Foundations of Cryptography|publisher=Cambridge University Press|year=2003|isbn=9780521791724}}</ref> He wrote a refutation of their first paper "Another look at 'provable security'"<ref>{{citation|last1=Koblitz|first1=Neal|last2=Menezes|first2=Alfred J.|title=Another look at "provable security"|journal=Journal of Cryptology|volume=20|issue=1|year=2007|pages=3–37|doi=10.1007/s00145-005-0432-z|s2cid=7601573|doi-access=free}}</ref> that he titled "On post-modern cryptography".  Goldreich wrote: "...&nbsp;we point out some of the fundamental philosophical flaws that underlie the said article and some of its misconceptions regarding theoretical research in cryptography in the last quarter of a century."<ref name="pomo">{{cite web|title=On post-modern cryptography|url=https://eprint.iacr.org/2006/461|access-date=12 April 2018}}</ref>{{rp|1}} In his essay Goldreich argued that the rigorous analysis methodology of provable security is the only one compatible with science, and that Koblitz and Menezes are "reactionary (i.e., they play to the hands of the opponents of progress)".<ref name="pomo"/>{{rp|2}}

In 2007, Koblitz published "The Uneasy Relationship Between Mathematics and Cryptography",<ref>{{citation|last=Koblitz|first=Neal|title=The uneasy relationship between mathematics and cryptography|journal=Notices Amer. Math. Soc.|volume=54|issue=8|year=2007|pages=972–979|url=https://www.ams.org/notices/200708/tx070800972p.pdf}}</ref> which contained some controversial statements about provable security and other topics.  Researchers Oded Goldreich, Boaz Barak, [[Jonathan Katz (computer scientist)|Jonathan Katz]], Hugo Krawczyk, and [[Avi Wigderson]] wrote letters responding to Koblitz's article, which were published in the November 2007 and January 2008 issues of the journal.<ref name="ams1">{{citation|title=Letters to the Editor|journal=Notices Amer. Math. Soc.|volume=54|issue=12|year=2007|pages=1454–1455|url=https://www.ams.org/notices/200711/tx071101454p.pdf}}</ref><ref name="ams2">{{citation|title=Letters to the Editor|journal=Notices Amer. Math. Soc.|volume=55|issue=1|year=2008|pages=6–7|url=https://www.ams.org/notices/200801/tx080100006p.pdf}}</ref>  Katz, who is coauthor of a highly regarded cryptography textbook,<ref>{{cite book|last1=Katz|first1=Jonathan|last2=Lindell|first2=Yehuda|title=Introduction to Modern Cryptography|publisher=Chapman & Hall/CRC|year=2008|isbn=9781584885511}}</ref> called Koblitz's article "snobbery at its purest";<ref name="ams1"/>{{rp|1455}} and Wigderson, who is a permanent member of the [[Institute for Advanced Study]] in Princeton, accused Koblitz of "slander".<ref name="ams2"/>{{rp|7}}

[[Ivan Damgård]] later wrote a [[position paper]] at ICALP 2007 on the technical issues,<ref>{{Cite book | last1 = Damgård | first1 = I. | title = Automata, Languages and Programming | chapter = A "proof-reading" of Some Issues in Cryptography | doi = 10.1007/978-3-540-73420-8_2 | volume = 4596 | pages = 2–11 | year = 2007 | isbn = 978-3-540-73419-2| series = Lecture Notes in Computer Science}}</ref> and it was recommended by [[Scott Aaronson]] as a good in-depth analysis.<ref>{{cite web|url=http://www.scottaaronson.com/blog/?p=268|title=Shtetl-Optimized|work=scottaaronson.com|date=September 2007 }}</ref>
[[Brian Snow]], former Technical Director of the Information Assurance Directorate of the U.S. [[National Security Agency]], recommended the Koblitz-Menezes paper "The brave new world of bodacious assumptions in cryptography"<ref>{{citation|last1=Koblitz|first1=Neal|last2=Menezes|first2=Alfred J.|title=The brave new world of bodacious assumptions in cryptography|journal=Notices Amer. Math. Soc.|volume=57|year=2010|pages=357–365|url=https://www.ams.org/notices/201003/rtx100300357p.pdf}}</ref> to the audience at the RSA Conference 2010 Cryptographers Panel.<ref>{{cite web|title=RSA Conference 2010 USA: The Cryptographers Panel| website=[[YouTube]] | date=9 March 2010 |url=https://www.youtube.com/watch?v=z7nOsqgIzew |archive-url=https://ghostarchive.org/varchive/youtube/20211222/z7nOsqgIzew |archive-date=2021-12-22 |url-status=live|access-date=9 April 2018}}{{cbignore}}</ref>