Cryptography Reference
In-Depth Information
Finally, indistinguishability from a truly random source is also a way to define
randomness
: a pseudorandom generator is secure if it is indistinguishable from a truly
random generator. Clearly, if we can predict some nontrivial information about the next
generation of a pseudorandom source, then we can distinguish it from a random one.
The converse is also true: if we can distinguish a pseudorandom source from a random
one with a minimal number
d
of generations, then from the
d
1 first generations
we can predict that the
d
-th one will be the one for which the distinguisher yields 1.
Indistinguishability is indeed often used as a synonym for randomness.
−
4.4.2
The Luby-Rackoff Result
In trying to analyze the security of DES, Michael Luby and Charles Rackoff proved
that the Feistel cipher can actually generate a good pseudorandom permutation if the
underlying round functions are random and we have at least three rounds. The result
formally, which was publicly presented in 1986, states the following.
Theorem 4.12 (Luby-Rac
k
off 1986 [119]).
Let F
1
,
F
2
,
F
3
be three independent
m
2
with uniform distribution. We have
random functions on
{
0
,
1
}
m
2
(
F
1
,
F
2
,
F
3
)
F
∗
)
d
2
2
−
BestAdv
Cl
a
(
,
≤
.
m
2
(
F
1
,
F
2
,
F
3
)
C
∗
)
d
2
2
−
BestAdv
Cl
a
(
,
≤
.
where F
∗
(resp. C
∗
) is a uniformly distributed random function (resp. permutation) on
{
m
. The results would still hold if we replaced the XOR of the Feistel schemes by
any (quasi)group operation.
0
,
1
}
(
F
1
,
F
2
,
F
3
), we let
Proof.
Following the Feistel scheme
F
=
(
z
i
,
z
i
)
x
i
=
z
i
=
z
i
+
F
1
(
z
i
)
(
z
i
,
z
i
)
y
i
=
.
We let
E
be the event
z
i
=
z
i
+
F
2
(
z
i
) and
z
i
=
z
i
+
F
3
(
z
i
) for
i
=
1
,...,
d
.We
thus have [
F
]
x
,
y
=
Pr[
E
]. We now define
Y
=
(
y
1
,...,
z
j
.
jz
i
=
y
d
);
∀
i
<
We can easily check that
Y
fulfills the requirements of Lemma 4.14 below. Firstly we
have
1
2
2
md
d
(
d
−
1)
m
2
−
#
Y
≥
−
2
Search WWH ::
Custom Search