196
D. M. Miller and M. Soeken
In this chapter, we present a novel algorithm that transforms the spectrum of a
function to the spectrum of the unique representative function for the equivalence
class that contains the original function. The algorithm applies for linear, affine or
spectral classification. We validate the algorithm by generating all linear, affine and
spectral equivalence classes for 1 ≤ n ≤ 5 variables. For n < 4, this is done
by an exhaustive examination of all Boolean functions. For n = 5, an exhaustive
search is not feasible due to the number of functions. One approach which uses NPN
class representative functions as the starting point generates all affine and spectral
classes but only finds 98.6% of the linear classes. We also present an alternative
approach based on function neighbourhood searching that finds all linear, affine and
spectral classes for ≤ 5 much more efficiently than the exhaustive function and NPN
examination approaches. Its one drawback is that it does not provide information on
the sizes of the classes.
For larger n, generating the equivalence classes is computationally very costly,
although we anticipate future progress using the neighbourhood search method.
Note that the transform algorithm presented here can be used for larger n to quickly
determine if two functions fall within the same equivalence class and, if they do,
to find the sequence of translations to map one to the other. Since linear, affine
and spectral equivalence are XOR based, the presented algorithm has potential
applications in cryptography [1, 2], reversible circuits [16], quantum computation
[18] and arithmetic verification [11].
In [15], Sasao et al. presented autocorrelation and spectral-based techniques to
determine if two functions are in the same affine equivalence class. The algorithm
presented here is complementary to that work as it determines a sequence of
translations to map between equivalent functions. Use of the techniques from [15]
to improve the efficiency of our approach is left for future work.
9.2 Background
9.2.1 Spectra of Boolean Functions
Definition 9.1 An n-input Boolean function f (x 1 , x 2 , . . . , x n ) is a mapping f :
B
n
→ B, where B = {0, 1}.
A Boolean function f can be represented by a ‘truth’ (column) vector, denoted
F , with 2 n entries. In this work, we use the so-called {1, −1} coding [8], where 1
denotes logic 0 and −1 denotes logic 1. For example, the majority function for 3
variables has
F =
1 1 1 −1 1 −1 −1 −1
t
(9.1)
Note that column vectors are written as transposed row vectors for space considerations.
D. M. Miller and M. Soeken
In this chapter, we present a novel algorithm that transforms the spectrum of a
function to the spectrum of the unique representative function for the equivalence
class that contains the original function. The algorithm applies for linear, affine or
spectral classification. We validate the algorithm by generating all linear, affine and
spectral equivalence classes for 1 ≤ n ≤ 5 variables. For n < 4, this is done
by an exhaustive examination of all Boolean functions. For n = 5, an exhaustive
search is not feasible due to the number of functions. One approach which uses NPN
class representative functions as the starting point generates all affine and spectral
classes but only finds 98.6% of the linear classes. We also present an alternative
approach based on function neighbourhood searching that finds all linear, affine and
spectral classes for ≤ 5 much more efficiently than the exhaustive function and NPN
examination approaches. Its one drawback is that it does not provide information on
the sizes of the classes.
For larger n, generating the equivalence classes is computationally very costly,
although we anticipate future progress using the neighbourhood search method.
Note that the transform algorithm presented here can be used for larger n to quickly
determine if two functions fall within the same equivalence class and, if they do,
to find the sequence of translations to map one to the other. Since linear, affine
and spectral equivalence are XOR based, the presented algorithm has potential
applications in cryptography [1, 2], reversible circuits [16], quantum computation
[18] and arithmetic verification [11].
In [15], Sasao et al. presented autocorrelation and spectral-based techniques to
determine if two functions are in the same affine equivalence class. The algorithm
presented here is complementary to that work as it determines a sequence of
translations to map between equivalent functions. Use of the techniques from [15]
to improve the efficiency of our approach is left for future work.
9.2 Background
9.2.1 Spectra of Boolean Functions
Definition 9.1 An n-input Boolean function f (x 1 , x 2 , . . . , x n ) is a mapping f :
B
n
→ B, where B = {0, 1}.
A Boolean function f can be represented by a ‘truth’ (column) vector, denoted
F , with 2 n entries. In this work, we use the so-called {1, −1} coding [8], where 1
denotes logic 0 and −1 denotes logic 1. For example, the majority function for 3
variables has
F =
1 1 1 −1 1 −1 −1 −1
t
(9.1)
Note that column vectors are written as transposed row vectors for space considerations.