Cryptography Reference
In-Depth Information
Proof.
We let
p
C
DP
C
(
a
b
) be the probability of the characteristic (which depends
on the secret key). Given a distribution
C
, the probability that the distinguisher outputs
1is
=
,
E
1
p
C
)
n
−
(1
−
x
)
n
E
(
p
C
).
over the distribution of
C
. Since we have 1
−
(1
−
≤
nx
, this is less than
n
.
p
∗
|≤
p
∗
), we obtain that
Now since
|
p
−
max(
p
,
max
E
(
p
C
)
E
(
p
C
∗
)
.
C
∗
)
Adv (
C
,
≤
n
.
,
Finally, we have
E
p
C
∗
=
E
DP
C
∗
(
a
b
)
,
P
X
C
∗
(
X
b
C
∗
(
X
)
=
+
=
+
C
∗
a
)
Pr
C
∗
b
C
∗
(
X
C
∗
(
X
)
=
X
+
a
)
=
+
1
=
1
.
2
m
−
This concludes the proof.
Linear distinguishers can be modelized as depicted in Fig. 4.12. Here is a useful
lemma in order to analyze the advantage.
Lemma 4.8.
For the distinguisher of Fig. 4.12 we let p
c
be the probability that the
output is 1 given an oracle c. We let p
0
be the probability that it outputs 1 when the
counter is incremented with probability
1
2
in each iteration instead of querying the
oracle. We have
2
n
p
c
LP
c
(
a
|
−
p
0
|≤
.
,
b
)
.
Proof.
We first express the probability
p
c
that the distinguisher accepts
c
. Let
N
i
be
the random variable defined as being 1 or 0 depending on whether or not we have
X
·
a
=
c
(
X
)
·
b
in the
i
-th iteration depending on the random variable
X
. All
N
i
's
Parameters:
a complexity
n
, a characteristic
(
a
,
b
)
, a set
Oracle:
a permutation
c
1:
initialize the counter value
u
to zero
2:
for
i
from 1 to
n
do
3:
pick a random
X
with a uniform distribution and query for
c
(
X
)
4:
if
X
·
a
=
c
(
X
)
·
b
, increment the counter
u
5:
end for
6:
if
u
∈
, output 1, otherwise output 0
Figure 4.12.
Linear distinguisher.
Search WWH ::
Custom Search