Cryptography Reference
In-Depth Information
does not depend on
i
. (Transition probabilities do not depend on “time.”) The following
property links Markov ciphers and Markov chains.
Theorem 4.4.
Let C
1
,...,
C
r
be independent Markov ciphers on a group G, let x
1
and
x
2
be two plaintexts, and let Y
j
=
Y
i
Y
2
−
Y
1
C
i
◦···◦
C
1
(
x
j
)
for j
=
1
,
2
and
=
Y
r
is a Markov chain. If the distribution of
the C
i
's is the same, the Markov chain is furthermore homogeneous.
Y
0
for i
=
1
,...,
r . The sequence
,...,
Y
1
Y
i
−
2
Proof.
Let
E
be the event
{
=
ω
1
,...,
=
ω
i
−
2
}
We h av e
Y
i
Y
i
−
1
Pr[
=
ω
i
|
=
ω
i
−
1
,
E
]
Y
i
Y
i
−
1
1
Y
i
−
1
=
Pr[
=
ω
i
,
=
y
|
=
ω
i
−
1
,
E
]
y
=
ω
i
] Pr[
Y
i
−
1
=
Pr[
C
i
(
y
+
ω
i
−
1
)
−
C
i
(
y
)
=
y
]
1
y
due to the independence between
Y
i
−
1
and
C
i
. This last probability is equal to
E
(DP
C
i
(
ω
i
−
1
,ω
i
)) due to the definition of Markov ciphers. Therefore we have
Y
i
Y
i
−
1
Y
i
Y
i
−
1
Pr[
=
ω
i
|
=
ω
i
−
1
,
E
]
=
Pr[
=
ω
i
|
=
ω
i
−
1
]
.
The homogeneous property is trivial.
The Markov cipher notion is a good model for differential cryptanalysis, as the
following result shows.
Theorem 4.5.
With the notations of the previous theorem, we now consider x
1
and x
2
as random, independent, and uniformly distributed. For any differential characteristic
=
(
ω
0
,...,ω
r
)
we have
E
Pr
x
1
,
x
2
=
ω
0
]
r
E
DP
C
i
(
ω
i
−
1
,ω
i
)
y
i
y
0
[
=
ω
i
,
i
=
1
,...,
r
|
=
i
=
1
where the expectations are over the distribution of the ciphers.
We notice that the probability of the left-hand term is the probability of the differential
characteristic, which depends on the key, and we take the expectation over the distribu-
tion of the key. People usually make the hypothesis of
Stochastic equivalence
, which
says that what holds on average over the keys holds for any key, so that we can remove
the expectations in the above result and have
r
y
i
y
0
DP
C
i
(
Pr
x
1
,
x
2
[
=
ω
i
,
i
=
1
,...,
r
|
=
ω
0
]
≈
ω
i
−
1
,ω
i
)
.
Search WWH ::
Custom Search