One-way function: Difference between revisions

Revision as of 12:02, 22 April 2021

Latest revision as of 01:21, 8 August 2025

(43 intermediate revisions by 37 users not shown)

Line 1:

{{Short description|Function thatused isin easycomputer to compute on every input, but hard to invert given the image of a random inputcryptography}}

{{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. Not being [[One-to-one function|one-to-one]] is not considered sufficient for a function to be called one-way (see [[#Theoretical definition|Theoretical definition]], below).

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. NotThis beinghas nothing to do with whether the function is [[One-to-one function|one-to-one]]; isfinding notany consideredone sufficientinput forwith athe functiondesired toimage beis calledconsidered one-waya (seesuccessful [[#Theoreticalinversion. definition (See {{slink||Theoretical definition]]}}, below.).

The existence of such one-way functions is still an open [[conjecture]]. In fact, 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 Bellare, M. [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"]. Summer course on cryptography, MIT, 1996–2001</ref>

The existence of such one-way functions is still an open [[conjecture]]. In fact, theirTheir 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}}. (seeSee 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≠NPP&nbsp;≠&nbsp;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 agent]]s". 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 [[telecommunication]]s, [[e-commerce]], and [[Online banking|e-banking]] systems around the world.

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 agentagents]]s".{{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 [[telecommunicationtelecommunications]]s, [[e-commerce]], and [[Online banking|e-banking]] systems around the world.

==Theoretical definition==

A function ''f'' : {0,&nbsp;1}^* → {0,&nbsp;1}^* is '''one-way''' if ''f'' can be computed by a polynomial -time algorithm, but any polynomial -time [[randomized algorithm]] <math>F</math> that attempts to compute a pseudo-inverse for ''f'' succeeds with [[Negligible function|negligible]] probability. (The * superscript means any number of repetitions, ''see'' [[Kleene star]].) That is, for all randomized algorithms <math>F</math> , all positive integers ''c'' and all sufficiently large ''n'' = length(''x'') ,

: <math>\Pr[f(F(f(x))) = f(x)] < n^{-c},</math>

where the probability is over the choice of ''x'' from the [[Uniform distribution (discrete)|discrete uniform distribution]] on {0,&nbsp;1}&nbsp;^''n'', and the randomness of <math>F</math>.<ref>Many authors view this definition as strong one-way function. A Weakweak one-way function can be defined similarly except that the probability that every adversarial <math>F</math> fails to invert ''f'' is noticeable. However, one may construct strong one-way functions based on weak ones. Loosely speaking, strong and weak versions of one-way function are equivalent theoretically. See Goldreich's Foundations of Cryptography, vol. &nbsp;1, ch .&nbsp;2.1–2.3.</ref>

Note that, by this definition, the function must be "hard to invert" in the [[best, worst and average case|average-case, rather than worst-case]] sense. This is different from much of complexity theory (e.g., [[NP-hard]]ness), where the term "hard" is meant in the worst-case. That is why even if some candidates for one-way functions (described below) are known to be [[NP-complete]], it does not imply their one-wayness. The latter property is only based on the lack of known algorithmalgorithms to solve the problem.

It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function that outputs the string of ''n'' zeros on any input of length ''n'' is ''not'' a one-way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm ''F'' that just outputs any string of length ''n'' on input ''f''(''x'') will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.

==Related concepts==

A '''one-way permutation''' is a one-way function that is also a permutation—that is, a one-way function that is [[Bijection|bijective]]. One-way permutations are an important [[cryptographic primitive]], and it is not known if their existence is implied by the existence of one-way functions.

A [[trapdoor one-way function]] or trapdoor permutation is a special kind of one-way function. Such a function is hard to invert unless some secret information, called the ''trapdoor'', is known.

A '''collision-free hash function''' ''f'' is a one-way function that is also ''collision-resistant''; that is, no [[randomized polynomial time]] algorithm can find a [[hash collision (computer science)|collision]]—distinct values ''x'', ''y'' such that ''f''(''x'') = ''f''(''y'')—with non-negligible probability.<ref>{{cite journal |last=Russell |first=A. |title=Necessary and Sufficient Conditions for Collision-Free Hashing |journal=[[Journal of Cryptology]] |volume=8 |issue=2 |pages=87–99 |year=1995 |doi=10.1007/BF00190757 |s2cid=26046704 }}</ref>

==Theoretical implications of one-way functions==

If ''f'' is a one-way function, then the inversion of ''f'' would be a problem whose output is hard to compute (by definition) but easy to check (just by computing ''f'' on it). Thus, the existence of a one-way function implies that [[FP (complexity)|FP]]&nbsp;≠&nbsp;[[FNP (complexity)|FNP]], which in turn implies that P≠NPP&nbsp;≠&nbsp;NP. However, P≠NPP&nbsp;≠&nbsp;NP does not imply the existence of one-way functions.

The existence of a one-way function implies the existence of many other useful concepts, including:

* [[Pseudorandom functiongenerator]] familiess

* [[Pseudorandom generatorfunction]]s families

* [[commitmentCommitment scheme|Bit commitment schemes]]

*[[Pseudorandom function]] families

* Private-key encryption schemes secure against [[adaptive chosen-ciphertext attack]]

*[[commitment scheme|Bit commitment schemes]]

* [[Message authentication code]]s

*Private-key encryption schemes secure against [[adaptive chosen-ciphertext attack]]

* [[Digital signature scheme]]s (secure against adaptive chosen-message attack)

*[[Message authentication code]]s

*[[Digital signature scheme]]s (secure against adaptive chosen-message attack)

The existence of one-way functions also implies that there is no [[natural proof]] for P≠NP.

==Candidates for one-way functions==

Line 44 ⟶ 42:

===Multiplication and factoring===

The function ''f'' takes as inputs two prime numbers ''p'' and ''q'' in binary notation and returns their product. This function can be "easily" computed in [[big O notation|''O''(''b''²)]] time, where ''b'' is the total number of bits of the inputs. Inverting this function requires finding the [[integer factorization|finding the factors]] of a given integer]] ''N''. The best factoring algorithms known run in <math>O\left(\exp\sqrt[3]{\frac{64}{9} b (\log b)^2}\right)</math>time, where b is the number of bits needed to represent ''N''.

This function can be generalized by allowing ''p'' and ''q'' to range over a suitable set of [[semiprimes]]. Note that ''f'' is not one-way for randomly selected integers {{nowrap|''p'', ''q'' &gt; 1}}, since the product will have 2 as a factor with probability 3/4 (because the probability that an arbitrary ''p'' is odd is 1/2, and likewise for ''q'', so if they're chosen independently, the probability that both are odd is therefore 1/4; hence the probability that ''p'' or ''q'' is even, is {{nowrap|1=1 − 1/4 = 3/4}}).

===The Rabin function (modular squaring)===

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 cryptosystemsignature algorithm]] is based on the assumption that this [[Rabin one-way function|Rabin function]] is one-way.

===Discrete exponential and logarithm===

Line 60 ⟶ 58:

:<math>\alpha^k = \underbrace{\alpha \cdot \alpha \cdot \ldots \cdot \alpha}_{k \; \mathrm{times}} = \beta</math>

The integer ''k'' that solves the equation {{nowrap|1=''&alpha;''^''k'''' = ''&beta;''}} is termed the '''discrete logarithm''' of ''&beta;'' to the base ''&alpha;''. One writes {{nowrap|1=''k'' = log_''&alpha;'' ''&beta;''}}.

Popular choices for the group ''G'' in discrete logarithm [[cryptography]] are the cyclic groups [[multiplicative group of integers modulo n|('''Z'''_''p'')^''×'']] (e.g. [[ElGamal encryption]], [[Diffie–Hellman key exchange]], and the [[Digital Signature Algorithm]]) and cyclic subgroups of [[elliptic curve]]s over [[finite field]]s (''see'' [[elliptic curve cryptography]]).

An elliptic curve is a set of pairs of elements of a [[Field (mathematics)|field]] satisfying {{nowrap|1=''y''² = ''x''³ + ''ax'' + ''b''}}. The elements of the curve form a group under an operation called "point addition" (which is not the same as the addition operation of the field). Multiplication ''kP'' of a point ''P'' by an integer ''k'' (''i.e.'', a [[Group action (mathematics)|group action]] of the additive group of the integers) is defined as repeated addition of the point to itself. If ''k'' and ''P'' are known, it is easy to compute {{nowrap|1=''R'' = ''kP''}}, but if only ''R'' and ''P'' are known, it is assumed to be hard to compute ''k''.

===Cryptographically secure hash functions===

There are a number of [[cryptographic hash function]]s that are fast to compute, such as [[SHA -256]]. Some of the simpler versions have fallen to sophisticated analysis, but the strongest versions continue to offer fast, practical solutions for one-way computation. Most of the theoretical support for the functions are more techniques for thwarting some of the previously successful attacks.

===Other candidates===

Other candidates for one-way functions have been based oninclude the hardness of the decoding of random [[linear code]]s, the hardness of certain [[lattice problems]], and the [[subset sum problem]] ([[Naccache–Stern knapsack cryptosystem]]), or other problems.

==Universal one-way function==

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 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

| author = Leonid Levin

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>

| author-link = Leonid Levin

| title = The Tale of One-Way Functions

| publisher = ACM

| year = 2003

| arxiv = cs.CR/0012023

}}</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 that one such function exists.

==See also==

Line 97 ⟶ 90:

{{DEFAULTSORT:One-Way Function}}

[[Category:Cryptography]]

[[Category:Cryptographic primitives]]

[[Category:Unsolved problems in computer science]]