On Equivalence Classes of Boolean Functions - Information Security and Cryptology-ICISC 2010 - page 312

optimum algebraic degree, optimum algebraic immunity and a much better non-
linearity than all the previously obtained infinite classes of functions. However,
the lower bound they deduced is not enough to resist fast correlation attacks
[14,15]. In [8], Tu and Deng introduced another class of balanced functions with
optimum algebraic degree, optimum algebraic immunity and a provable good
nonlinearity. However, also these functions are weak against fast algebraic at-
tacks [16,21]. It seems very hard to construct Boolean functions achieving all the
necessary criteria.
Moreover, even if we can find many Boolean functions satisfying all the nec-
essary criteria, they may still be vulnerable to those attacks. In fact, Rønjom
and Cid put forward a nonlinear equivalence of Boolean functions used in a filter
generator and demonstrated that many cryptographic properties may be not in-
variant among functions in the same equivalence class by providing some special
examples [17]. Therefore, Boolean functions with good cryptographic properties
may be equivalent to some functions that are not good and we should assess the
resistance of a cipher against some types of attacks by investigating the whole
equivalence class. They gave the basic idea and many problems were left open.
In this paper, we investigate equivalence of Boolean functions more deeply
using another method and discuss the number of Boolean functions in each
equivalence class. We investigate further the cryptographic properties includ-
ing algebraic degree, algebraic immunity and nonlinearity of the equivalence
classes, and deduce tight bounds on them. We find that there are many equiv-
alence classes of Boolean functions with optimum algebraic immunity, optimum
algebraic degree and a good nonlinearity. Moreover, we discuss how to con-
struct equivalence classes with desired properties and show that it is possible to
construct practical Boolean functions such that their equivalence classes have
guaranteed cryptographic properties.
The paper is organized as follows. In Section 2, the necessary background is
established. We represent sequences and Boolean functions by generator matri-
ces in Section 3. In Section 4, we then introduce equivalence of Boolean functions
and investigate the number of Boolean functions in each equivalence class. We
investigate further the cryptographic properties including algebraic degree, al-
gebraic immunity and nonlinearity of the equivalence classes in Section 5, and
deduce tight bounds on them. In Section 6, we give some equivalence classes of
Boolean functions with optimum algebraic immunity, optimum algebraic degree
and a good nonlinearity. In Section 7, we discuss how to construct equivalence
classes with desired properties and show that it is possible to construct practical
Boolean functions such that their equivalence classes have guaranteed crypto-
graphic properties. We end in Section 8 with a few conclusions.

2 Preliminaries

2 be the n -dimensional vector space over the finite field

Let F F 2 .ABoolean

2 into

function of n variables is a function from F F 2 .Wedenoteby B n the set

of all n -variable Boolean functions.