Information Technology Reference
In-Depth Information
There is a relation between the Reed-Muller code and the row vectors of
P
k
,
which will be introduced in the next section.
4 Characterizations of Boolean Functions with Low
Degree Multipliers
Assume that a boolean function
f
employed in a cipher system is not of low
degree.
Definition 1.
Given
f
a boolean function in
n
variables, i.e.,
f
∈F
n
,apairof
positive integers
d<deg
(
f
)
and
e
, if there exists some function
g
with
deg
(
g
)
≤
d
such that the product
h
=
fg
=0
or
h
=(
f
+1)
g
=0
with
deg
(
h
)
≤
e
,then
g
is said to be a
low degree multiplier
of
f
.
In this section, we will show how to characterize those multipliers. We first
present a sucient condition for the existence of low degree multipliers. Following
this approach, we establish a sucient and necessary condition for the existence
of low degree multipliers, which also yields an algorithm to construct them. It
follows that Assertion A in Section 1 is not true from the results we derived in
this section. Let
S
d
=
{
row vectors of
P
k
| k ∈ Γ
(
n
)
,w
(
k
)
≤ d}
(20)
where
P
k
is defined by (19). Then
S
d
can be considered as either the set consisting
of all the functions in the polynomial basis with
w
(
k
)
r
or the set consisting
of all boolean monomial terms of degrees less than or equal to
d
, i.e., we can
rewrite
S
d
as follows.
≤
S
d
=
Π
k
w
(
k
)
≤d
where
Π
k
is defined in (17). Then we have
|
S
d
|
=
T
d
, defined by (3) in Section 1.
F
n
of degree
d
is a linear combination of functions
Notice that any function in
in
S
d
over
F
2
. From Section 3.2, the sequence version of
S
d
, still denoted by
S
d
,
is given by
L
i
a
(
k
)
S
d
=
{
|
0
≤
i<n
k
,w
(
k
)
≤
d
}
(21)
where
n
k
is the size of the coset
C
k
or the degree of the minimal polynomial of
a
(
k
)
.Foragiven
f
∈F
n
,wedenote
fS
d
=
{
f
(
x
)
·
g
(
x
)
|
g
∈
S
d
}
.
(22)
From (21), the sequence version of (22) is given by
u
S
d
=
{
u
·
b
|
b
∈ S
d
}
(23)
where
u
is the sequence associated with
f
(
x
), defined by (16) in Section 2, and
the multiplication of two sequences is the term-by-term multiplication. (Note.
We keep the notation
S
d
for both functions and sequences, and the exact meaning
depends on the context.)
