Constructions and Search
Recognising a good Boolean function is easy; finding one is hard. There are $2^{2^n}$ functions of $n$ inputs, and the cryptographically strong ones are a vanishingly small fraction. This page describes the two construction methods developed in the PhD research (Chapter 5 of the thesis), the picture of the "Boolean terrain" that motivated them, and the history of heuristic search at QUT. Every example function below links to the Function Analyser, so you can check it yourself.
Why random search fails
A million random balanced functions were generated for each $n$. On average they fall far short of the best known values: for $n = 8$, the average nonlinearity is 103.5, against a best known 116.
Average properties of random balanced functions ($10^6$ samples per $n$)
| n | average nonlinearity | average degree | average acmax |
|---|---|---|---|
| 6 | 21.5 | 5.0 | 27.9 |
| 7 | 47.9 | 6.0 | 43.8 |
| 8 | 103.5 | 7.0 | 67.6 |
| 9 | 219.2 | 8.0 | 102.8 |
| 10 | 456.8 | 9.0 | 154.7 |
| 11 | 941.9 | 10.0 | 231.2 |
| 12 | 1926.3 | 11.0 | 343.4 |
| 13 | 3916.2 | 12.0 | 507.8 |
| 14 | 7927.4 | 13.0 | 747.7 |
| 15 | 15995.5 | 14.0 | 1098.4 |
| 16 | 32199.1 | 15.0 | 1609.1 |
1. A new construction of bent functions
Bent functions have the maximum possible nonlinearity for even $n$. The construction rests on a simple property proved in the thesis: split a function's truth table into two halves along any non-zero direction $\omega$. Then
a function is bent if and only if, in every non-zero direction, exactly one of the two halves is balanced.
Together with the bound $\deg f \le n/2$ for bent functions, this gives a fast filter:
- Start from a quadratic bent function, $x_1x_{n/2+1} \oplus x_2x_{n/2+2} \oplus \cdots$.
- Try adding ANF terms of degree 3 up to a chosen maximum (at most $n/2$), starting from a random position.
- Discard any term that breaks the weight or "half balanced" conditions in the $n$ unit directions, which is cheap to test. Only the survivors need a full Walsh transform.
- Keep the term if the result is still bent, and repeat to build a chain of bent functions of increasing degree.
On a 500 MHz Pentium III in 2003 this produced bent functions for $n = 8$ to $16$, at speeds from under a millisecond to about 4 seconds per function.
Construction results (bent functions produced per run)
| n | max degree | bent functions | ms per function |
|---|---|---|---|
| 8 | 3 | 12 | 0 |
| 8 | 4 | 17 | 0.59 |
| 10 | 3 | 19 | 0.63 |
| 10 | 4 | 32 | 1.56 |
| 10 | 5 | 51 | 1.76 |
| 12 | 3 | 37 | 2.16 |
| 12 | 4 | 56 | 6.07 |
| 12 | 5 | 78 | 17.97 |
| 12 | 6 | 66 | 19.58 |
| 14 | 3 | 71 | 10.01 |
| 14 | 4 | 57 | 111.04 |
| 14 | 5 | 118 | 110.25 |
| 14 | 6 | 187 | 165.32 |
| 14 | 7 | 146 | 404.27 |
| 16 | 3 | 113 | 52.38 |
| 16 | 4 | 165 | 248.36 |
| 16 | 5 | 292 | 332.22 |
| 16 | 6 | 365 | 930.08 |
| 16 | 7 | 424 | 2361.32 |
| 16 | 8 | 339 | 3947.06 |
How many classes does it reach?
A construction is only as useful as the variety it produces: any one function generates its whole affine class, so the real measure is how many classes a method reaches. The thesis classified the output by affine equivalence, giving lower bounds on the number of bent classes. For comparison, $n = 6$ has exactly 4.
| n | degree 2 | 3 | 4 | 5 | 6 | 7 | total classes found |
|---|---|---|---|---|---|---|---|
| 8 | 1 | 3 | 10 | – | – | – | 14 |
| 10 | 1 | 7 | 11 | 27 | – | – | 46 |
| 12 | 1 | 7 | 20 | 32 | 56 | – | 116 |
| 14 | 1 | 9 | 26 | 43 | 71 | 39 | 189 |
The 14 bent classes found for $n = 8$, with example functions
These were the counts reached in 2003; they are lower bounds, not complete classifications.
2. The Boolean terrain
Hill climbing improves a function by small truth-table changes. Changing one bit moves every Walsh value by $\pm 2$; changing two bits (one 0 and one 1, so the weight is unchanged) moves each by $-4$, $0$ or $+4$, so nonlinearity rises by 2, stays level, or falls by 2. For each function, the possible two-bit changes therefore split into an improvement set, a static set and a reduction set. Which sets are non-empty describes the local shape of the landscape:
| shape | improvement | static | reduction |
|---|---|---|---|
| peak | – | – | ✓ |
| plateau | – | ✓ | – |
| ridge | – | ✓ | ✓ |
| trough | ✓ | – | – |
| saddle point | ✓ | – | ✓ |
| valley | ✓ | ✓ | – |
| slope | ✓ | ✓ | ✓ |
Surveys of this terrain for $n = 4$, $5$ and $6$, and of the functions met during searches at $n = 8$, show that most functions sit on slopes, but as nonlinearity rises the improvement set shrinks to nothing and highly nonlinear functions sit on ridges. That is exactly where ordinary hill climbing stops.
3. Dynamic hill climbing
Strong hill climbing (Millan, Clark and Dawson, 1997) only accepts improving moves, so it halts at the first ridge. Weak hill climbing (1999) also accepts level moves, but rarely finds the few improving ones. Dynamic hill climbing switches between the two: it takes an improving move whenever one exists, and otherwise walks along the ridge with level moves (up to a limit), checking for a new improving move at every step.
For balanced functions of 8 inputs, over 1,000 runs of each method:
| nonlinearity | random | strong HC | weak HC | dynamic HC |
|---|---|---|---|---|
| 88 | 1 | 0 | 0 | 0 |
| 90 | 1 | 0 | 0 | 0 |
| 92 | 5 | 0 | 0 | 0 |
| 94 | 16 | 0 | 0 | 0 |
| 96 | 38 | 0 | 0 | 0 |
| 98 | 95 | 0 | 0 | 0 |
| 100 | 191 | 0 | 0 | 0 |
| 102 | 318 | 0 | 0 | 0 |
| 104 | 267 | 0 | 0 | 0 |
| 106 | 64 | 5 | 0 | 0 |
| 108 | 4 | 190 | 0 | 0 |
| 110 | 0 | 505 | 38 | 0 |
| 112 | 0 | 300 | 962 | 13 |
| 114 | 0 | 0 | 0 | 613 |
| 116 | 0 | 0 | 0 | 374 |
Average final nonlinearity (computed from the table): random 101.6, strong 110.2, weak 111.9, dynamic 114.7. Only dynamic hill climbing reached 114 and 116, and it reached 116, the best known for balanced 8-input functions, in 374 of 1,000 runs.
Every nonlinearity-116 function found sat at an isolated peak: no two-bit change kept it at 116. The thesis noted that if this holds for all such functions, then balanced functions with nonlinearity 118 cannot exist. Whether they do remains an open problem.
Classifying the output found 4,797 distinct classes of balanced nonlinearity-116 functions. A modified version that preserves correlation immunity produced 1-resilient (8, 1, 6, 116) functions; ten example classes are below. The same approach, combined with concatenation, gave a 12-input 1-resilient function of degree 10 and nonlinearity 1,992, the best known at the time (since improved).
Ten (8, 1, 6, 116) classes: balanced, 1-resilient, degree 6, nonlinearity 116
A short history of heuristic search at QUT
The Information Security Research Centre at QUT was an early centre for heuristic design of cryptographic Boolean functions:
- 1997. W. Millan, A. Clark and E. Dawson introduce hill climbing ("Smart Hill Climbing Finds Better Boolean Functions", SAC 1997) and a genetic algorithm ("An Effective Genetic Algorithm for Finding Highly Nonlinear Boolean Functions", ICICS 1997) for cryptographic Boolean functions. PhD theses by Millan (1997) and Clark (1998) follow.
- 1998–1999. Heuristic design of balanced functions (Eurocrypt 1998) and weak hill climbing (ACISP 1999), from the same group.
- 2000. J. A. Clark and J. L. Jacob introduce simulated annealing for Boolean function design (ACISP 2000).
- 2002. Efficient algorithms for Boolean function analysis (Fuller, Millan and Dawson, AWOCA 2002): the fast transforms that made large-scale searches and the exhaustive $n = 6$ classification practical. See Efficient Implementation.
- 2003. "Evolutionary Generation of Bent Functions for Cryptography" (Fuller, Millan and Dawson) and "New Concepts in Evolutionary Search for Boolean Functions in Cryptology" (Millan, Fuller and Dawson), both at the IEEE Congress on Evolutionary Computation. The PhD thesis (December 2003) presents the bent construction, the terrain classification and dynamic hill climbing above, and analyses the output of each construction by affine equivalence class.
Try a simple version yourself: the Class Graph Explorer animates a hill climb through the classes for $n \le 5$.