Cryptography Reference
In-Depth Information
2
Lemma 3.
Let
f
∈
B
n
. Then we have
AI
(
f
)
≤
, which is a tight bound.
Proof.
For
n
odd,
f
and
f
+(
x
1
+1)(
x
2
+1)
···
(
x
n
+1) cannot be both balanced.
<
2
n−
1
or
<
2
n−
1
.Since
Say,
f
is not balanced. Therefore, we have
|
1
f
|
|
1
f
+1
|
2
is 2
n−
1
,there
the number of coecients of a function with degree at most
2
exists a function
g
of degree at most
such that
fg
=0or(
f
+1)
g
=0.For
n
n
n
n
even,
2
=
2
. Hence,
AI
(
f
)
≤
2
. In the next section, we can find that
2
there exist many
f
such that
AI
(
f
)=
, and the result follows.
Lemma 4.
Let
f
∈
B
n
. Then we have
2
n−
1
2
n/
2
−
1
nl
(
f
)
≤
−
−
1
.
Proof.
Clearly, the theorem is true for
n
odd. For
n
even, bent functions have
the maximum nonlinearity and the highest possible degree for a bent function
is
2
.Sinceoneof
f
and
f
+(
x
1
+1)(
x
2
+1)
···
(
x
n
+1) is of degree
n
,theycan
not be both bent. Therefore,
nl
(
f
)
≤
2
n−
1
−
2
n/
2
−
1
−
1.
Remark 1:
For small even
n
, it is easy to find equivalence classes whose non-
linearity can achieve the bound. However, for general
n
, we can not find an
equivalence class such that the bound can be achieved. We do not know whether
this bound can be tight for an infinite class and we leave this as an open problem.
Fast algebraic immunity and higher order nonlinearities of an equivalence class
canbedefinedinasimilarway:
FAI
(
f
)=min
g∈f
FAI
(
g
)and
nl
r
(
f
)=min
g∈f
nl
r
(
g
)
.
(
f
)and
nl
r
(
f
), since it may be
hard to deduce tight bounds on them. Anyway, to resist fast algebraic attacks,
FAI
(
f
) should be high.
In practice, we should use equivalence classes with good cryptographic prop-
erties and choose the functions of them which can be implied eciently as filter
functions.
FAI
We do not want to discuss the bounds on
6 Equivalence Classes with Optimum Algebraic Degree,
Optimum Algebraic Immunity and a Good Nonlinearity
B
n
and
Given an LFSR and its generator matrix
M
1
,let
f
1
∈
M
1
b
0
|
i
=0
,
1
, ...,
2
n−
1
1
f
1
=
{
−
1
}
.
This function has been investigated by many papers and has good cryptographic
properties (see [7,20,22,23]). We now investigate the equivalence class to which
f
1
belongs. Clearly, any
g ∼ f
1
can be represented by
M
k
+
i
j
i
=0
,
1
, ...,
2
n−
1
1
g
=
{
b
0
|
−
1
}
,
φ
(2
n
2
n
where 1
≤
j
≤
−
1)
/n
,
M
j
is a generator matrix and 0
≤
k
≤
−
2.
Search WWH ::
Custom Search