What this programme is about
Ciphers rely on nonlinear substitutions, called S-boxes, to stop attackers from breaking encryption with linear algebra. Each nonlinear step, usually an AND gate or finite-field product, costs circuit area in hardware, adds proof overhead in zero-knowledge systems, and demands costly Toffoli gates on fault-tolerant quantum computers. This programme measures the exact minimum number of nonlinear multiplications—the multiplicative complexity—needed to run cipher S-boxes and finite-field operations in binary circuits and reversible quantum networks. It focuses on the χ permutation powering Keccak and Ascon, small finite-field operations, and standard block-cipher S-boxes. For engineers and cryptanalysts outside pure circuit complexity, these counts establish hard physical floors. An exact count settles the gate budget for masked hardware, prices the quantum circuit required to invert a cipher, and marks when further logic optimization cannot succeed.
What has been settled
Forward χ needs exactly n AND gates for width n ≥ 3 MF-129, while χ₅² takes 7 gates MF-154, closing the [6, 7] bracket MF-142. Odd powers of χ₄ cost 4 gates and even powers cost 5 MF-130. The k-window law fixes joint complexity of k iterates to kn through k = ⌊n/2⌋ MF-156; joint χ_n and χ_n² takes 2n gates MF-134. Iterate degrees follow j+1 up to ⌊n/2⌋, with prior art credited to Kriepke–Kyureghyan, Schoone–Daemen, Liu et al., and Biryukov et al. MF-157. For odd n, inverse χ takes 3(n−1)/2 products, reaching 9 at n=7 MF-098 and superseding earlier bounds [MF-078, MF-079]. The six-AND χ₅⁻¹ circuit is prior art MF-079. Strict syntactic symmetry sets inverse-χ costs at 3, 10, and 21 for widths 3, 5, and 7, imposing taxes of 0, 4, and 12 [MF-116, ML-058]. Rowwise replacement cannot cut 12-round Keccak-p[1600,12] below 19,200 products ML-064, and inverse-χ exactness yields zero savings ML-066.
Exact NCT networks for χ₅ need at least 6 Toffoli gates MF-080. Reversible synthesis failures eliminated cyclic p6 modules via wrong row-0 assignments ML-017, the acyclic p7 route after 786,430 checks ML-018, and the χ₀₁ catalyst on the p7 tile MF-010.
GF(8) multiplication takes 6 AND gates MF-128, superseding model brackets MF-120; GF(4)'s cost of 3 is prior art. General GF(2^k) multiplication requires at least ⌈5k/2⌉ - 2 gates MF-147. GF(16) inversion costs 5 gates MF-168, and GF(16) multiplication takes 9 products in quadratic models MF-167. All 16 optimal 4-bit S-box classes are settled: 11 cost 5 gates and 5 cost 4; PRINCE costs 5, while PRESENT, GIFT, RECTANGLE, Piccolo, and SKINNY cost 4 MF-176. The AES S-box lower bound of 13 is the known general 2n-3 bound, withdrawing novelty MF-081. Three whole-function floors hold with one non-affine rescope MF-135, and five lower-bound conjectures were disproved MF-174.
What is still open
Three main complexity brackets remain unresolved across algebraic fields and iterated permutations.
In finite fields, unrestricted multiplication in GF(2^4) is bracketed between 8 and 9 AND gates [ML-076, MF-167]. Resolving whether 8 gates suffice has been reduced to 3-form transfer analysis or exhaustive circuit search ML-076. Inversion in GF(2^5) also remains open within [7, 14] gates, supported by quadratic-model witness costs of 7 for x^3 and x^5 MF-168.
For iterated Keccak layers, two-round permutations leave brackets of [8, 12] for χ₆² and [9, 14] for χ₇² [ML-082, MF-155]. Exhaustive gate-budget exclusions confirm the lower floors of 8 and 9 gates, while explicit circuit constructions give the upper bounds MF-155. In quantum synthesis, alternate prefix branches for the Toffoli acyclic p7 route remain open following exhaustion of the 3-gate start ML-018.
How to read the evidence
Receipted computational artifacts and exhaustive checks dominate this register, backed by certified machine proofs and written deductions. Exhaustive checks and machine certificates give total confidence on exact gate numbers and structural obstructions at small widths. Receipted entries supply concrete circuit witnesses and replayable logs that confirm upper bounds directly. Unreceipted legacy searches document exhausted branches and warrant fresh verification before new synthesis attempts.