Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-081
A lower bound for the multiplicative complexity of the AES S-box
13 ≤ MC(S_AES) ≤ 32
Published 2026-08-29
For everyone
Plain summary
The AES S-box maps 8 input bits to 8 output bits. In the register's multiplicative complexity model, any circuit implementing this forward S-box requires at least 13 AND gates.
This bound is mathematically valid, but it is not an AES-specific discovery. Evaluating the standard 2n−3 lower bound for (n,n) Boolean functions at n = 8 yields 2·8−3 = 13. The proof uses a rank-plus-degree obstruction, which pairs algebraic degree with linear independence. A known construction by Boyar and Peralta achieves an upper bound of 32 AND gates. A targeted search found no published lower bound specific to the AES S-box, though the literature sweep was not exhaustive.
Result
For the forward AES S-box S_AES,
MC(S_AES) ≥ 13.
The bound follows from applying the rank-plus-degree obstruction to the 8-bit to 8-bit AES S-box. The value matches the general 2n−3 repeated-degree lower bound for n = 8:
2·8−3 = 13.
The register also notes the upper bound MC(S_AES) ≤ 32 from the Boyar–Peralta construction. The lower bound of 13 is sound, but it represents an evaluation of a known general formula rather than an AES-specific record.
Setting and definitions
Let S_AES denote the forward AES S-box treated as an (8,8) Boolean function. Multiplicative complexity MC counts the minimum number of AND gates required to compute the function over GF(2).
The rank-plus-degree obstruction establishes a 2n−3 lower bound on MC for (n,n) Boolean functions. This yields a lower bound only: it proves no circuit can use 12 or fewer AND gates, while the known upper bound remains 32.
Method
The transfer study applied the rank-plus-degree obstruction to S_AES to derive MC(S_AES) ≥ 13.
A subsequent literature comparison identified the rank-plus-degree lemma as the vector form of the classical repeated-degree argument, matching 2n−3 at n = 8.
The original entry listed prior art as unchecked. A follow-up search consisting of two targeted web queries found no published AES-specific lower bound on multiplicative complexity, while confirming the standard 32-AND upper bound. The query scope did not include a systematic crawl of eprint or DBLP.
Discussion
The lower bound MC(S_AES) ≥ 13 is mathematically sound. The correction strictly addresses novelty: 13 is the evaluation of the classical 2n−3 repeated-degree bound for (8,8) functions, as formalized by Boyar and Find, not an AES-tailored result.
The targeted literature search found no tighter AES-specific lower bound. Because the search was restricted to two web queries without systematic eprint or DBLP indexing, it establishes that claiming an AES-specific novelty record is unsupported, rather than proving no tighter bound exists in the literature.
A substantial gap remains between the 13-AND lower bound and the 32-AND Boyar–Peralta upper bound.
For everyone — the takeaway
What this means
Every circuit computing the AES S-box requires at least 13 AND gates. It may well require more: the best known recipe uses 32.
The number 13 comes directly from a formula that applies to every 8-input, 8-output Boolean function. AES is simply one example of that rule. The bound is verified, but it is a general floor rather than an AES-specific breakthrough.
Attribution and prior art
Prior art: The novelty claim for this result is withdrawn: this bound is an instance of the known general 2n-3 repeated-degree lower bound for (8,8)-functions, not a new AES-specific record. A literature search found no published lower bound specific to AES. Sources: arXiv:1407.6169
Register references
- MF-081.
zkgolf-transfer-studies\03-mc-lower-bounds-tcount\REPORT.md§1.zkgolf-transfer-studies\03-mc-lower-bounds-tcount\REPORT.md§2.2.- Boyar–Find, [arXiv:1407.6169](https://arxiv.org/abs/1407.6169).
- Boyar–Peralta, the 32-AND upper bound named by the register.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 1 of 1 receipt files bundled (11 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-27The novelty claim for MF-081 is withdrawn: a prior-art search confirmed that its lower bound of 13 for n = 8 re-derives the general 2n−3 lower bound for an (n,n)-function by Boyar–Find (2014, arXiv:1407.6169). The calculated bound 2·8−3 = 13 itself still stands.
- 2026-08-29Published on this site.