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