Cryptography Reference
In-Depth Information
Decorrelation has nice properties which come from its algebraic definition. For
instance we can use the triangular inequality. When
D
is defined by a matrix norm,
6
decorrelation is multiplicative: if the canonical ideal random function associated with a
random permutation is a uniformly distributed random permutation, then the decorre-
lation of a product of independent random permutations is at most equal to the product
of the decorrelation of each permutation. Let
C
1
and
C
2
be two independent random
permutations over a set
A
. They are compared to a uniformly distributed random per-
mutation over
A
. Because of the independence between
C
1
and
C
2
,wehave
C
1
]
d
[
C
1
]
d
[
C
2
]
d
[
C
2
◦
=
×
.
Then we notice that
[
C
1
]
d
[
C
∗
]
d
[
C
∗
◦
C
1
]
d
[
C
∗
]
d
×
=
=
and
[
C
∗
]
d
[
C
2
]
d
C
∗
]
d
[
C
∗
]
d
×
=
[
C
2
◦
=
because
C
∗
◦
C
∗
, and
C
∗
have exactly the same distribution. Hence
C
1
,
C
2
◦
[
C
1
]
d
[
C
∗
]
d
×
[
C
2
]
d
[
C
∗
]
d
=
C
1
]
d
[
C
∗
]
d
−
−
[
C
2
◦
−
which leads us to
Dec
d
(
C
2
◦
Dec
d
(
C
1
)
Dec
d
(
C
2
)
C
1
)
≤
×
.
We now show the relationship between best advantage and decorrelation.
Theorem 4.13 (Vaudenay 2003 [183]).
We let
|||
.
|||
∞
be the matrix norm associated
to the infinity norm:
y
1
,
y
2
,...,
y
d
|
|||
A
|||
∞
=
max
x
1
,
x
2
,...,
x
d
A
(
x
1
,
x
2
,...,
x
d
)
,
(
y
1
,
y
2
,...,
y
d
)
|
.
For any F and its canonical ideal version F
∗
we have
1
2
Dec
d
F
∗
)
,
=
.
BestAdv
Cl
na
(
F
(
F
)
|||
.
|||
∞
||
.
||
a
which provides the same result for
Cl
a
:
Similarly, there exists a matrix norm
1
2
Dec
d
F
∗
)
BestAdv
Cl
a
(
F
,
=
||
.
||
a
(
F
)
.
6
A matrix norm is a norm such that
||
A
×
B
||≤||
A
||
.
||
B
||
.
Search WWH ::
Custom Search