TOPICS

One-Way Function

Informally, a function is a one-way function if

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

2. Given , it is easy to compute .

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

The existence of one-way functions is not proven. If true, it would imply . 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: , for randomly chosen primes .

2. Discrete logarithm problem:

for a generator of for some prime .

3. Discrete root extraction problem: , for in , in and relatively prime to , and primes. This is the function commonly known as RSA encryption.

4. Subset sum problem: , for , and -bit integers .

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

Explore with Wolfram|Alpha

More things to try:

References

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.

One-Way Function

Cite this as:

Weisstein, Eric W. "One-Way Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/One-WayFunction.html