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
.
5. Quadratic residue problem.