Information Technology Reference
In-Depth Information
(b) the assertion that
fg
=0
for all nonconstant
g
∈
S
d
0
is true if and only if
fS
d
=
{
f,
0
}
where
S
d
0
is the subset of
S
d
which consists of the functions
with the zero constant term.
Some questions for resistance against the fast algebraic attack (FAA) arise from
the degenerated cases in Corollary 3. We will analysis those cases in depth and
introduce some new concepts related to those new phenomena in the next section.
In the following, using Theorem 2, we provide an algorithm for determin-
ing whether there exists a function
g
with
deg
(
g
)
≤
d
such that
fg
=0with
deg
(
fg
)
d, e < n
.Ifthere
exists such a multiplier
g
, the algorithm outputs
g
and
fg
. Otherwise, it outputs
g
=0and
fg
= 0. For simplicity, in the algorithm, if it is needed, a subset
of
≤
e
foragiven
f
and two integers
d
and
e
with 1
≤
F
n
is also regarded as a matrix in which each row is a function in the set,
represented as a 2
n
-dimensional binary vector.
Algorithm 1.
An Algorithm for Finding a Low Degree Multiplier
Input:
f ∈F
n
, a function from
F
2
n
to
F
2
;
1
d, e < n
;and
t
(
x
)=
x
n
+
n−
1
i
=0
≤
t
i
x
i
,t
i
∈
F
2
, a primitive polynomial over
F
2
of
degree
n
.
Output:
g
∈F
n
with
deg
(
g
)
≤
d
and
h
=
fg
with
h
=0
and
deg
(
h
)
≤
e
if
there exist such
g
and
h
.Otherwise,outputs
g
=0
and
h
=0
.
Procedure
1. Randomly select an initial state
(
a
0
,a
1
,...,a
n−
1
)
,a
i
∈
F
2
,andcompute
n−
1
t
j
a
j
+
i
,i
=0
,
1
,...,
2
n
a
n
+
i
=
−
1
−
n.
j
=0
(Note
a
=(
a
0
,...,a
2
n
−
2
)
is a binary
m
-sequence of degree
n
.)
2. Compute
k
, each coset leader modulo
2
n
−
1
,and
n
k
, the size of
C
k
.Set
I
=
{
(
k, n
k
)
|
k
∈
Γn
}
. (Recal l that
Γ
(
n
)
is the set consisting of all coset
leaders modulo
2
n
−
1
.)
3. Set
m
=
max
{
d, e
}
. Establish
S
m
:
P
0
=(1
,
1
,...,
1)
;
for
0
m
do
Compute
a
(
k
)
=(
a
0
,a
k
,...,a
k
(2
n
−
2)
)
,a
k
-decimation of
a
, then apply the
shift operator to the decimated sequence.
Loading
P
k
, defined by (19), as an
n
k
×
=
k
in
Γ
(
n
)
with
w
(
k
)
≤
2
n
sub-matrix of
S
m
for all
k
with
m
.
4. Using the Gauss elimination, find the rank of
fS
d
, represented as an
0
≤
w
(
k
)
≤
|
fS
d
|×
2
n
matrix, and a maximal linearly independent set of
fS
d
,say
D
d
.
