Content deleted Content added
Citation bot (talk | contribs) Alter: date, title, journal, url, isbn, template type. URLs might have been anonymized. Add: chapter-url, chapter, series, isbn, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Cosmia Nebula | #UCB_webform |
Isaidnoway (talk | contribs) →Cryptography: close ref tag |
||
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>
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.
| |||