Cryptography Reference
In-Depth Information
where the probability is taken uniformly over all the possible
choices of
x ∈{
0
,
1
}
n
and all the possible outcomes of the
internal coin tosses of algorithm
A
.
Algorithm
A
is given the auxiliary input 1
n
so to allow it to run in
time polynomial in the length of
x
, which is important in case
f
drasti-
cally shrinks its input (e.g.,
)). Typically,
f
is length
preserving, in which case the auxiliary input 1
n
is redundant. Note
that
A
is not required to output a specific preimage of
f
(
x
); any pre-
image (i.e., element in the set
f
−
1
(
f
(
x
))) will do. (Indeed, in case
f
is
1-1, the string
x
is the only preimage of
f
(
x
) under
f
; but in general
there may be other preimages.) It is required that algorithm
A
fails (to
find a preimage) with overwhelming probability, when the probability
is also taken over the input distribution. That is,
f
is “typically” hard
to invert, not merely hard to invert in some (“rare”) cases.
Some of the most popular candidates for one-way functions are
based on the conjectured intractability of computational problems in
number theory. One such conjecture is that it is infeasible to factor
large integers. Consequently, the function that takes as input two (equal
length) primes and outputs their product is widely believed to be a one-
way function. Furthermore, factoring such a composite is infeasible if
and only if squaring modulo such a composite is a one-way function
(see (109)). For certain composites (i.e., products of two primes that
are both congruent to 3 mod 4), the latter function induces a permuta-
tion over the set of quadratic residues modulo this composite. A related
permutation, which is widely believed to be one-way, is the RSA func-
tion (112):
x
|
f
(
x
)
|
=
O
(log
|
x
|
x
e
mod
N
,where
N
=
P
→
·
Q
is a composite as above,
e
is relatively prime to (
P
. The latter
examples (as well as other popular suggestions) are better captured by
the following formulation of a collection of one-way functions (which is
indeed related to Definition 2.1):
−
1)
·
(
Q
−
1), and
x
∈{
0
, ..., N
−
1
}
Definition 2.2.
(collections of one-way functions):
A collection of
functions,
}
∗
}
i∈I
, is called
one-way
if there exists three
probabilistic polynomial-time algorithms,
I
,
D
and
F
, so that the fol-
lowing two conditions hold:
{
f
i
:
D
i
→{
0
,
1
