Cryptography Reference
In-Depth Information
cient function in the sense that there exists a deterministic algorithm that, on input
k
in time polynomial in 1
n
.
We can now define pseudo-random functions (and pseudo-random permutations)
with the help of PPT distinguishers
D
that output 0 or 1 according to whether or not
a permutation looks random to them:
n
, computes
F
k
(
,
∈{
,
}
)
x
0
1
x
Definition 4.2
The
pseudo-random function experiment
Prf
D
,
F
(
, where
F
is a
length-preserving keyed function,
D
a PPT algorithm, and
n
any value of the security
parameter, is the following:
1. On input 1
n
,abit
b
n
)
n
)
{
0
,
1
}
n
(where
we use the notation
Y
X
for the set of functions from
X
to
Y
) is selected as follows:
∈{
0
,
1
}
is chosen and a function
f
∈
(
{
0
,
1
}
n
n
)
{
0
,
1
}
•
If
b
(i.e.,
f
is randomly chosen in the set of
functions that map
n
-bit strings to
n
-bit strings).
=
0 then
f
←
(
{
0
,
1
}
n
,
f
F
k
.
D
is then given input 1
n
and oracle access to
f
.
•
If
b
=
1 then
k
←{
0
,
1
}
:=
2.
D
adaptively makes a polynomial number of queries to the oracle about
f
(
x
)
,
n
for the values
x
∈{
0
,
1
}
it chooses.
3.
D
outputs a bit
b
.
4. The advantage of
D
in the experiment is defined as
Adv
prf
b
=
D
,
F
(
n
)
=|
Pr
(
1
|
b
=
b
=
1
)
−
Pr
(
1
|
b
=
0
)
|
.
The length-preserving keyed function
F
is said to be a
pseudo-random function
if, for
any PPT algorithm
D
, there is a negligible function
negl
(
such that
Adv
prf
D
n
)
F
(
n
)
≤
,
negl
(
)
. The experiment
Prp
D
,
F
(
)
is defined for an efficient length-preserving
keyed permutation
F
in an entirely similar way, with the only difference that when
b
n
n
is a randomly chosen permutation. If
Adv
prp
D
n
=
0, then
f
←
S
(
{
0
,
1
}
)
F
(
n
)
is
,
negligible, then
F
is said to be a
pseudo-random permutation
.
Remarks 4.2
1. When
F
is a block cipher,
F
may be seen as the result of letting a keyed permu-
tation act on keys and inputs of fixed length
n
. In this case it does not make much
sense to say that the advantage of
D
is negligible but, for practical purposes, we
will understand this as meaning that the advantage is very small for this value
of
n
, so that no PPT distinguisher would be able, in practice, to succeed in the
above experiment. In this case we can say that the block cipher is modeled as a
pseudo-random permutation or, simply, that it is a pseudo-random permutation.
2. If
F
is a pseudo-randompermutation, thenwemaywonder whether distinguishing
it from a random function is any easier than distinguishing it from a random
permutation (or even if there are pseudo-randompermutations that are not pseudo-
random functions). When
n
is small, this is indeed the case, for an adversary able
to make about 1
2
n
/
2
queries has a probability
.
18
·
≥
1
/
2 of finding two values
x
=
y
such that
f
(
x
)
=
f
(
y
)
(a collision for
f
) in case
f
is a randomly
n
. This is a consequence of the birthday
paradox (see Theorem 5.4) and means that this adversary is able to distinguish
n
:{
,
}
→{
,
}
chosen function
f
0
1
0
1
