Cryptography Reference
In-Depth Information
further clarify the condition placed on the success probability, we consider two trivial
algorithms.
Random-Guess Algorithm
A
1
.
On input (
y
1
n
), algorithm
A
1
uniformly selects and
outputs a string of length
n
. We note that the success probability of
A
1
equals the
,
collision probability of the random variable
f
(
U
n
) (i.e.,
y
Pr
[
f
(
U
n
)
=
y
]
2
). That is,
letting
U
n
denote a random variable uniformly distributed over
{
0
,
1
}
n
independently
of
U
n
,wehave
[
A
1
(
f
(
U
n
)
,
1
n
)
∈
f
−
1
(
f
(
U
n
))]
=
Pr
[
f
(
U
n
)
=
f
(
U
n
)]
Pr
y
Pr
y
]
2
2
−
n
=
[
f
(
U
n
)
=
≥
where the inequality is due to the fact that, for non-negative
x
i
's summing to 1, the
sum
i
x
i
is minimized when all
x
i
's are equal. Thus, the last inequality becomes an
equality if and only if
f
is a 1-1 function. Consequently:
1.
For any function
f
, the success probability of the trivial algorithm
A
1
is strictly positive.
Thus, one cannot require that any efficient algorithm will
always
fail to invert
f
.
2.
For any 1-1 function
f
, the success probability of
A
1
in inverting
f
is negligible.
Of course, this does not indicate that
f
is one-way (but rather that
A
1
is trivial).
3.
If
f
is one-way, then the collision probability of the random variable
f
(
U
n
) is negligible.
This follows from the fact that
A
1
falls within the scope of the definition, and its
success probability equals the collision probability.
Fixed-Output Algorithm
A
2
.
Another trivial algorithm, denoted
A
2
, is one that com-
putes a function that is constant on all inputs of the same length (e.g.,
A
2
(
y
1
n
)
0
n
).
,
=
For every function
f
,wehave
[
A
2
(
f
(
U
n
)
,
1
n
)
∈
f
−
1
(
f
(
U
n
))]
=
Pr
[
f
(0
n
)
=
f
(
U
n
)]
=
|
f
−
1
(
f
(0
n
))
Pr
|
≥
2
−
n
2
n
with equality holding in case
f
(0
n
) has a single pre-image (i.e., 0
n
itself ) under
f
.
Again we observe analogous facts:
1.
For any function
f
, the success probability of the trivial algorithm
A
2
is strictly positive.
2.
For any 1-1 function
f
, the success probability of
A
2
in inverting
f
is negligible.
3.
If
f
is one-way, then the fraction of
x
's in
n
that are mapped by
f
to
f
(0
n
)is
{
0
,
1
}
negligible.
Obviously, Definition 2.2.1 considers all probabilistic polynomial-time algorithms,
not merely the trivial ones discussed earlier. In some sense this definition asserts that
for one-way functions, no probabilistic polynomial-time algorithm can “significantly”
outperform these trivial algorithms.
