Cryptography Reference
In-Depth Information
Any
f
∈
B
n
can be uniquely represented as a multivariate polynomial in
F
2
[
x
1
,
···
,x
n
],
f
(
x
1
, ..., x
n
)=
a
K
x
k
,
k∈K
K⊆{
1
,
2
,...,n}
which is called its algebraic normal form (ANF). The algebraic degree of
f
,
denoted by deg(
f
), is the number of variables in the highest order term with
nonzero coecient.
A Boolean function is ane if there exists no term of degree strictly greater
than 1 in the ANF and the set of all ane functions is denoted by
A
n
.
Let
2
2
.
The cardinality of 1
f
, denoted by
wt
(
f
), is called the Hamming weight of
f
.
The Hamming distance between two functions
f
and
g
, denoted by
d
(
f, g
), is
the Hamming weight of
f
+
g
. We say that an
n
-variable Boolean function
f
is
balanced if
wt
(
f
)=2
n−
1
.
Let
f
1
f
=
{
x
∈
F
|
f
(
x
)=1
}
,
0
f
=
{
x
∈
F
|
f
(
x
)=0
}
B
n
. The nonlinearity of
f
, denoted by
nl
(
f
), is its distance from the
set of all
n
-variable ane functions, i.e.,
∈
nl
(
f
)= min
g∈A
n
d
(
f, g
)
.
The
r
-order nonlinearity, denoted by
nl
r
(
f
), is its Hamming distance to the set
of all
n
-variable functions of degree at most
r
.
The nonlinearity of an
n
-variable Boolean function is upper bounded by 2
n−
1
−
2
n/
2
−
1
, and a function is said to be bent if it can achieve this bound. Clearly,
bent functions exist only for
n
even and it is known that the algebraic degree of
a bent function is upper bounded by
2
[18].
B
n
is called an annihilator of
f
if
fg
= 0, and the algebraic immunity of
f
, denoted by
For any
f
∈
B
n
, a nonzero function
g
∈
(
f
), is the minimum
value of
d
such that
f
or
f
+ 1 admits an annihilator of degree
d
.Itisknown
that the algebraic immunity of an
n
-variable Boolean function is upper bounded
by
AI
2
[19].
To resist algebraic attacks, a Boolean function
f
used in stream ciphers should
have a high algebraic immunity, which implies that the nonlinearity of
f
is also
not very low since [26]
n
.
AI
(
f
)
−
2
−
1
nl
(
f
)
≥
2
i
i
=0
Many
bounds
on
higher
order
nonlinearities
have
also
been
deduced
[27,28,29,30,31,32].
Let
f
B
n
. If there are functions
g
of low degree and
h
of reasonable degree
such that
fg
=
h
,then
f
is considered to be weak against fast algebraic attacks.
The fast algebraic immunity of an
n
-variable Boolean function
f
, denoted by
FAI
∈
(
f
), is defined as
FAI
(
f
)= min
g∈B
n
{
2
AI
(
f
)
,
deg
g
+deg(
fg
)
}
,
Search WWH ::
Custom Search