Information Technology Reference
In-Depth Information
It can be proved [19,7] that, for every positive real
c
such that
c
2
log
2
(
e
)
>
1,
where
e
is the base of the natural logarithm, (e.g. for
c
= 1), almost all Boolean
functions satisfy
n
i
r
cn
r/
2
2
n/
2
π
1
/
4
r
(2
r
+1)
/
4
2
3
/
4
,
2
n−
1
2
n−
1
2
n−
1
nl
r
(
f
)
≥
−
c
≈
−
(1)
2
i
=0
and that the probability that
nl
r
(
f
) is smaller than this expression is asymptot-
ically at most
O
(2
(1
−
log
2
e
)
i
=0
(
i
)
)when
n
tends to
.
This proves that the best possible
r
-th order nonlinearity of
n
-variable Boolean
functions is asymptotically equivalent to 2
n−
1
, and that its difference with 2
n−
1
is polynomially (in
n
, for every fixed
r
) proportional to 2
n/
2
. The proof of this
fact is obtained by counting the number of functions having upper bounded
r
-
th order nonlinearity (or more precisely by upper bounding this number) and it
does not help obtaining explicit functions with non-weak
r
-th order nonlinearity.
∞
2.3 Lower Bounds on the Higher Order Nonlinearity of a
Boolean/Vectorial Boolean Function with Given Algebraic
Immunity
The algebraic immunity [45] of a Boolean function
f
quantifies the resistance
to the standard algebraic attack of the pseudo-random generators using it as a
nonlinear function.
Definition 1.
Let
f
:
F
2
→
F
2
be an
n
-variable Boolean function. We call
an annihilator of
f
any
n
-variable function
g
whose product with
f
is null (i.e.
whose support is included in the support of
f
+1
, or in other words any function
which is a multiple of
f
+1
). The algebraic immunity of
f
is the minimum
algebraic degree of all the nonzero annihilators of
f
or of
f
+1
.
We shall denote the algebraic immunity of
f
by
AI
(
f
). Clearly, since
f
is an
annihilator of
f
+1(and
f
+ 1 is an annihilator of
f
)wehave
AI
(
f
)
≤
d
◦
f
.
≤
2
. This bound is tight. Also,
we know that almost all Boolean functions have algebraic immunities close to
this optimum; more precisely, for all
a<
1,
AI
(
f
) is almost surely greater than
n
As shown in [22], we always have
AI
(
f
)
2
ln
a
ln 2
when
n
tends to infinity, see [27].
n
2
−
Remark
. Few functions are known (up to ane equivalence) with provably op-
timum algebraic immunities: the functions whose construction is introduced in
[26] (see in [11] their further properties) and some functions which are symmetric
(that is, whose outputs depend only on the Hamming weights of their inputs)
[25,4] or almost symmetric (see [10]). These functions have some drawbacks: all
of them have insucient nonlinearities and many are non-balanced (i.e. their
output is not uniformly distributed over
F
2
). Moreover, the functions studied in
[25,4], and to a slightly smaller extent the functions introduced in [26], have not
