Content deleted Content added
m →Multiplication and factoring: Fixed typo |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (5 intermediate revisions by 5 users not shown) | |||
Line 1:
{{Short description|Function used in computer cryptography}}
{{unsolved|computer science|Do one-way functions exist?}}
In [[computer science]], a '''one-way function''' is a [[function (mathematics)|function]] that is easy to compute on every input, but hard to [[Inverse function|invert]] given the [[image (mathematics)|image]] of a random input. Here, "easy" and "hard" are to be understood in the sense of [[computational complexity theory]], specifically the theory of [[polynomial time]] problems. This has nothing to do with whether the function is [[One-to-one function|one-to-one]]; finding any one input with the desired image is considered a successful inversion. (See {{slink||Theoretical definition}}, below.)
The existence of such one-way functions is still an open [[conjecture]]. Their existence would prove that the [[complexity classes]] [[P = NP problem|P and NP are not equal]], thus resolving the foremost unsolved question of theoretical computer science.<ref name=Goldreich>[[Oded Goldreich]] (2001). Foundations of Cryptography: Volume 1, Basic Tools ([http://www.wisdom.weizmann.ac.il/~oded/PSBookFrag/part2N.ps draft available] from author's site). Cambridge University Press. {{isbn|0-521-79172-3}}. See also [http://www.wisdom.weizmann.ac.il/~oded/foc-book.html wisdom.weizmann.ac.il].</ref>{{rp|ex. 2.2, page 70}} The converse is not known to be true, i.e. the existence of a proof that P ≠ NP would not directly imply the existence of one-way functions.<ref>[[Shafi Goldwasser|Goldwasser, S.]] and [[Mihir Bellare|Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Webarchive|url=https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html |date=2012-04-21 }}. Summer course on cryptography, MIT, 1996–2001.</ref>
In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any [[Black hat hacking|malicious agents]]".{{citation needed|date=September 2023}} One-way functions, in this sense, are fundamental tools for [[cryptography]], [[personal identification]], [[authentication]], and other [[data security]] applications. While the existence of one-way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most [[
==Theoretical definition==
Line 48 ⟶ 49:
The '''Rabin function''',<ref name=Goldreich />{{rp|57}} or squaring [[modular arithmetic|modulo]] <math>N=pq</math>, where {{mvar|p}} and {{mvar|q}} are primes is believed to be a collection of one-way functions. We write
:<math>\operatorname{Rabin}_N(x)\triangleq x^2\bmod N</math>
to denote squaring modulo {{mvar|N}}: a specific member of the '''Rabin collection'''. It can be shown that extracting square roots, i.e. inverting the Rabin function, is computationally equivalent to factoring {{mvar|N}} (in the sense of [[polynomial-time reduction]]). Hence it can be proven that the Rabin collection is one-way if and only if factoring is hard. This also holds for the special case in which {{mvar|p}} and {{mvar|q}} are of the same bit length. The [[Rabin
===Discrete exponential and logarithm===
Line 72 ⟶ 73:
There is an explicit function ''f'' that has been proved to be one-way, if and only if one-way functions exist.<ref name="HCPred">{{Cite journal |first=Leonid A. |last=Levin |author-link=Leonid Levin |title=The Tale of One-Way Functions |journal=Problems of Information Transmission |issue=39 |date=January 2003 |volume=39 |pages=92–103 |arxiv=cs.CR/0012023 |doi=10.1023/A:1023634616182}}</ref> In other words, if any function is one-way, then so is ''f''. Since this function was the first combinatorial complete one-way function to be demonstrated, it is known as the "universal one-way function". The problem of finding a one-way function is thus reduced to proving{{emdash}}perhaps non-constructively{{emdash}}that one such function exists.
There also exists a function that is one-way if polynomial-time bounded [[Kolmogorov complexity#Time-bounded complexity|Kolmogorov complexity]] is mildly hard on average. Since the existence of one-way functions implies that polynomial-time bounded Kolmogorov complexity is mildly hard on average, the function is a universal one-way function.<ref>{{cite arXiv |last1=Liu |first1=Yanyi |title=On One-way Functions and Kolmogorov Complexity |date=2020-09-24 |eprint=2009.11514 |class=cs.CC |last2=Pass |first2=Rafael}}</ref>
==See also==
| |||