Cryptography Reference
In-Depth Information
Proof.
The ratio between the two shifted first terms of the equation is
y
i
=
ω
i
,
=
,...,
|
y
0
=
ω
0
]
Pr[
i
1
r
y
i
=
ω
i
,
=
,...,
−
|
y
0
=
ω
0
]
Pr[
i
1
r
1
y
r
y
i
=
Pr[
=
ω
r
|
=
ω
i
,
i
=
0
,...,
r
−
1]
y
r
y
r
−
1
=
Pr[
=
ω
r
|
=
ω
r
−
1
]
E
DP
C
r
(
ω
r
−
1
,ω
r
)
.
=
So applying this equality with different
r
's, we obtain the result.
We can add up all characteristics with the same
ω
0
and
ω
r
and obtain the following
result.
m
. For any
Theorem 4.6.
Let C
1
,...,
C
r
be independent Markov ciphers on
{
0
,
1
}
differential or linear characteristic
(
ω
0
,ω
r
)
, we have
r
E
DP
C
r
◦···◦
C
1
(
ω
0
,ω
r
)
=
E
DP
C
i
(
ω
i
−
1
,ω
i
)
ω
1
,...,ω
r
−
1
i
=
1
r
E
LP
C
r
◦···◦
C
1
(
ω
0
,ω
r
)
=
E
LP
C
i
(
ω
i
−
1
,ω
i
)
ω
1
,...,ω
r
−
1
i
=
1
where the expectations are over the distribution of the ciphers.
The above result links the probability of what is called a
multipath characteristic
(
ω
0
,...,ω
r
). There is indeed a cumulative
effect, although one single-path characteristic is often overwhelming.
ω
0
,ω
r
) with
single-path characteristics
(
4.3.3
Theoretical Differential and Linear Cryptanalysis
Classical studies of differential and linear cryptanalysis say that the complexity is
roughly the inverse of the appropriate DP or LP coefficient. Hence a classical (and
heuristic) argument for the security of block ciphers consists of proving that there are
no high DP or LP coefficients. We can prove the equivalence between the DP and LP
coefficients and the complexity of the attacks in a more formal way. For this we need
to have a model of the attacks. Here we use the model in terms of a distinguisher.
As depicted in Fig. 4.10, a distinguisher is an algorithm which plays with a random
oracle and which ultimately outputs 0 or 1. Given a distribution over random oracles,
we can compute the probability that the algorithm outputs 1. We say that the algorithm
distinguishes a distribution from another if the probabilities are far away.
Distinguishers are classical tools for measuring randomness. They are also called
Turing tests
.
Search WWH ::
Custom Search