Learning
A short, opinionated set of starting points for getting into Boolean functions for cryptography. This list will grow.
Core concepts
A Boolean function $f : \{0,1\}^n \to \{0,1\}$ is judged for cryptographic use against a handful of properties:
- Balance — equal numbers of zeros and ones in the truth table. A biased function leaks information.
- Nonlinearity $\mathrm{NL}(f)$ — the Hamming distance to the nearest affine function; equivalently, the distance to the first-order Reed–Muller code $\mathrm{RM}(1,n)$. High nonlinearity resists linear approximation (linear cryptanalysis).
- Algebraic degree — the degree of the ANF; the functions of degree at most $r$ form the Reed–Muller code $\mathrm{RM}(r,n)$. Low degree is exploitable.
- Correlation immunity — statistical independence of the output from small subsets of inputs; essential for combining functions in stream ciphers.
- Autocorrelation / propagation — how the function changes under input differences; related to the strict avalanche criterion.
- Algebraic immunity — resistance to algebraic attacks (a post-2003 criterion); the minimum degree of an annihilator of $f$ or $f \oplus 1$.
These criteria interact and often conflict: improving one can worsen another. Designing a function that is simultaneously good across all of them — and provably so — is the central challenge.
Key transforms
- Walsh–Hadamard transform (WHT) — the spectral tool behind nonlinearity and correlation immunity.
- Algebraic Normal Form (ANF) — the polynomial representation behind algebraic degree and algebraic immunity, computed via the Möbius transform.
- Autocorrelation — derived from the WHT by the Wiener–Khinchin theorem.
See Efficient Implementation for how these are computed in practice.
Foundational reading
- O. S. Rothaus, On Bent Functions, J. Combinatorial Theory (A), 1976 — the origin of bent functions and maximum nonlinearity.
- T. Siegenthaler, Correlation-Immunity of Nonlinear Combining Functions, IEEE Trans. Information Theory, 1984 — introduces correlation immunity and the trade-off with degree.
- W. Meier and O. Staffelbach, Nonlinearity Criteria for Cryptographic Functions, EUROCRYPT 1989.
- N. Courtois and W. Meier, Algebraic Attacks on Stream Ciphers with Linear Feedback, EUROCRYPT 2003 — introduces algebraic immunity.
- C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press — a comprehensive modern reference that, as its title signals, treats the two fields together.
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 — the standard reference for Reed–Muller codes and their covering radii.
- J. A. Maiorana, A Classification of the Cosets of the Reed–Muller Code R(1,6), Mathematics of Computation, 1991 — the coding-theory enumeration of the 150,357 affine equivalence classes for $n = 6$.
Tools
- This site's equivalence class tables — concrete examples with full property profiles for $n \le 6$.
- A modern open-source library implementing these properties is in development; details will be linked here when it is released.
- See Resources below for a curated list of openly available papers and datasets.
Resources: papers and datasets
A curated, growing list of openly available papers, datasets and references for Boolean functions in cryptography. Links point to canonical sources — author / arXiv preprints, IACR ePrint, PubMed Central, the AMS, publisher DOIs, and official code repositories. Entries marked free have free full text.
This list grows over time. If a link breaks or you have a suggestion, please message me on LinkedIn.
Textbooks & surveys
- R. O'Donnell, Analysis of Boolean Functions (2014; 2021 arXiv edition) — free. The standard modern textbook; ~500 exercises.
- C. Carlet & S. Mesnager, "Four Decades of Research on Bent Functions", Des. Codes Cryptogr. 78 (2016) — authoritative survey of bent (maximally nonlinear) functions.
- M. Đurasević, D. Jakobović, L. Mariot & S. Picek, "A Survey of Metaheuristic Algorithms for the Design of Cryptographic Boolean Functions" (2023) — free. The modern search-based / heuristic design of Boolean functions.
Classification & affine equivalence ($n \le 6$)
- J. A. Maiorana, "A Classification of the Cosets of the Reed–Muller Code R(1,6)", Math. Comp. 57 (1991) — free. First enumeration of the 150,357 affine equivalence classes for $n = 6$.
- A. Braeken, Y. Borissov, S. Nikova & B. Preneel, "Classification of Boolean Functions of 6 Variables or Less…" (ICALP 2005) — free. CI / resiliency / propagation classification.
- X.-D. Hou, "On the Number of Affine Equivalence Classes of Boolean Functions" (2020) — free. Counting AGL(n,2) orbits.
- P. Leopardi, "Classifying Bent Functions by Their Cayley Graphs" (2018) — free. Cayley-graph / extended-affine classification of bent functions up to dimension 8 (with SageMath).
- V. Gillot & P. Langevin, "Classification of Some Cosets of Reed–Muller Codes" (2022) — free. Classifies the length-128 (n = 7) Reed–Muller cosets under the affine group.
- Q.-S. Meng, M. Yang, H.-G. Zhang & Y. Liu, "The Analysis of Affinely Equivalent Boolean Functions" (2005) — free. A general algorithm to test affine equivalence and recover the transform.
Algebraic immunity & algebraic attacks
- N. Courtois & W. Meier, "Algebraic Attacks on Stream Ciphers with Linear Feedback" (EUROCRYPT 2003) — free. Introduced algebraic attacks via low-degree multiples.
- W. Meier, E. Pasalic & C. Carlet, "Algebraic Attacks and Decomposition of Boolean Functions" (EUROCRYPT 2004, LNCS 3027) — defines algebraic immunity and proves AI(f) ≤ ⌈n/2⌉. Springer / search by title.
- D. K. Dalai, K. C. Gupta & S. Maitra — "Results on Algebraic Immunity…" (INDOCRYPT 2004) and "Cryptographically Significant Boolean Functions: Construction & Analysis in Terms of Algebraic Immunity" (FSE 2005). Springer / search by title.
- P. Sarkar, "Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs" (2025) — free. A general framework for functions with provable NL / resiliency / AI trade-offs.
Multiplicative complexity & datasets
- Ç. Çalık, M. Sönmez Türan & R. Peralta, "The Multiplicative Complexity of 6-variable Boolean Functions" (2018) — free (also open access via PMC). Multiplicative complexity for all 150,357 $n = 6$ classes.
- J. Boyar, M. G. Find & R. Peralta, "On Various Nonlinearity Measures for Boolean Functions", Cryptogr. Commun. 8 (2016) — six affine-invariant measures (free author manuscript via PubMed Central).
- NIST — minimal-multiplication circuits for 6-variable predicates — free. One representative + a minimal-AND circuit per $n = 6$ class.
Higher-order nonlinearity & covering radius
- "The Covering Radius of the Reed–Muller Code RM(2,7) is 40" — free. Settles the maximum second-order nonlinearity for $n = 7$.
- "On the Covering Radius of the Second-Order Reed–Muller Code of Length 128" — free. Related second-order-nonlinearity / covering-radius work.
Foundational classics
Origin papers — widely cited; not all are freely online (check a library or the publisher).
- O. S. Rothaus, "On Bent Functions," J. Combinatorial Theory A 20 (1976) — defines bent functions.
- T. Siegenthaler, "Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications," IEEE Trans. Inf. Theory (1984) — correlation immunity and the degree trade-off.
- W. Meier & O. Staffelbach, "Nonlinearity Criteria for Cryptographic Functions" (EUROCRYPT 1989).