Boolean Functions for Cryptography

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.

nall functionsbalancedfirst reference
46 (bent)4Rothaus (1976); exhaustive
51212classical — covering radius of RM(1,5)
628 (bent)26Rothaus (1976); balanced via the n=6 classification
75656classical — covering radius of RM(1,7)
8120 (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.

noptimal AIbest balanced NL at optimal AIstatus / reference
6326balanced NL=26, AI=3 attained — n=6 classification
84< 116★ OPEN — balanced NL=116 with AI=4 is not known

Affine equivalence class counts

naffine classeswith balanced functionsfirst reference
33—exhaustive (classical)
48—exhaustive (classical)
548—Berlekamp–Welch (1972)
6150,35774,542Maiorana (1991); Fuller (2003); Braeken et al. (2005)

A complete affine-equivalence classification for $n = 7$ is open.

Bent functions (even $n$)

nbent NLnumber of bent functionsreference
46896classical
6285,425,430,528classical; 4 affine classes (this site)
8120enumeratedLangevin & Leander (2008)

Second-order nonlinearity (covering radius of RM(2,n))

nmax NL₂reference
618Schatz (1981)
740Gao 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