Cryptography Reference
In-Depth Information
•
The function
f
is hard to invert, meaning that it is not known how to efficiently
compute
f
−
1
(
f
(
x
))
for all
x
X
or
f
−
1
(
y
)
for
y
∈
R
Y
. Alternatively
speaking, there is no known PPT algorithm
A
that outputs
A
(
f
(
x
)) =
f
−
1
(
f
(
x
))
for all
x
∈
X
or
A
(
y
)=
f
−
1
(
y
)
for
y
∈
∈
R
Y
.
}
∗
. In either case,
A
is not required to find the
correct
x
; it is only required to find some inverse of
y
(if the function
f
is injective,
then the only inverse of
y
is
x
).
Another way to express the second condition in Definition 7.1 is to say that
any PPT algorithm
A
attempting to invert the one-way function on an element in its
range will succeed with no more than a negligible probability (i.e., smaller than any
polynomial in the size of the input, where the probability is taken over the elements
in the domain of the function and the internal coin tosses of
A
). The statement is
probabilistic (i.e.,
A
is not unable to invert the function, but it has a very low success
probability). More formally,
X
and
Y
are often set to
{
0
,
1
1
p
(
n
)
Pr[
A
(
f
(
x
)
,
1
n
)
f
−
1
(
f
(
x
))]
∈
≤
for every PPT algorithm
A
,all
x
X
, every polynomial
p
, and all sufficiently large
n
(with
n
representing the binary length of
x
). In this notation, the algorithm
A
is
given
f
(
x
) and the security parameter 1
n
(expressed in unary representation). The
only purpose of the second argument is to allow
A
to run in time polynomial in the
length of
x
,evenif
f
(
x
) is much shorter than
x
. This rules out the possibility that a
function is considered one way only because the inverting algorithm does not have
enough time to print the output. Typically,
f
is a length-preserving function, and in
this case the auxiliary argument 1
n
is redundant.
Note that the notation given earlier is not standard, and that there are many
notations used in the literature to express the same idea. For example, the following
notion is also frequently used in the literature.
∈
1
p
(
n
)
u
←{
n
;
y
A
(
y,
1
n
)]
Pr[(
f
(
z
)=
y
:
x
0
,
1
}
←
f
(
x
);
z
←
≤
n
,
y
is
assigned
f
(
x
),and
z
is assigned
A
(
y,
1
n
), then the probability that
f
(
z
) equals
y
is
negligible.
A few words concerning the notion of negligible probability are in place. We
consider the success probability of a PPT algorithm
A
to be negligible if it is bound
by a polynomial fraction. It follows that repeating
A
polynomially (in the input
It basically says the same thing: if
x
is selected uniformly from
{
0
,
1
}
