Analysis of Affine Equivalent Boolean Functions
for Cryptography

by

Joanne Elizabeth Fuller

Bachelor of Applied Science (Mathematics), 1998
Bachelor of Information Technology (Honours), 1999

Thesis submitted in accordance with the regulation for Degree of
Doctor of Philosophy

Information Security Research Centre
Faculty of Information Technology
Queensland University of Technology

December, 2003



i


ii


Keywords
Boolean functions, affine transformation, equivalence class, local connectivity, nonlinearity, algebraic order, autocorrelation, S-boxes, Advanced Encryption Standard.

iii

iv


Abstract
Boolean functions are an important area of study for cryptography. These functions,
consisting merely of one’s and zero’s, are the heart of numerous cryptographic systems
and their ability to provide secure communication. Boolean functions have application in a variety of such systems, including block ciphers, stream ciphers and hash
functions. The continued study of Boolean functions for cryptography is therefore
fundamental to the provision of secure communication in the future.
This thesis presents an investigation into the analysis of Boolean functions and in
particular, analysis of affine transformations with respect to both the design and application of Boolean functions for cryptography. Past research has often been limited
by the difficulties arising from the magnitude of the search space. The research presented in this thesis will be shown to provide an important step towards overcoming
such restrictions and hence forms the basis for a new analysis methodology. The new
perspective allows a reduced view of the Boolean space in which all Boolean functions
are grouped into connected equivalence classes so that only one function from each
class need be established. This approach is a significant development in Boolean function research with many applications, including class distinguishing, class structures,
self mapping analysis and finite field based s-box analysis.
The thesis will begin with a brief overview of Boolean function theory; including
an introduction to the main theme of the research, namely the affine transformation.
This will be followed by the presentation of a fundamental new theorem describing
the connectivity that exists between equivalence classes. The theorem of connectivity
will form the foundation for the remainder of the research presented in this thesis.
A discussion of efficient algorithms for the manipulation of Boolean functions will
then be presented. The ability of Boolean function research to achieve new levels
of analysis and understanding is centered on the availability of computer based programs that can perform various manipulations. The development and optimisation of
efficient algorithms specifically for execution on a computer will be shown to have a
considerable advantage compared to those constructed using a more traditional approach to algorithm optimisation.
The theorem of connectivity will be shown to be fundamental in the provision of

v


many avenues of new analysis and application. These applications include the first
non-exhaustive test for determining equivalent Boolean functions, a visual representation of the connected equivalence class structure to aid in the understanding of the
Boolean space and a self mapping constant that enables enumeration of the functions
in each equivalence class. A detailed survey of the classes with six inputs is also
presented, providing valuable insight into their range and structure.
This theme is then continued in the application Boolean function construction.
Two important new methodologies are presented; the first to yield bent functions
and the second to yield the best currently known balanced functions of eight inputs
with respect to nonlinearity. The implementation of these constructions is extremely
efficient. The first construction yields bent functions of a variety of algebraic order
and inputs sizes. The second construction provides better results than previously
proposed heuristic techniques. Each construction is then analysed with respect to its
ability to produce functions from a variety of equivalence classes.
Finally, in a further application of affine equivalence analysis, the impact to both
s-box design and construction will be considered. The effect of linear redundancy in
finite field based s-boxes will be examined and in particular it will be shown that the
AES s-box possesses complete linear redundancy. The effect of such analysis will be
discussed and an alternative construction to s-box design that ensures removal of all
linear redundancy will be presented in addition to the best known example of such an
s-box.

vi


Contents
Certificate Recommending Acceptance


i

Keywords

iii

Abstract

v

List of Figures

xi

List of Tables

xiii

Declaration

xvii

Published Papers

xix

1 Introduction

1


1.1

Aims and Outcomes of Thesis . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Overview of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2 Preliminaries
2.1

5

Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.1

Truth Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.2

Algebraic Normal Form . . . . . . . . . . . . . . . . . . . . . .


7

The Walsh-Hadamard Transform . . . . . . . . . . . . . . . . . . . . .

10

2.2.1

Nonlinearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.2.2

Correlation Immunity and Resilience . . . . . . . . . . . . . . .

12

2.2.3

Subfunction Hamming Weight . . . . . . . . . . . . . . . . . .

14

Autocorrelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3.1


The Propagation Criteria . . . . . . . . . . . . . . . . . . . . .

18

2.4

Bent Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.5

Affine Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.2

2.3

vii


2.6

2.5.1

Equivalence Classes . . . . . . . . . . . . . . . . . . . . . . . .


20

2.5.2

Invariance Analysis . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.5.3

Local Connectivity . . . . . . . . . . . . . . . . . . . . . . . . .

22

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3 Tools for Efficient Boolean Function Analysis
3.1

27

General Optimisation Issues . . . . . . . . . . . . . . . . . . . . . . . .

28

3.1.1

Algorithm Development . . . . . . . . . . . . . . . . . . . . . .


28

3.1.2

Operation Minimisation . . . . . . . . . . . . . . . . . . . . . .

29

3.1.3

ModularProgramming . . . . . . . . . . . . . . . . . . . . . . .

30

Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2.1

Boolean Function Structures . . . . . . . . . . . . . . . . . . .

31

3.2.2

The Algebraic Normal Form . . . . . . . . . . . . . . . . . . . .

32


3.2.3

The Walsh-Hadamard Transform . . . . . . . . . . . . . . . . .

34

3.2.4

The Autocorrelation Function . . . . . . . . . . . . . . . . . . .

36

3.3

A Survey of Boolean Functions of Five Inputs . . . . . . . . . . . . . .

37

3.4

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.2

4 Analysis of Affine Equivalent Boolean Functions
4.1


4.2

4.3

4.4

4.5

39

Distinguishing Affine Equivalence Classes . . . . . . . . . . . . . . . .

40

4.1.1

Basic Class Distinguishing Properties . . . . . . . . . . . . . .

40

4.1.2

m-step Analysis

. . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.1.3


Identifying the Affine Transform . . . . . . . . . . . . . . . . .

43

4.1.4

Experimental Analysis . . . . . . . . . . . . . . . . . . . . . . .

45

Equivalence Class Structures . . . . . . . . . . . . . . . . . . . . . . .

45

4.2.1

Exploration of the Class Structure . . . . . . . . . . . . . . . .

46

4.2.2

A Visual Representation . . . . . . . . . . . . . . . . . . . . . .

47

4.2.3

Bent Function Analysis . . . . . . . . . . . . . . . . . . . . . .


52

Self Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4.3.1

Self Mapping Analysis . . . . . . . . . . . . . . . . . . . . . . .

58

4.3.2

Counting Boolean Functions

. . . . . . . . . . . . . . . . . . .

59

A Survey of Boolean Functions of Six Inputs . . . . . . . . . . . . . .

60

4.4.1

Local and Global Maxima . . . . . . . . . . . . . . . . . . . . .

60


4.4.2

Highly Nonlinear and Balanced Boolean Functions . . . . . . .

61

4.4.3

Correlation Immune Boolean Functions . . . . . . . . . . . . .

62

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

viii


5 Constructing Highly Nonlinear Boolean Functions
5.1

5.2

5.3

5.4

Construction Methodologies . . . . . . . . . . . . . . . . . . . . . . . .


66

5.1.1

Random and Exhaustive . . . . . . . . . . . . . . . . . . . . . .

66

5.1.2

Algebraic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.1.3

Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

A New Construction of Bent Functions . . . . . . . . . . . . . . . . . .

69

5.2.1

Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70


5.2.2

Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.2.3

Experimental Results . . . . . . . . . . . . . . . . . . . . . . .

72

5.2.4

Class Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

Dynamic Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.3.1

Traditional Hill Climbing . . . . . . . . . . . . . . . . . . . . .

77

5.3.2


The Boolean Terrain . . . . . . . . . . . . . . . . . . . . . . . .

79

5.3.3

The New Approach . . . . . . . . . . . . . . . . . . . . . . . . .

82

5.3.4

Experimental Analysis . . . . . . . . . . . . . . . . . . . . . . .

83

5.3.5

Class Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.3.6

Modified Dynamic Hill Climbing . . . . . . . . . . . . . . . . .

87

Conclusion


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Bijective S-box Applications
6.1

65

88
91

S-box Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

6.1.1

Traditional Design Criteria . . . . . . . . . . . . . . . . . . . .

93

6.1.2

A New S-box Criterion . . . . . . . . . . . . . . . . . . . . . . .

94

6.1.3

Modern S-boxes . . . . . . . . . . . . . . . . . . . . . . . . . .


96

6.2

Redundancy in the AES S-box Functions . . . . . . . . . . . . . . . .

97

6.3

Finite Field Based S-boxes . . . . . . . . . . . . . . . . . . . . . . . . . 100

6.4

6.3.1

Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

6.3.2

Power Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.3.3

Affine Transforms . . . . . . . . . . . . . . . . . . . . . . . . . 102

Removing Linear Redundancy . . . . . . . . . . . . . . . . . . . . . . . 102
6.4.1

2-Step Tweaking . . . . . . . . . . . . . . . . . . . . . . . . . . 103


6.4.2

4-Step Tweaking . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.5

Impact on Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.6

Conclusion

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

7 Conclusion

113

7.1

Thesis Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

7.2

Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
ix


A Equivalence Class Summary


117

B Equivalence Connectivity

119

C Efficient Algorithms

121

D Bent Connection Analysis

125

E Self Mapping Analysis

129

F Survey of n = 6

133

G Bent Class Summary

137

H Modified Dynamic Hill Climbing Example

145


I

147

AES Equivalence Mappings

J Power Mapping Classes

151

K Replacement S-boxes

153

Bibliography

155

x


List of Figures
4.1

Class Connection Diagram n = 3 . . . . . . . . . . . . . . . . . . . . .

48

4.2


Class Connection Diagram n = 4 . . . . . . . . . . . . . . . . . . . . .

48

4.3

Class Connection Diagram n = 5 . . . . . . . . . . . . . . . . . . . . .

49

4.4

Highly Nonlinear Class Connection Diagram (Partial) n = 6 . . . . . .

50

xi


xii


List of Tables
2.1

Example of a Truth Table, n = 3 . . . . . . . . . . . . . . . . . . . . .

6


2.2

Calculating the ANF, n = 3 . . . . . . . . . . . . . . . . . . . . . . . .

8

2.3

Example of an ANF, n = 3 . . . . . . . . . . . . . . . . . . . . . . . .

8

2.4

Example of a WHT, n = 3 . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.5

Example of Subfunction Hamming Weight, n = 3 . . . . . . . . . . . .

16

2.6

Example of an AC, n = 3 . . . . . . . . . . . . . . . . . . . . . . . . .

17


2.7

Equivalence Class Properties, n = 3 . . . . . . . . . . . . . . . . . . .

21

2.8

Equivalence Class Properties, n = 4 . . . . . . . . . . . . . . . . . . .

21

2.9

Equivalence Class Connectivity, n = 3 . . . . . . . . . . . . . . . . . .

24

2.10 Equivalence Class Connectivity, n = 4 . . . . . . . . . . . . . . . . . .

24

3.1

ANFT Timings (ms per 10000 functions)

. . . . . . . . . . . . . . . .

34


3.2

WHT Timings (ms per 10000 functions) . . . . . . . . . . . . . . . . .

36

3.3

AC Timings (ms per 10000 functions) . . . . . . . . . . . . . . . . . .

37

3.4

Survey of Boolean Functions of 5 Input Variables . . . . . . . . . . . .

37

4.1

Basic Class Distinguishing Properties . . . . . . . . . . . . . . . . . . .

40

4.2

Basic Property Class Analysis, n = 6 . . . . . . . . . . . . . . . . . . .

41


4.3

Connectivity Class Analysis, n = 6 . . . . . . . . . . . . . . . . . . . .

42

4.4

Average Time to Identify an Affine Transform . . . . . . . . . . . . . .

45

4.5

Number Class Connections vs. Nonlinearity, n = 6 . . . . . . . . . . .

51

4.6

Time to Identify an Affine Transform n = 6 . . . . . . . . . . . . . . .

53

4.7

Timing for Bent Function Indicator Analysis . . . . . . . . . . . . . .

55


4.8

Self Mapping Analysis, n = 5 . . . . . . . . . . . . . . . . . . . . . . .

59

4.9

Self Mapping Analysis, n = 6 . . . . . . . . . . . . . . . . . . . . . . .

59

4.10 Nonlinearity Frequency Survey, n = 6 . . . . . . . . . . . . . . . . . .

59

4.11 Maximum Classes for Nonlinearity, n = 6 . . . . . . . . . . . . . . . .

60

4.12 Balanced Classes of Nonlinearity 26, n = 6 . . . . . . . . . . . . . . . .

61

4.13 CI(1) Classes of Nonlinearity 26, n = 6 . . . . . . . . . . . . . . . . . .

62

5.1


66

Survey of Random Balanced Boolean Functions . . . . . . . . . . . . .
xiii


5.2

Summary of the New Bent Function Construction . . . . . . . . . . .

73

5.3

Bent Function Equivalence Classes n = 8

. . . . . . . . . . . . . . . .

75

5.4

Lower Bounds on the Number of Bent Classes . . . . . . . . . . . . . .

76

5.5

Classification of Functions in the Boolean Terrain . . . . . . . . . . . .


79

5.6

Survey of 2-step Balanced Functions n = 4 . . . . . . . . . . . . . . . .

80

5.7

Survey of 2-step Balanced Functions n = 5 . . . . . . . . . . . . . . . .

80

5.8

Survey of 2-step Balanced Functions n = 6 . . . . . . . . . . . . . . . .

80

5.9

Comparison of Construction Techniques n = 8 . . . . . . . . . . . . . .

84

5.10 Change Sets From Dynamic Hill Climbing n = 8 . . . . . . . . . . . .

85


5.11 Dynamic Hill Climbing Function Types n = 8 . . . . . . . . . . . . . .

85

5.12 Example (8,1,6,116) Equivalence Classes . . . . . . . . . . . . . . . . .

86

6.1

Average Random Bijective S-box Properties . . . . . . . . . . . . . . .

95

6.2

Summary of Bijective S-boxes . . . . . . . . . . . . . . . . . . . . . . .

96

6.3

b0 Specification and Basic Properties . . . . . . . . . . . . . . . . . . .

97

6.4

b1 Specification and Basic Properties . . . . . . . . . . . . . . . . . . .


98

6.5

Possible Mappings Between i and j . . . . . . . . . . . . . . . . . . . .

99

6.6

8 × 8 Finite Field Inversion Based S-box Properties . . . . . . . . . . . 100

6.7

8 × 8 Finite Field Power Mapping Properties . . . . . . . . . . . . . . 101

6.8

Experimental Results From The Two-Step Tweak . . . . . . . . . . . . 106

6.9

Experimental Results From The Four-Step Tweak . . . . . . . . . . . 109

A.1 Equivalence Class Properties, n = 5 . . . . . . . . . . . . . . . . . . . 117
B.1 Equivalence Class Connectivity, n = 5 . . . . . . . . . . . . . . . . . . 119
D.1 Near Bent Classes n = 6 . . . . . . . . . . . . . . . . . . . . . . . . . . 125
D.2 Near Bent Classes n = 6, Continued . . . . . . . . . . . . . . . . . . . 126
E.1 Self Mapping Analysis, n = 5 . . . . . . . . . . . . . . . . . . . . . . . 129
E.2 Self Mapping Frequency Analysis, n = 5 . . . . . . . . . . . . . . . . . 130

E.3 Self Mapping Frequency Analysis, n = 6 . . . . . . . . . . . . . . . . . 130
F.1 Maxima Classes, Nonlinearity ≥ 26 . . . . . . . . . . . . . . . . . . . . 133
F.2 Balanced Classes of Nonlinearity 26, n = 6 . . . . . . . . . . . . . . . . 136
G.1 Bent Function Classes n = 10 (Order=2) . . . . . . . . . . . . . . . . . 137
G.2 Bent Function Classes n = 10 (Order=3) . . . . . . . . . . . . . . . . . 137
G.3 Bent Function Classes n = 10 (Order=4) . . . . . . . . . . . . . . . . . 138
G.4 Bent Function Classes n = 10 (Order=5) . . . . . . . . . . . . . . . . . 140
xiv


J.1

8 × 8 Finite Field Power Mappings . . . . . . . . . . . . . . . . . . . . 151

K.1 Frequency Distribution of Sbox Properties . . . . . . . . . . . . . . . . 153
K.2 Distribution of S-box Properties

. . . . . . . . . . . . . . . . . . . . . 154

xv


xvi


Declaration
The work contained in this thesis has not been previously submitted for a degree or
diploma at any higher education institution. To the best of my knowledge and belief,
the thesis contains no material previously published or written by another person
except where due reference is made.


Signed: . . . . . . . . . . . . . . . . . . . . . . Date: . . . . . . . . .

xvii


xviii


Published Papers
The following papers have been published as a result of the material contained in this
thesis.
[P1] A. Clark, E. Dawson, J. Fuller, J. Golic, H-J. Lee, W. Millan, S-J. Moon, and L.
Simpson. The LILI-II Keystream Generator. In Sixth Australian Conference on Information Securtity and Privacy, Proceedings, volume 2384 of Lecture Notes in Computer
Science, pages 25-39. Springer-Verlag, 2001.
[P2] J. Fuller, W. Millan and E. Dawson. Efficient Algorithms for Analysis of Cryptographic Boolean Functions. In Thirteenth Australiasian Workshop on Combinatorial
Algorithms, Proceedings, pages 133-150, 2002.
[P3] J. Fuller and W. Millan. Linear Redundancy in S-boxes. In Fast Software Encryption, Proceedings, pages 79-92, 2003.
[P4] W. Millan, J. Fuller and E. Dawson. New Concepts in Evolutionary Search for
Boolean Functions in Cryptology. To appear Congress on Evolutionary Computing,
Canberra, Australia, December 8-12, 2003.
[P5] J. Fuller, W. Millan and E. Dawson. Evolutionary Generation of Bent Functions for Cryptography. To appear Congress on Evolutionary Computing, Canberra,
Australia, December 8-12, 2003.

xix


xx



Chapter 1

Introduction
Boolean functions play an important role in modern cryptography and its ability to
meet the continuing demand for increased communications security. The study of
Boolean functions from both a theoretical and practical perspective is crucial in the
provision of secure cryptographic applications such as block ciphers, stream ciphers
and hash functions.
Since the late 1980’s there has been an increasing amount of research in this area,
however there are still many open problems with regard to the design and analysis
of Boolean functions for cryptography. The level of security achieved in applications
based on Boolean functions is measured by the quality of combinatorial properties
within the functions. The selection of Boolean functions with strong cryptographic
properties reduces the effectiveness of advanced cryptanalytic attacks, including linear
cryptanalysis [58] and differential cryptanalysis [6].

1.1

Aims and Outcomes of Thesis

This thesis presents a study of Boolean functions and in particular, analysis of an affine
transformation with respect to both the design and application of Boolean functions
for cryptography. The overall aim of the research presented in this thesis is to
improve understanding of Boolean functions by providing new perspectives
and efficient programming techniques, leading to superior search heuristics
for Boolean functions with optimal cryptographic properties.
Past research has often been limited by the difficulties associated with the vast
magnitude of the Boolean space.

The first objective of this research was


therefore to assist in overcoming such restrictions by means of a mapping methodology for Boolean functions. The theorem of connectivity, initially
introduced in Chapter 2, fulfills this objective. This theorem defines the relationship
between affine equivalent functions. It provides the means to view the Boolean space
1


as a set of connected equivalence classes rather than simply a collection of individual
functions.
An extension to this objective was to also investigate any useful applications of this
theory. Chapter 4 is dedicated to the exploration of such applications and includes
development of the first non exhaustive algorithm for the purpose of distinguishing
between affine equivalent Boolean functions, a visual representation of the Boolean
space and discovery of a self mapping constant which is able to define the size of an
equivalence class.
The ability to further study Boolean functions, and in particular explore the
Boolean space, is directly correlated with our capacity to manipulate Boolean functions in a fast and efficient manner through computer programs. The second objective of this research was therefore to investigate the optimal methods
for such manipulation and determine whether better programming techniques could be developed to facilitate their speedy implementation using
the modern computer processor. In Chapter 3 this objective is fulfilled by the
specification of efficient algorithms for calculation of the fundamental Boolean functions properties, including the Walsh-Hadamard transform, the algebraic normal form
and the autocorrelation function.
A third objective was to provide new Boolean function construction
techniques. In Chapter 5 this objective is fulfilled with the specification of a new
pseudo-random construction for bent functions. Bent functions are of particular interest due to their ability to maximise the important cryptographic property of nonlinearity. This new construction also provides the means to generate a wide variety
of bent function equivalence classes. A list of the bent function classes is included. A
second construction is also presented in Chapter 5. It is based on our ability to exploit
the inherent structure of the Boolean space and yields balanced functions of eight input variables possessing the currently best known level of nonlinearity. The functions
resulting from this construction are also subjected to equivalence class analysis to
provide an understanding of that particular region of the Boolean space.
The final objective was to examine the impact of affine equivalence

analysis in the application of Boolean functions for s-boxes. In Chapter 6
this objective is fulfilled with the specification of a new s-box design criterion; sbox linear redundancy. As well as analysis of many of the currently used s-boxes
with regard to this property. The identification of complete linear redundancy in the
Advanced Encryption Standard (AES) is made. As well analysis of this property for
any finite field based s-box is presented. In an extension to the objective, the need for
a technique to remove linear redundancy from an s-box was also identified. The final
2


section of Chapter 6 provides such a technique, as well as examples of the best known
s-boxes without linear redundancy.

1.2

Overview of Thesis

The specific suitability of a Boolean function for use in cryptography is typically determined from the evaluation of various properties of the algebraic normal form (ANF)
and Walsh-Hadamard transform (WHT) of the function. Chapter 2 will provide the
preliminary review of Boolean function theory, including their representation, the
ANF, the WHT and autocorrelation function (AC); as well as the various properties
of cryptographic importance derived from each.
This will be followed by an introduction to the main theme of the research, namely
the affine transformation, which provides the basis for grouping Boolean functions into
equivalence classes that possess similar cryptographic properties and hence provide a
reduced view of the Boolean search space that is more amenable to exploration. A
fundamental new theorem describing the connectivity that exists between equivalence
classes will be presented. The theorem of connectivity will form the foundation of
the research presented in the chapters that follow. The definition of the theorem of
connectivity was published in [P3].
The design and analysis of Boolean functions for cryptographic applications typically involves a substantial amount of computational processing. In particular, for

Boolean functions of a large number of input variables this analysis places a high
demand on computing resources. No consideration has been given, to date, in the
provision of efficient Boolean function programming techniques in the related cryptographic literature. Chapter 3 will examine a range of general optimisation techniques
that can be applied to Boolean function programs. A structure and code for an optimal implementation of Boolean functions and their associated operations, including
the WHT, ANF and AC, will be presented using the C language. This work was
published in [P2].
The theorem of connectivity will then be shown to be fundamental in the provision
of many avenues of new analysis and research. In Chapter 4 a variety of applications
of the theorem and equivalence class analysis will be discussed, including the first
non-exhaustive test for determining equivalent Boolean functions, a visual representation to aid in the understanding of the Boolean space and a self mapping constant
that enables enumeration of the equivalence classes. This chapter will present many
previously unknown sets of exhaustive data, including a survey of the Boolean space
of six input variables with respect to global maximum equivalence classes, balanced
3