Cryptography Reference
In-Depth Information
We can now sum over all possible values for x
y
= α
and
f ( x )
f ( y )
= β
by
y ) pairs that satisfy these relations. It is 2 p DP f (
counting the number of ( x
,
α, β
). So
we obtain
2 p
α,β
LP f ( a
1) ( a · α ) + ( b · β ) DP f (
,
b )
=
(
α, β
)
Next we compute
2 q
α,β
1) ( a · α ) + ( b · β ) LP f (
(
α, β
)
2 q
α,β
1) ( a · α ) + ( b · β ) 2 p
u ,v
1) ( α · u ) + ( β · v ) DP f ( u
=
(
(
,v
)
2 p q
u ,v
)
α,β
DP f ( u
1) (( a u ) · α ) + (( b v ) · β )
=
,v
.
(
in which case it is 2 p + q . Thus we
The last sum is nonzero only for a
=
u and b
= v
obtain the second relation.
4.3.2
Characteristics and Markov Ciphers
Differential cryptanalysis is essentially heuristic. In order to make a formal study, we
need to have a good model for the underlying primitives. One model, based on Markov
ciphers, is due to Xuejia Lai, James Massey, and Sean Murphy.
Definition 4.3 (Lai-Massey-Murphy [111]). A random permutation C over a group
G is called a Markov cipher on G if for any a
,
b
,
x
G we have
E DP C ( a
b )
Pr[ C ( x
+
a )
C ( x )
=
b ]
=
,
where the probability and the expectation hold over the distribution of the permutation
C.
A basic example is C ( x )
K ) where C 0 is a random permutation and K is an
independent uniformly distributed key in a group.
=
C 0 ( x
+
The name “Markov cipher” refers to Markov chains. We recall that a Markov chain
is a sequence X 1 ,
X 2 ,...
of “oblivious” random variables, which means that for any i
and any a 1 ,...,
a i we have
Pr[ X i =
a i |
X 1 =
a 1 ,...,
X i 1 =
=
Pr[ X i =
a i |
X i 1 =
.
a i 1 ]
a i 1 ]
The probability that X i =
a i only depends on the “recent past” X i 1 =
a i 1 . A Markov
chain is homogeneous if for any a and b the probability
Pr[ X i =
b
|
X i 1 =
a ]
Search WWH ::




Custom Search