Information Technology Reference
In-Depth Information
and
xy
denotes the product of
x
and
y
in
F
2
n
. Indeed we have
xF
inv
(
x
)=1for
every nonzero
x
. As observed in [23], we have also
w
H
(
h
(
x, F
inv
(
x
))) = 0 for the
bilinear functions
h
(
x, y
)=
tr
(
a
(
x
+
x
2
y
)) and
h
(
x, y
)=
tr
(
a
(
y
+
y
2
x
)) where
a
is any nonzero element, and for the quadratic functions
h
(
x, y
)=
tr
(
a
(
x
3
+
x
4
y
))
and
h
(
x, y
)=
tr
(
a
(
y
3
+
y
4
x
)). These properties are the core properties used in
the tentative algebraic attack on the AES by Courtois and J. Pieprzyk [23].
Let us study now
nl
s,r
(
F
inv
):
Proposition 7.
For every ordered pair
(
s, r
)
of strictly positive integers, we
have:
-
nl
s,r
(
F
inv
)=0
if
r
+
s
n
;
-
nl
s,r
(
F
inv
)
>
0
if
r
+
s<n
.
In particular, for every ordered pair
(
s, r
)
of positive integers such that
r
+
s
=
n
≥
1
, we have
nl
s,r
(
F
inv
)=2
.
Proof.
If
r
+
s
−
,
2
n
≥
n
then there exists an integer
d
∈{
1
,
···
−
2
}
whose 2-
weight
w
2
(
d
)isatmost
r
andsuchthat
w
2
(2
n
−
1
−
d
)=
n
−
w
2
(
d
)
≤
s
(taking
for instance
w
2
(
d
)=
r
which implies
w
2
(2
n
−
1
−
d
)=
n
−
r
≤
s
). Then taking
f
(
x
)=
tr
(
ax
2
n
−
1
−d
),
a
F
2
n
and
g
(
x
)=
tr
(
ax
d
), we have, by construction
∈
f
F
inv
=
g
and since
f
has degree at most
s
and
g
has degree at most
r
,we
deduce that
nl
s,r
(
F
inv
) = 0 (indeed, there exists at least one
a
◦
∈
F
2
n
such that
f
is not constant, since otherwise we would have
tr
(
ax
2
n
−
1
−d
) = 0 for every
F
2
n
while we know that
tr
(
ax
2
n
−
1
−d
) = 0 for every
a
∈
F
2
n
and every
x
∈
a
=0).
If
r
+
s<n
, then consider any Boolean functions
f
of degree at most
s
and
g
of degree at most
r
. Let us consider their representation as polynomials in one
variable:
∈
F
2
n
is impossible when
x
2
n
2
n
−
1
−
1
f
i
x
i
;
g
j
x
j
;
f
(
x
)=
g
(
x
)=
f
i
,g
j
∈
F
2
n
i
=0
j
=0
where
f
i
=0forevery
i
such that
w
2
(
i
)
>s
and
g
j
=0forevery
j
such
that
w
2
(
j
)
>r
. Assume that
g
=
f
F
inv
.Wehavethen
f
0
=
g
0
. Without
loss of generality, we can assume that
f
0
=
g
0
= 0. Since the composition of
the function
x
i
◦
with
F
inv
(on the right) equals the function
x
2
n
−
1
−
i
for every
=0
,
2
n
1, and since
s<
2
n
i
−
−
1, the equality
f
◦
F
inv
=
g
is then equivalent
to the fact that the function
2
n
−
1
i
=0
−i
+
2
n
−
1
j
=0
f
i
x
2
n
−
1
g
j
x
j
is null. For every
i
=0suchthat
w
2
(
i
)
≤
s
and every
j
=0suchthat
w
2
(
j
)
≤
r
, the inequalities
w
2
(2
n
r
imply that 2
n
=
j
. According to
the uniqueness of the representation as a polynomial in one variable, this implies
that
f
=
g
= 0. Hence we have
nl
s,r
(
F
inv
)
>
0.
In particular, if
r
+
s
=
n
−
1
−
i
)
≥
n
−
s>r
and
w
2
(
j
)
≤
−
1
−
i
−
1, then let:
x
i
and
g
(
x
)=
x
i
.
f
(
x
)=
0
<i<
2
n
−
1
/w
2
(
i
)
≤
s
0
≤
i<
2
n
−
1
/w
2
(
i
)
≤
r
Note that
f
and
g
are both Boolean, since
f
2
i
=
f
i
and
g
2
i
=
g
i
for every
i
=0
,
2
n
−
1and
f
0
,f
2
n
−
1
,g
0
,g
2
n
−
1
∈
F
2
.Thenwehave(
f
◦
F
inv
)(
x
)+
