Cryptography Reference
In-Depth Information
probability, where the probability is taken over the elements on the domain of the
function and the random coins of the algorithm. This is reasonable in view of the fact
that an inverse image (or preimage) of an element can always be foundwith negligible
probability just by guessing and, on the other hand, if we allow the inverting algorithm
enough power, it is always possible to invert the function just by performing a brute-
force search over its domain in exponential time. To formalize this we define an
experiment (a game between a challenger and an adversary
A
):
}
∗
Definition 3.8
The
inversion experiment
Inv
A,
f
(
n
)
for a function
f
:{
0
,
1
→
}
∗
, where
{
0
,
1
A
is a PPT algorithm and
n
a positive integer, is the following:
n
1. A random
x
←{
0
,
1
}
is chosen and
y
:=
f
(
x
)
is computed (by the challenger).
is given 1
n
and
y
as input and outputs an integer
x
.
3. The output of the experiment is defined to be 1 (
2.
A
x
)
=
A
wins the game) if
f
(
y
,
and 0 otherwise.
The formal definition of one-way function is then the following:
}
∗
→{
}
∗
is
one-way
if the following condi-
Definition 3.9
A function
f
:{
0
,
1
0
,
1
tions hold:
1. (
f is easy to compute.
) There exists a PPT algorithm that on input
x
outputs
f
.
2. (
f is hard to invert.
) For every PPT algorithm
(
x
)
A
there exists a negligible function
negl
such that
Pr
(
Inv
A
,
f
(
n
)
=
1
)
≤
negl
(
n
).
Remarks 3.3
1. The meaning of the 'security parameter' 1
n
, given in unary in the definition
above, is that
takes as input 1
n
and
f
A
(
)
x
for some randomly chosen
x
such
(
)
=
that len
x
n
and has to run on polynomial time on
n
, independently of the
length of
f
. This prevents the possibility that a function might be regarded
as one-way because the size of
x
is exponential as a function of the size of
f
(
x
)
most significant bits of
x
, then any inverting algorithm requires time exponential
in len
(
x
)
. For example, if
f
(
x
)
=
y
, where
y
is the string formed by the
ln ln
x
(
f
(
x
))
(because just printing its output is exponential in len
(
f
(
x
))
)but,
clearly, there is an inverting algorithm polynomial in len
(
x
)
. Of course, in case
, then the auxiliary
input given by the security parameter is no longer necessary.
2. Note that, in Definition 3.8,
f
is a length-preserving function, i.e., len
(
f
(
x
))
=
len
(
x
)
is not asked to output
x
but some
x
such that
A
x
)
=
although, of course, the only possible value is
x
if
f
is injective.
3. There are many variations on the concept of one-way function; the definition
above is perhaps the most convenient and these functions are often called
strong
one-way functions
(when a PPT algorithm has negligible success probability in
inverting them while, for example,
weak
one-way functions are those for which
f
(
f
(
x
)
