Boolean Functions for Cryptography

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$)
naverage nonlinearityaverage degreeaverage acmax
621.55.027.9
747.96.043.8
8103.57.067.6
9219.28.0102.8
10456.89.0154.7
11941.910.0231.2
121926.311.0343.4
133916.212.0507.8
147927.413.0747.7
1515995.514.01098.4
1632199.115.01609.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:

  1. Start from a quadratic bent function, $x_1x_{n/2+1} \oplus x_2x_{n/2+2} \oplus \cdots$.
  2. Try adding ANF terms of degree 3 up to a chosen maximum (at most $n/2$), starting from a random position.
  3. 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.
  4. 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)
nmax degreebent functionsms per function
83120
84170.59
103190.63
104321.56
105511.76
123372.16
124566.07
1257817.97
1266619.58
1437110.01
14457111.04
145118110.25
146187165.32
147146404.27
16311352.38
164165248.36
165292332.22
166365930.08
1674242361.32
1683393947.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.

ndegree 234567total classes found
81310–––14
10171127––46
1217203256–116
141926437139189
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:

shapeimprovementstaticreduction
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:

nonlinearityrandomstrong HCweak HCdynamic HC
881000
901000
925000
9416000
9638000
9895000
100191000
102318000
104267000
10664500
108419000
1100505380
112030096213
114000613
116000374

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:

Try a simple version yourself: the Class Graph Explorer animates a hill climb through the classes for $n \le 5$.