One-Way Function

Informally, a function f is a one-way function if

1. The description of f is publicly known and does not require any secret information for its operation.

2. Given x, it is easy to compute f(x).

3. Given y, in the range of f, it is hard to find an x such that f(x)=y. More precisely, any efficient algorithm solving a P-problem succeeds in inverting f with negligible probability.

The existence of one-way functions is not proven. If true, it would imply P!=NP. Therefore, it would answer the complexity theory NP-problem question of whether all apparently NP-problems are actually P-problems. Yet a number of conjectured one-way functions are routinely used in commerce and industry. For example, it is conjectured, but not proved, that the following are one-way functions:

1. Factoring problem: f(p,q)=pq, for randomly chosen primes p,q.

2. Discrete logarithm problem:

 f(p,g,x)=<p,g,g^x (mod p)>

for g a generator of Z_p^* for some prime p.

3. Discrete root extraction problem: f(p,q,e,y)=<pq,e,y^e (mod pq)>, for y in Z_(pq)^*, e in Z_(pq) and relatively prime to (p-1)(q-1), and p,q primes. This is the function commonly known as RSA encryption.

4. Subset sum problem: f(a,b)=<sum_(i=1)^(n)a_ib_i,b>, for a_i in {0,1}, and n-bit integers b_i.

5. Quadratic residue problem.

See also

NP-Problem, One-Way Hash Function, P-Problem, Quadratic Residue, RSA Encryption, Subset Sum Problem

Explore with Wolfram|Alpha


Luby, M. Pseudorandomness and Cryptographic Applications. Princeton, NJ: Princeton University Press, 1996.Ziv, J. "In Search of a One-Way Function" §4.1 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 104-105, 1987.

Referenced on Wolfram|Alpha

One-Way Function

Cite this as:

Weisstein, Eric W. "One-Way Function." From MathWorld--A Wolfram Web Resource.

Subject classifications