Cryptography Reference
In-Depth Information
Proof.
We use the characterization of Dec
d
||
.
||
a
in terms of best adaptive distinguisher.
be a distinguisher between
F
and
F
∗
limited to
d
oracle calls with maximum
advantage. As discussed previously, we can assume without loss of generality that the
distinguisher is deterministic, and that all queries to the oracle are pairwise different (we
can simulate the distinguisher by replacing repeated queries by dummy queries). The
behavior of
We let
A
A
is deterministically defined by the oracle responses
y
=
(
y
1
,...,
y
d
).
We let
x
i
denote the
i
-th query defined by
y
. It actually depends on
y
1
,...,
y
i
−
1
only.
We let
x
=
(
x
1
,...,
x
d
) which is assumed to be in
X
.Welet
A
be the set of all
y
for
which
A
outputs 0. It is straightforward that
[
F
]
x
,
y
−
[
F
∗
]
x
,
y
.
F
∗
)
Adv
A
(
F
,
=−
y
∈
A
Next we have
F
∗
)
ε
2
[
F
∗
]
x
,
y
+
[
F
∗
]
x
,
y
.
Adv
A
(
F
,
≤
y
∈
A
y
∈
A
y
∈
Y
y
∈
Y
By relaxing the
y
in the first sum, we observe that it is upper-bounded by
2
. (We just
have to add the
y
j
's backward, starting by adding all
y
d
's, then
y
d
−
1
, etc.) For the second
sum, we recall that all
x
i
's are pairwise different, so [
F
∗
]
x
,
y
is always equal to
p
0
. This
sum is thus less than
ε
1
.
Finally, the following result shows the relationship between the decorrelation of
order 2 and the resistance against differential and linear cryptanalysis. This demon-
strates that although it is hard to construct a cryptographic primitive with proven low
decorrelation bias to a high order
d
, focusing on the order
d
=
2 already provides
decent security results.
Theorem 4.15 (Vaudenay 2003 [183]).
Let C be a random permutation over
{
0
,
1
}
m
compared with a uniformly distributed random permutation C
∗
. We have
1
EDP
max
≤
C
∗
)
1
+
,
BestAdv
Cl
a
(
C
2
m
−
1
ELP
max
≤
C
∗
)
1
+
4BestAdv
Cl
a
(
C
,
2
m
−
where C
∗
is a uniformly distributed random permutation.
Proof.
By straightforward computations we obtain that
2
−
m
x
1
,
x
2
y
1
,
E
(DP
C
(
a
b
[
C
]
(
x
1
,
x
2
)
,
(
y
1
,
y
2
)
,
b
))
=
1
x
2
=
x
1
+
a
y
2
=
y
1
+
y
2
Search WWH ::
Custom Search