A one-way function is a function that is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. The precise meanings of "easy" and "hard" can be specified mathematically. With rare exceptions, almost the entire field of public key cryptography rests on the existence of one-way functions.

Formal definitions

---

Formally, two variants of one-way functions are defined: strong and weak one-way functions.

Strong one-way functions

A function $f\; :\; \backslash \{0,1\backslash \}^*\; \backslash rightarrow\; \backslash \{0,1\backslash \}^*$ is called (strongly) one-way if the following two conditions hold:

1. easy to compute: There exists a (deterministic) polynomial-time algorithm, $A$, so that on input $x$ algorithm $A$ outputs $f(x)$ (i.e., $A(x)=f(x)$)
2. hard to invert: For every probabilistic polynomial-time algorithm, $A^\text{'}$, every polynomial $p(\backslash cdot)$, and every sufficiently large $n$

$U\_n$ denotes a random variable uniformly distributed over $\backslash \{0,1\backslash \}^n$. Hence, the probability in the second condition is taken over all the possible values assigned to $U\_n$ and all possible internal coin tosses of $A^\text{'}$ with uniform probability distribution. In addition to an input in the range of $f$ the inverting algorithm is also given the desired length of the output in unary notation. The main reason for this convention is to rule out the possibility that a function is considered one-way merely because the inverting algorithm does not have enough time to print the output.

The left hand part of the comparison is quite easy to understand: it is the probability, that $A^\text{'}$ finds any value $U$, with property $f(U)\; =\; f(U\_n)$. So, basically, the hard-to-invert condition requires this probability to negligibly small.

Weak one-way functions

One-way functions as defined above, are one-way in a very strong sense. Namely, any efficient inverting algorithm has negligible success in inverting them. A much weaker definition, presented below, only requires that all efficient inverting algorithms fail with some non-negligible probability.

A function $f\; :\; \backslash \{0,1\backslash \}^*\; \backslash rightarrow\; \backslash \{0,1\backslash \}^*$ is called weakly one-way if the following two conditions hold:

1. easy to compute: as in the definition of strong one-way function.
2. slightly-hard to invert: There exists a polynomial $p(\backslash cdot)$ such that for every probabilistic polynomial-time algorithm, $A^\text{'}$, and all sufficiently large $n$'s

$P(A^\text{'}(f(U\_n),\; 1^n)\; \backslash not\backslash in\; f^\{-1\}f(U\_n))\; >\; \{1\; \backslash over\; p(n)\}$

Existence

---

It is not known whether one-way functions exist. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science. However, it is not clear if P≠NP implies the existence of one-way functions. It can be proved that weak one-way functions exist if and only if strong one-way functions do. Thus, as far as the mere existence of one-way function goes, the notions of weak and strong one-way functions are equivalent.

It is known that the existence of one-way functions implies the existence of many other useful cryptographic primitives, including (but not limited to):

• Pseudorandom bit generators;
• Pseudorandom function families;
• Digital signature schemes (secure against adaptive chosen-message attack).

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. RSA is a well known example of a function believed to belong to this class.

A distinct but related concept in cryptography is that of the cryptographic hash function.

Candidates for one-way functions

---

Following are several candidates for one-way functions. Clearly, it is not known whether these functions are indeed one-way. This is only a conjecture supported by extensive research which has so far failed to produce an efficient inverting algorithm having non-negligible success probability.

Integer factorization

In spite of the extensive research directed towards the construction of the efficient (integer) factoring algorithm, the best algorithms known for factoring an integer $N$, run in time $2^\{O(\backslash sqrt\{\backslash log\; P\; \backslash log\; \backslash log\; P\})\}$, where $P$ is the second biggest prime factor of $N$. Hence it is reasonable to believe that the function, which partitions its input string into two parts and returns the (binary representation of the) integer by multiplying (the integers represented by) these parts, is one-way.

Rabin (quadratic residue) function

It can be shown that extracting square roots modulo $N$ is computationally equivalent to factoring $N$ (i.e., the two tasks are reducible to one another via probabilistic polynomial-time reductions). Hence, squaring modulo a composite is a one-way function if and only if factoring is intractable. The Rabin cryptosystem is based on the assumption that Rabin function is one-way. (See also quadratic residue.)

Discrete logarithms

Another computational number problem which is widely believed to be intractable is that of extracting discrete logarithms in a finite field (and in particular of prime cardinality). Thus exponentiation in the finite field is a reasonable candidate for one-way function.

Other candidates

Other possible candidates for one-way functions might based on the hardness of the decoding of random linear codes, the subset sum problem, or any other NP-complete problem.

References

---

• Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
• Section 10.6.3: One-way functions, pp.374–376.
• Section 12.1: One-way functions, pp.279–298.

Cryptography | Cryptographic primitives

Einwegfunktion | Funciones de un solo sentido | Fonction à sens unique | 일방향함수 | פונקציה חד כיוונית | 一方向性関数