Cryptography Reference
In-Depth Information
0, we can upper-bound EDP
C
1
(
w
We consider
v
w
=
0. If
w
=
0 and
y
=
,
x
⊕
v
) and
EDP
C
3
(
y
,
z
⊕
x
)by
p
. Then we have
p
2
x
EDP
(
C
1
,
C
2
,
C
3
)
(
EDP
C
2
(
x
v
,
≤
,
⊕
w
zy
)
y
w
)
which is 0 because
C
2
is a permutation. If
w
=
0 and
y
=
0, we have
EDP
(
C
1
,
C
2
,
C
3
)
(
EDP
C
1
(
w
)EDP
C
2
(
z
v
w
,
zy
)
=
,
z
⊕
v
,
y
⊕
w
)
which is less than
p
2
. The
w
=
0 and
y
=
0 case is similar. Finally, if
w
=
y
=
0, the
term is the only remaining one, and the EDP
C
2
(
x
x
=
v
,
y
⊕
w
) term must be zero
because
x
=
v
=
0 and
y
⊕
w
=
0 and
C
2
is a permutation.
As an application, Kaisa Nyberg and Lars Knudsen invented the PURE cipher.
4
Its core is defined as a three-round Feistel cipher with round functions
F
K
(
x
)
=
f
(
g
(
E
(
x
)
+
K
))
where
f
: GF(2
33
)
32
32
GF(2
33
)
→{
0
,
1
}
consists of discarding one bit,
E
:
{
0
,
1
}
→
is an injective linear mapping, and
g
: GF(2
33
)
GF(2
33
) is defined by
g
(
x
)
x
3
.
→
=
2
−
61
and ELP
max
≤
2
−
61
.
We can prove that EDP
max
≤
The PURE cipher is provably secure against differential and linear cryptanalysis.
This is however an ad hoc construction which is weak against another attack: the
interpolation cryptanalysis
. Let us consider
r
=
r
+
1 rounds. Let
F
i
=
=
F
K
i
and
C
(
F
1
,...,
F
r
). For
X
=
(
A
1
,...,
A
32
,
c
1
,...,
c
32
) with constant values
c
i
, let
Y
=
C
(
X
)
=
(
B
1
,...,
B
64
). A classical result of the finite field theory tells us that
x
→
x
2
x
3
can be expressed as a
multivariable polynomial of degree 2 in terms of input bits. For
i
is a linear function. Hence, every output bit of
g
:
x
→
≥
32,
B
i
is a Boolean
A
32
with algebraic degree at most 2
r
−
2
if
r
−
function of
A
1
,...,
32. (This means
that
B
i
can be expressed as a polynomial in terms of
A
j
's with a total degree at most
2
r
−
2
.) If
2
≤
is an affine space with dimension 2
r
−
2
{
X
1
,...,
X
2
2
r
−
2
}
+
1, and
Y
j
=
C
(
x
j
),
then
Y
j
=
0 from the property of polynomial functions (see the lemma below). This
property enables us to make a distinguisher between
r
rounds and a truly random
permutation (see Ref. [95]).
Lemma 4.11.
Let f
(
x
1
,...,
x
n
)
be a polynomial of total degree d over a field
K
.IfA
is a subset of
K
n
with an algebraic structure of affine space of dimension d
+
1
, then
f
(
x
1
,...,
x
n
)
=
0
.
(
x
1
,...,
x
n
)
∈
A
This can easily be proved by induction.
4
This is the topic of Exercise 4.3 on p. 132.
Search WWH ::
Custom Search