Records: Best-Known Functions
Best-known cryptographic Boolean functions for given parameters, with the work that first reported each result. Organised by objective — because the criteria trade off (Siegenthaler's bound, the nonlinearity–algebraic-immunity tension, …), "best" is only meaningful once the optimised property and the fixed constraints are specified.
Work in progress — corrections welcome. This is a best-effort community record and may be incomplete or out of date. If you know a stronger result, a missing entry, or a correction to a first attribution, please message me on LinkedIn. Entries without a link cite the publication of record; ★ marks an open target.
Maximum nonlinearity
For even $n$ the maximum over all functions is the bent value $2^{n-1}-2^{n/2-1}$. Balanced functions cannot be bent, so their record is lower.
| n | all functions | balanced | first reference |
|---|---|---|---|
| 4 | 6 (bent) | 4 | Rothaus (1976); exhaustive |
| 5 | 12 | 12 | classical — covering radius of RM(1,5) |
| 6 | 28 (bent) | 26 | Rothaus (1976); balanced via the n=6 classification |
| 7 | 56 | 56 | classical — covering radius of RM(1,7) |
| 8 | 120 (bent) | 116 (best known) | Rothaus (1976); balanced: Stănică–Maitra–Clark (2004) |
Maximum nonlinearity for odd $n \ge 9$ is open (best-known values exceed the bent-concatenation bound).
Algebraic immunity
The maximum possible algebraic immunity is $\lceil n/2 \rceil$ (Meier–Pasalic–Carlet, 2004). The meaningful record is the best nonlinearity attainable together with optimal AI.
| n | optimal AI | best balanced NL at optimal AI | status / reference |
|---|---|---|---|
| 6 | 3 | 26 | balanced NL=26, AI=3 attained — n=6 classification |
| 8 | 4 | < 116 | ★ OPEN — balanced NL=116 with AI=4 is not known |
Affine equivalence class counts
| n | affine classes | with balanced functions | first reference |
|---|---|---|---|
| 3 | 3 | — | exhaustive (classical) |
| 4 | 8 | — | exhaustive (classical) |
| 5 | 48 | — | Berlekamp–Welch (1972) |
| 6 | 150,357 | 74,542 | Maiorana (1991); Fuller (2003); Braeken et al. (2005) |
A complete affine-equivalence classification for $n = 7$ is open.
Bent functions (even $n$)
| n | bent NL | number of bent functions | reference |
|---|---|---|---|
| 4 | 6 | 896 | classical |
| 6 | 28 | 5,425,430,528 | classical; 4 affine classes (this site) |
| 8 | 120 | enumerated | Langevin & Leander (2008) |
Second-order nonlinearity (covering radius of RM(2,n))
| n | max NL₂ | reference |
|---|---|---|
| 6 | 18 | Schatz (1981) |
| 7 | 40 | Gao et al. (2019) |
Multiplicative complexity ($n = 6$)
Every 6-variable Boolean function can be implemented with at most 6 AND gates; the multiplicative complexity of all 150,357 affine classes is known (Çalık, Sönmez Türan & Peralta, 2018).
★ Open targets
- $n = 8$, balanced, NL = 116 and AI = 4. NL=116 balanced functions are known (Stănică–Maitra–Clark, 2004) and AI = 4 is the optimum, but no function is known to achieve both.
- Maximum nonlinearity of functions for $n \ge 9$.
- A complete affine-equivalence classification for $n = 7$.