Cryptography Reference
In-Depth Information
4
Lower Bound on Complexity of Differential
Distinguisher for Random Permutations
In this section we present a lower bound on the complexity of differential distin-
guishers for a black-box random permutation. This allows us to fairly compare
our cipher-specific distinguisher complexities in Section 2.2 to the best possible
black-box distinguisher. Although a similar
upper
bound has been used before
(see, e.g. [13]), our result proves that it is indeed close to the best possible. To
our knowledge, such a lower bound has not been published before, and may be
of independent interest.
When the key is fixed, a block cipher becomes a permutation. An open-key
differential distinguisher with no difference in the key is valid if the complexity
of finding a differential pair is less than the complexity of finding such pair in
a random permutation. When the input and output differences are fully fixed,
in
n
-bit random permutation the complexity of finding a differential pair is 2
n
,
hence any differential distinguisher with a probability higher than 2
−n
is valid.
When the input difference is fixed, and the output difference can take values
from a set of the cardinality 2
c
, then for a random permutation, a differential
pair can be found after performing 2
n−c
encryptions. The general case when both
the input and the output differences are taken from sets of fixed cardinalities, is
discussed in the following lemma.
n
, which are closed under
Lemma 1.
Let
D
I
,D
O
denote subsets of
{
0
,
1
}
⊕
, i.e.
x
D
I
(resp.
D
O
). For any attacker making
queries to a random
n
-bit permutation
π
and its inverse
π
−
1
,thecomplexity
(measured in expected number of oracle queries) of finding a pair of inputs
(
x, y
)
,
where
x
⊕
y
∈
D
I
(respectively
D
O
)for
x, y
∈
⊕
y
∈
D
I
,
|
D
I
|
=2
c
I
, such that
π
(
x
)
⊕
π
(
y
)
∈
D
O
,
|
D
O
|
=2
c
O
,islower
min(2
2
−
2
,
2
n−
(
c
I
+
c
O
)
−
3
)
.
bounded as
Q
≥
n
into input
Proof.
Since
D
I
and
D
O
are closed under
⊕
, we may partition
{
0
,
1
}
2
n
|D
I
|
=2
c
I
,
N
=
=2
n−c
I
, such that
sets
A
1
,...,A
N
,whereeach
|
A
i
|
=
|
D
I
|
x
⊕
y
∈
D
I
for
x, y
∈
A
i
for
i
=1
,...,N
. Similarly, we have a partition into
2
n
|D
O
|
=2
c
O
,
M
=
=2
n−c
O
for all
output sets
B
1
,...,B
M
where
|
B
j
|
=
|
D
O
|
j
=1
,...,M
.
Let us define the following game
G
0
: attacker
A
has an access to a random
n
n
and its inverse
π
−
1
, making a total of
permutation oracle
π
:
{
0
,
1
}
→{
0
,
1
}
q
queries to these oracles.
In the following games
G
k
(
k
=0
,
1
,
2), let
E
k
be the following event:
A
finds
x
=
y
with
x, y
∈
A
i
and
π
(
x
)
,π
(
y
)
∈
B
j
for some
i, j
while interacting with
game
G
k
.
We show below the following upper bound:
q
2
2
n
+
q
2
n−
(
c
O
+
c
I
)
.
Pr(
E
0
)
≤
(1)
Before we explain the formal proof, we remark that the intuition for this result
is as follows. The first term
q
2
2
n
is the upper bound on the collision probability
Search WWH ::
Custom Search