Incomputer science, aone-way function is afunction that is easy to compute on every input, but hard toinvert given theimage of a random input. Here, "easy" and "hard" are to be understood in the sense ofcomputational complexity theory, specifically the theory ofpolynomial time problems. This has nothing to do with whether the function isone-to-one; finding any one input with the desired image is considered a successful inversion. (See§ Theoretical definition, below.)

The existence of such one-way functions is still an openconjecture. Their existence would prove that thecomplexity classesP and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.^{[1]: 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.^[2]

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 anymalicious agents".^{[citation needed]} One-way functions, in this sense, are fundamental tools forcryptography,personal identification,authentication, and otherdata 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 mosttelecommunications,e-commerce, ande-banking systems around the world.

A functionf : {0, 1}^* → {0, 1}^* isone-way iff can be computed by a polynomial-time algorithm, but any polynomial-timerandomized algorithm${\displaystyle F}$ that attempts to compute a pseudo-inverse forf succeeds withnegligible probability. (The * superscript means any number of repetitions, seeKleene star.) That is, for all randomized algorithms${\displaystyle F}$, all positive integersc and all sufficiently largen = length(x),

where the probability is over the choice ofx from thediscrete uniform distribution on {0, 1} ⁿ, and the randomness of${\displaystyle F}$.^[3]

Note that, by this definition, the function must be "hard to invert" in theaverage-case, rather than worst-case sense. This is different from much of complexity theory (e.g.,NP-hardness), 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 beNP-complete, it does not imply their one-wayness. The latter property is only based on the lack of known algorithms 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 ofn zeros on any input of lengthn isnot 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 algorithmF that just outputs any string of lengthn on inputf(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.

Aone-way permutation is a one-way function that is also a permutation—that is, a one-way function that isbijective. One-way permutations are an importantcryptographic primitive, and it is not known if their existence is implied by the existence of one-way functions.

Atrapdoor 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 thetrapdoor, is known.

Acollision-free hash functionf is a one-way function that is alsocollision-resistant; that is, norandomized polynomial time algorithm can find acollision—distinct valuesx,y such thatf(x) =f(y)—with non-negligible probability.^[4]

Iff is a one-way function, then the inversion off would be a problem whose output is hard to compute (by definition) but easy to check (just by computingf on it). Thus, the existence of a one-way function implies thatFP ≠ FNP, which in turn implies that P ≠ NP. However, P ≠ 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 generators
• Pseudorandom function families
• Bit commitment schemes
• Private-key encryption schemes secure againstadaptive chosen-ciphertext attack
• Message authentication codes
• Digital signature schemes (secure against adaptive chosen-message attack)

The following are several candidates for one-way functions (as of April 2009). Clearly, it is not known whetherthese functions are indeed one-way; but extensive research has so far failed to produce an efficient inverting algorithm for any of them.^{[citation needed]}

The functionf takes as inputs two prime numbersp andq in binary notation and returns their product. This function can be "easily" computed inO(b²) time, whereb is the total number of bits of the inputs. Inverting this function requires finding thefactors of a given integerN. The best factoring algorithms known run in${\displaystyle O\left(\exp \sqrt[3]{\frac{64}{9}b(\log b{)}^2}\right)}$time, where b is the number of bits needed to representN.

This function can be generalized by allowingp andq to range over a suitable set ofsemiprimes. Note thatf is not one-way for randomly selected integersp,q > 1, since the product will have 2 as a factor with probability 3/4 (because the probability that an arbitraryp is odd is 1/2, and likewise forq, so if they're chosen independently, the probability that both are odd is therefore 1/4; hence the probability thatp orq is even, is1 − 1/4 = 3/4).

TheRabin function,^[1]: 57 or squaringmodulo${\displaystyle N=pq}$, wherep andq are primes is believed to be a collection of one-way functions. We write

${\displaystyle {\mathrm{Rabin}}_N(x)\triangleq x^{2}modN}$

to denote squaring moduloN: a specific member of theRabin collection. It can be shown that extracting square roots, i.e. inverting the Rabin function, is computationally equivalent to factoringN (in the sense ofpolynomial-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 whichp andq are of the same bit length. TheRabin signature algorithm is based on the assumption that this Rabin function is one-way.

Modular exponentiation can be done in polynomial time. Inverting this function requires computing thediscrete logarithm. Currently there are several popular groups for which no algorithm to calculate the underlying discrete logarithm in polynomial time is known. These groups are allfinite abelian groups and the general discrete logarithm problem can be described as thus.

LetG be a finite abelian group ofcardinalityn. Denote itsgroup operation by multiplication. Consider aprimitive elementα ∈G and another elementβ ∈G. The discrete logarithm problem is to find the positive integerk, where1 ≤k ≤ n, such that:

${\displaystyle {\alpha }^k=\underset{k\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}}{\underbrace{\alpha \cdot \alpha \cdot \dots \cdot \alpha }}=\beta }$

The integerk that solves the equationα^k =β is termed thediscrete logarithm ofβ to the baseα. One writesk = log_αβ.

Popular choices for the groupG in discrete logarithmcryptography are the cyclic groups(Z_p)^× (e.g.ElGamal encryption,Diffie–Hellman key exchange, and theDigital Signature Algorithm) and cyclic subgroups ofelliptic curves overfinite fields (seeelliptic curve cryptography).

An elliptic curve is a set of pairs of elements of afield satisfyingy² =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). MultiplicationkP of a pointP by an integerk (i.e., agroup action of the additive group of the integers) is defined as repeated addition of the point to itself. Ifk andP are known, it is easy to computeR =kP, but if onlyR andP are known, it is assumed to be hard to computek.

There are a number ofcryptographic hash functions that are fast to compute, such asSHA-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 for one-way functions include the hardness of the decoding of randomlinear codes, the hardness of certainlattice problems, and thesubset sum problem (Naccache–Stern knapsack cryptosystem).

There is an explicit functionf that has been proved to be one-way, if and only if one-way functions exist.^[5] In other words, if any function is one-way, then so isf. 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—perhaps non-constructively—that one such function exists.

There also exists a function that is one-way if polynomial-time boundedKolmogorov 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.^[6]

• One-way compression function
• Cryptographic hash function
• Geometric cryptography
• Trapdoor function

• Jonathan Katz and Yehuda Lindell (2007).Introduction to Modern Cryptography. CRC Press.ISBN 1-58488-551-3.
• Michael Sipser (1997).Introduction to the Theory of Computation. PWS Publishing.ISBN 978-0-534-94728-6. Section 10.6.3: One-way functions, pp. 374–376.
• Christos Papadimitriou (1993).Computational Complexity (1st ed.). Addison Wesley.ISBN 978-0-201-53082-7. Section 12.1: One-way functions, pp. 279–298.

• Cryptographic primitives
• Unsolved problems in computer science

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from September 2023
• Articles with unsourced statements from March 2018