Cryptography Reference
In-Depth Information
a 3 x 2 + a 2 x + a 1 by a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 ), VAR denotes number of variables ap-
pearing in ANF,
denotes algebraic immunity, DEG denotes algebraic degree
and NL denotes nonlinearity. Clearly, var ( f )=5,
AI
( f )=3,deg( f )=4and
nl ( f ) = 80. It is an equivalence class with desired properties. We now pick out a
function g such that it can be implemented eciently. Let M 1 be the generator
matrix corresponding to the primitive polynomial x 8 + x 6 + x 5 + x +1. Take
1 g =
AI
{
M 1 b 0 |
i
E
}
. From Table 1, we have var ( g )=5.Infact,
g = x 1 x 2 x 3 x 5 + x 1 x 2 x 4 x 5 + x 1 x 3 x 4 x 5 + x 1 x 2 x 3 + x 1 x 3 x 5 + x 1 x 4 x 5
+ x 2 x 3 x 4 + x 2 x 4 x 5 + x 3 x 4 x 5 + x 1 x 2 + x 1 + x 3 + x 5 .
It is simple to implement and in effect acting as a 5-variable function.
Remark 2: All functions of the equivalence class g have nonlinearity at least
80, which is greater than the lowest possible nonlinearity 58 of an 8-variable
function with optimum algebraic immunity. If we regard g as a 5-variable Boolean
function, then it is balanced and has optimum algebraic degree 4, optimum
algebraic immunity 3 and nonlinearity 10. Clearly, var ( g )= var ( g ),
AI
( g )=
AI
( g ), deg( g )=deg( g )and nl ( g )=8 nl ( g ).
Remark 3: It may be very hard to construct an infinite class of equivalence
classes satisfying all the necessary criteria. However, for a given n , the example
shows that it is possible to construct practical Boolean functions (in few variables
m<n ) such that their equivalence classes with respect to
2 have guaranteed
F
cryptographic properties.
8Con lu on
In this paper, we investigated equivalence of Boolean functions and discussed
the number of Boolean functions in each equivalence class. We investigated fur-
ther the cryptographic properties including algebraic immunity, algebraic de-
gree and nonlinearity of the equivalence classes, and deduced tight bounds on
them. We found that there are many equivalence classes of Boolean functions
with optimum algebraic degree, optimum algebraic immunity and a good non-
linearity. Moreover, we discussed how to construct equivalence classes with de-
sired properties and showed that it is possible to construct practical Boolean
functions such that their equivalence classes have guaranteed cryptographic
properties.
Previous constructed Boolean functions with good cryptographic properties
may be equivalent to some functions which are not good and we must assess the
resistance of a Boolean function against some types of attacks by investigating
the whole equivalence class. In practice, we should use equivalence classes with
good cryptographic properties and choose the functions of them which can be
implemented eciently as filter functions.
Search WWH ::




Custom Search