One-way function: Difference between revisions

Revision as of 21:44, 26 March 2024

Latest revision as of 01:21, 8 August 2025

(17 intermediate revisions by 15 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. 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]]. 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&nbsp;≠&nbsp;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]]. 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&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 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 [[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 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 [[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>

Line 19 ⟶ 20:

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

Line 41 ⟶ 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 function is one-way.

===Discrete exponential and logarithm===

Line 57 ⟶ 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===

Line 70 ⟶ 71:

==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{{emdash}}perhaps non-constructively{{emdash}}that one such function exists.

==See also==