Cryptography Reference
In-Depth Information
d
(
d
−
1)
m
2
. Second, for
y
2
−
thus we let
1
=
∈
Y
and any
x
(with pairwise different
2
entries), we need to consider [
F
]
x
,
y
. Let
E
2
be the event that all
z
i
's are pairwise
different over the distribution of
F
1
.Wehave
[
F
]
x
,
y
≥
E
2
] Pr[
E
2
]
|
.
Pr[
E
E
2
] we know that
z
i
's are pairwise different, as for the
z
i
's. Hence
For computing Pr[
E
|
d
(
d
−
1)
2
m
2
, which is
E
2
]
2
−
md
. It is then straightforward that Pr[
E
2
]
2
−
Pr[
E
|
=
≥
1
−
F
∗
)
1
−
ε
2
. We thus obtain from Lemma 4.14 (given later) that BestAdv
Cl
a
(
F
,
≤
m
2
. From Lemma 4.14 it is straightforward that BestAdv
Cl
a
(
C
∗
,
1)2
−
F
∗
)
d
(
d
−
≤
m
2
m
2
. Since
1
1)2
−
m
. We thus obtain BestAdv
Cl
a
(
F
C
∗
)
d
2
2
−
2
1
+
2
d
(
d
−
,
≤
for
d
≤
BestAdv is always less than 1, it also holds for larger
d
.
4.4.3
Decorrelation
The notion of decorrelation of a function provides a nice algebraic interpretation of the
best advantage in terms of distribution distance (see Ref. [183]).
Given a random function
F
from a set
A
to a set
B
, we first define the real matrix
[
F
]
d
B
d
-type matrix (the rows are numbered by input
d
-tuples, and the
columns are numbered by output
d
-tuples) for which the ((
x
1
,...,
as a
A
d
×
x
d
)
,
(
y
1
,...,
y
d
))-
entry is
[
F
]
(
x
1
,...,
x
d
)
,
(
y
1
,...,
y
d
)
=
Pr[
F
(
x
1
)
=
y
1
,...,
F
(
x
d
)
=
y
d
]
.
A random function
F
is aimed at being compared to a canonical ideal random function
F
∗
. For instance, if
F
is a block cipher, the canonical ideal random function is a
uniformly distributed random permutation. Given a distance
D
on the vector space of
A
d
B
d
-type real matrices, we define the
d
-wise decorrelation bias of
F
by
×
Dec
d
(
F
)
D
([
F
]
d
[
F
∗
]
d
)
=
,
.
Different distances will define various decorrelation notions.
x
2
We take a simple example with
A
={
0
,
1
,
2
}
and
B
={
0
,
1
}
with
F
(
x
)
=
(
K
.
+
K
+
x
2
K
.
+
x
+
1) mod 2 for
K
uniformly distributed in
{
1
,
2
,
3
,
4
}
. Here is the table
of all possible
F
functions.
K
f
(0)
f
(1)
f
(2)
1
1
0
0
2
1
0
1
3
0
1
1
4
1
0
1
Search WWH ::
Custom Search