Information Technology Reference
In-Depth Information
5. Apply the Gauss elimination to the following matrix whose entries are
given by
⎡
⎤
D
d
S
e
⎣
⎦
.
If the rank of the above matrix is equal to
t
+
s
where
|D
d
|
=
t
and
|S
e
|
=
s
,
set
g
=0
and
h
=0
, then go to Step 6. Otherwise, find
c
i
,i
=1
,...,t
such
that
t
s
c
i
fg
i
+
c
t
+
i
h
i
=0
.
i
=1
i
=1
Set
g
=
i
=1
c
i
g
i
and
h
=
i
=1
c
t
+
i
h
i
.
6. Return
g
and
h
.
Remark 3.
The algorithm can also be applied to a boolean representation of
f
. However, establishing
S
m
using the polynomial basis is more ecient than
establishing
S
m
using the boolean function basis:
1
,x
1
,...,x
n
,x
1
x
2
,...,
x
c
,...,x
i
1
x
i
2
...x
i
m
,
for all
c
n
∈
F
2
with
w
(
c
)
≤
m,
due to Step 3 which needs only the shift operation for the group of
n
k
−
1rows
of
S
m
for each
k
∈
Γ
(
n
)with
w
(
k
)
≤
m
.
Remark 4.
Algorithm 1 can be applied to find
g
such that
fg
= 0, i.e., the
annihilators of
f
, when Step 5 is replaced by Step 5': If
, then return
g
= 0 which represents no annihilators with degree at most
d
. Otherwise, finding
|
D
|
=
|
S
d
|
c
i
such that
i
=1
c
i
fg
i
=0,set
g
=
i
=1
c
i
g
i
, and return
g
. When Algorithm 1
is restricted to compute annihilators of
f
, the computational complexity of this
algorithm is approximately determined by the cost for applying the Gaussian
elimination algorithm to a
T
d
×
2
n
matrix.
Remark 5.
Any algorithm for finding annihilators in the boolean basis can be
extended to compute low degree multipliers in the polynomial basis, for example,
Algorithms 1 and 2 in [17]. We omit the details for the sake of space.
However, the algorithm that we proposed here is easier to characterize the
degenerated cases and analysis of the resistance against FAA, which will be
given in the next section. Another aspect is that it is easier to apply to those
functions which directly are given in their polynomial forms.
5 Degenerated Cases and Resistance against FAA
In order to launch an ecient FAA attack, one needs to find a multiplier
g
with
deg
(
g
)
≤
d
such that
h
=
fg
=0with
deg
(
h
)
≤
e
for some pair (
d, e
)whichis
in favor of FAA.
Definition 2.
For a given function
f
and an integer pair
(
d, r
)
, assume that
thereexistssomefunction
g
with
deg
(
g
)
≤ d
such that
h
=
fg
=0
with
deg
(
h
)
≤
e
. Then we say that the pair
(
d, r
)
is an
enable pair of
f
.
