Cryptography Reference
In-Depth Information
5 Cryptographic Properties of Equivalence Classes
Let
f ∈ B
n
and
M
k
1
+
i
1
1
b
0
,M
k
1
+
i
2
b
0
, ..., M
k
1
+
i
w
1
f
=
{
b
0
}
,
1
1
where
M
1
is the generator matrix of the sequence and 0
≤
i
1
<i
2
< ... < i
w
≤
q
−
2. Clearly, any
g
∼
f
can be represented by
M
k
2
+
i
1
j
b
0
,M
k
2
+
i
2
b
0
, ..., M
k
2
+
i
w
1
g
=
{
b
0
}
,
j
j
where 1
≤
j
≤
φ
(
q
−
1)
/n
,
M
j
is a generator matrix and 0
≤
k
2
≤
q
−
2. Let
f
=
denote the equivalence class to which
f
belongs. Since
thesamekeystreamcanbegenerated by using Boolean functions of the same
equivalence class as filter functions, to assess the resistance to a certain type of
attack, we should define the corresponding cryptographic criteria by using the
weakest equivalent function. Define
{
g
∈
B
n
|
g
∼
f
}
deg(
f
)=min
g∈f
deg(
g
)
,
AI
(
f
)=min
g∈f
AI
(
g
)
,
and
nl
(
f
)=min
g∈f
nl
(
g
)
.
To resist many kinds of attacks, deg(
f
),
(
f
)and
nl
(
f
) should all be high. More-
over, every function equivalent to
f
should have a good immunity against fast al-
gebraic attacks. Clearly, for the function
f
1
inExample1,wehavedeg(
f
1
)=1,
AI
AI
(
f
1
)=1and
nl
(
f
1
) = 0, which are very bad.
The number of variables of
f
, denoted by
var
(
f
), is the number of variables
appearing in its ANF. Define
var
(
f
)=min
g∈f
var
(
g
)
To be implemented eciently,
var
(
f
) should be small.
Lemma 1.
Let
f
∈
B
n
. Then we have
deg(
f
)
≤
n
−
1
, which is a tight bound.
Proof.
Since (
x
1
+1)(
x
2
+1)
···
(
x
n
+1) is of degree
n
,oneof
f
and
f
+
(
x
1
+1)(
x
2
+1)
···
(
x
n
+1) is of degree
n
, and the other is not. Therefore,
deg(
f
)
1. In the next section, we can find that there exist many
f
such
that deg(
f
)=
n
≤
n
−
−
1, and the result follows.
Lemma 2.
Let
f
∈
B
n
. If there is a balanced function
g
such that
g
∼
f
,then
deg
(
f
)
≤
var
(
f
)
−
1
.
Proof.
Let
var
(
f
)=
m
.If
m
=
n
, then by Lemma 1 the result follows. If
m<n
,
then there is an
h
∈
B
n
such that the number of variables appearing in its ANF
=
k
2
n−m
,where
k
is an integer. Since
h
is equivalent to a
balanced function, we have
is
m
. Therefore,
|
1
h
|
=2
n−
1
+
c
,where
c
=0or
1. Therefore,
c
=0
and
h
is balanced. We regard
h
as an
m
-variable function, that is,
h
|
1
h
|
±
∈
B
m
.Then
h
is balanced and deg(
h
)
≤
m
−
1.
Search WWH ::
Custom Search