Cryptography Reference
InDepth 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
11, 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 oneway 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 oneway 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 oneway, 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 oneway functions (which is
indeed related to Definition 2.1):
−
1)
·
(
Q
−
1), and
x
∈{
0
, ..., N
−
1
}
Definition 2.2.
(collections of oneway functions):
A collection of
functions,
}
∗
}
i∈I
, is called
oneway
if there exists three
probabilistic polynomialtime algorithms,
I
,
D
and
F
, so that the fol
lowing two conditions hold:
{
f
i
:
D
i
→{
0
,
1