Information Technology Reference
In-Depth Information
It can be verified that the system of those equations has no solutions for any
choices of
b, c, d
and
e
.Thus
deg
(
fg
)
2. Therefore,
f
is 2-resistance to FAA.
Alternatively, we can directly apply Algorithm 1 to
f
for obtaining this result.
(Note that the boolean form of
f
(
x
)isgivenby
x
2
+
x
0
x
1
+
x
0
x
2
+
x
0
x
3
+
x
1
x
2
+
x
1
x
3
+
x
2
x
3
. However, in order to verify whether
f
is 2-resistance to FAA, using
the polynomial form of
f
is much easier than using the boolean form.)
≥
Another application of an enable pair (
d, r
)of
f
is to find proper values for
(
d, e
) which are in favor of FAA. For example, let
f
(
x
) be a hyper-bent function
with two trace terms from
F
2
(for the definition of hyper-bent functions,
see [25]). Then
deg
(
f
) = 4. We have verified that there are many hyper-bent
functions with the algebraic immunity 3, i.e.,
AI
(
f
) = 3. However we could have
an enable pair (
d, e
)=(2
,
3) for many such functions. In other words, there
exists some
g
with degree
d
=2suchthat
h
=
fg
F
2
8
to
=0withdegree
e
=3.Inthis
case, the required known bits from a key stream is similar for both the algebraic
attack and FAA. But the number of unknowns in FAA is much smaller than in
the algebraic attack (of course for FAA case, the required key stream bits should
be consecutive). For some results about the algebraic immunity of hyper-bent
functions, see an earlier version of this work [15].
Remark 6.
In general, it is not easy to determine whether a given function
f
is
(
d, e
) resistance against FAA or it is an enable pair of
f
, because the DFT of
h
is the convolution of the DFTs of
f
and
g
(see the definition of the convolution
at Section 2). Even it is not easy for some particular functions, for example,
hyper-bent functions. This could be an interesting question for further research.
6 Conclusions and Discussions
Courtois and Meier showed the effective algebraic attacks or the fast algebraic
attack on several concrete stream cipher systems proposed in the literature. In
order to enable the fast algebraic attack, it needs to find a function
g
with degree
at most
d
such that
h
=
fg
= 0 with degree at most
e
.IntermsoftheDFT
of sequences and boolean functions, we have showed the characterizations of
existence of those multipliers for given function
f
and a pair of integer (
d, e
).
Those results revealed that the sucient condition, given by Courtois and Meier
in [8] and [9], cannot guarantee the existence of such multipliers. An algorithm
for constructing such multipliers is given in terms of the polynomial basis. We
have provided a thorough analysis for degenerated cases of boolean functions
and how it effects the fast algebraic attack. A new concept of resistance against
the fast algebraic attack is introduced, and a set of functions in a degenerated
case is identified. Those degenerated functions are weak for resistance against
both the algebraic attack and the fast algebraic attack.
All results obtained in this paper are due to use the (discrete) Fourier trans-
form (DFT), which gives a polynomial or trace representation of a boolean func-
tion in terms of technics of analysis of pseudo-random sequences. We would like
to point out some trade-offs between the polynomial representation of a function
