Average-case complexity: Difference between revisions

Revision as of 21:34, 21 May 2025

Revision as of 21:35, 21 May 2025

Line 76:

===Cryptography===

For most problems, average-case complexity analysis is undertaken to find efficient algorithms for a problem that is considered difficult in the worst-case. In cryptographic applications, however, the opposite is true: the worst-case complexity is irrelevant; we instead want a guarantee that the average-case complexity of every algorithm which "breaks" the cryptographic scheme is inefficient.<ref name="katz07"/><ref>{{Cite book |last1=Katz |first1=Jonathan |title=Introduction to modern cryptography |last2=Lindell |first2=Yehuda |date=2021 |publisher=CRC Press |isbn=978-1-351-13303-6 |edition=3 |series=Chapman & Hall/CRC cryptography and network security series |___location=Boca Raton, FL}}</ref>{{pn}}

Thus, all secure cryptographic schemes rely on the existence of [[one-way functions]].<ref name="bog06"/> Although the existence of one-way functions is still an open problem, many candidate one-way functions are based on hard problems such as [[integer factorization]] or computing the [[discrete log]]. Note that it is not desirable for the candidate function to be {{math|'''NP'''}}-complete since this would only guarantee that there is likely no efficient algorithm for solving the problem in the worst case; what we actually want is a guarantee that no efficient algorithm can solve the problem over random inputs (i.e. the average case). In fact, both the integer factorization and discrete log problems are in {{math|'''NP''' ∩ }}[[coNP|{{math|'''coNP'''}}]], and are therefore not believed to be {{math|'''NP'''}}-complete.<ref name="ab09"/> The fact that all of cryptography is predicated on the existence of average-case intractable problems in {{math|'''NP'''}} is one of the primary motivations for studying average-case complexity.