Information Technology Reference
In-Depth Information
where
e
i
's and
k
i
's are not all zero. Thus,
D
d
∪
S
e
is linear dependent over
F
2
,
which completes the proof.
From the sequence version of
fS
d
and the DFT of the sequences in
S
j
,wecan
express the result of Theorem 2 in a sequence version. Let
{
X
k
}
be the DFT of
{
x
t
}
in the following corollary.
Corollary 1.
(
Existence of Low Degree Multipliers
,SequenceVersion)
For a given binary sequence
u
with period
N
2
n
|
−
1
,andapairofintegers
(
d, e
)
which satisfy that
1
d, e < n
,let
D
d
be a maximal linearly independent set
of
u
S
d
. Then there exists a sequence
b
with
B
k
=0
for all
k
in the range of
w
(
k
)
>d
such that
c
=
ub
≤
=0
with
C
k
=0
for all
k
in the range of
w
(
k
)
>e
if and only if
D
d
∪
S
e
is linearly dependent over
F
2
.
Another characterization of low degree multipliers of
f
is through the Reed-
Muller code. The Reed-Muller code of length 2
n
and order
r
,1
n
, denoted
as
R
(
r, n
), is the set consisting of the binary sequences with trace representation
f
(
x
) given by (11), i.e.,
≤
r
≤
f
(
x
)=
w
(
k
)
≤r
(
f
(0)
,f
(1)
,f
(
α
)
,...,f
(
α
2
n
−
2
))
Tr
n
1
(
A
k
x
k
)
R
(
r, n
)=
{
|
}
.
(25)
Therefore,
R
(
r, n
)=
<
S
r
>
(26)
where
S
r
is defined in (20). Using (26), together with Theorem 2, the following
assertion is immediate.
Corollary 2.
For a given
f
∈F
n
, and two integers
d
and
e
,
1
≤
d, e < n
,there
exists a function
g
with
deg
(
g
)
e
if and
only if the intersection of
fR
(
d, n
)
and
R
(
e, n
)
contains functions which are not
constant, i.e.,
≤
d
such that
h
=
fg
=0
with
deg
(
h
)
≤
{
0
,
1
}⊂
fR
(
d, n
)
∩
R
(
e, n
)
and
|
fR
(
d, n
)
∩
R
(
e, n
)
|
>
2
where
0
is understood as the all zeros vector or zero, which depends on the
context, a similar notation for 1.
Note.
For the cryptographic properties of Reed-Muller codes, the reader is re-
ferred to [5].
Note that there is an extremely degenerated case, i.e.,
fS
d
=
{
f,
0
}
.Fromthe
proof of Theorem 2, in this case, for all nonconstant
g
S
d
,
fg
=0.Thus,we
have established the following corollary for the case
fg
=0.
∈
Corollary 3.
For a given
f
∈F
n
and
0
<d<n
,
(a) there exists some
g
=0
with
deg
(
g
)
≤
d
such that
fg
=0
if and only if
|
D
|
<
|
S
d
|
,and
