Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-154
Exact multiplicative complexity of chi_5^2
MC(chi_5^2) = 7, closing the [6,7] bracket at the top, with eps_5 = 10 - 7 = 3 = eps_4
Published 2026-09-04
For everyone
Plain summary
The Keccak cryptographic hash function, used in the SHA-3 standard, uses a core nonlinear step called chi. In circuit design and advanced cryptography, circuit cost is measured by multiplicative complexity: the smallest number of AND gates (multiplications) needed to evaluate a function when XOR additions cost nothing. Previous work placed the cost of running the 5-bit chi operation twice in a row, written as chi_5^2, between 6 and 7 AND gates. This work shows that no 6-gate circuit exists, proving the exact cost is 7 AND gates. Before this computation, no exact multiplicative complexity for any iterated chi layer had appeared in the literature or in NIST records.
Result
For the 5-bit Keccak nonlinear permutation chi_5, the two-round composition chi_5^2 has exact multiplicative complexity:
MC(chi_5^2) = 7
This closes the [6, 7] bracket from MF-142 at the upper bound. The width-5 checkpoint-erasure dividend evaluates to eps_5 = 10 - 7 = 3, matching eps_4 = 3, leaving the seam index at [1, 2] unchanged.
Setting and definitions
Let chi_5 : GF(2)^5 -> GF(2)^5 denote the standard 5-bit Keccak S-box mapping x = (x0, x1, x2, x3, x4) to y, where y_i = x_i + (x_{i+1} + 1) * x_{i+2} with indices modulo 5. The map chi_5^2 is the two-round iterate chi_5 o chi_5.
The multiplicative complexity MC(f) of a Boolean map f over GF(2) is the minimum number of two-input AND gates required to compute f in an XOR-AND graph with free affine additions and scalar constants. The checkpoint-erasure dividend at width n is eps_n = 2 * n - MC(chi_n^2).
Method
Establishing MC(chi_5^2) = 7 requires a lower bound of 7 and an explicit 7-AND witness circuit.
The lower bound MC(chi_5^2) >= 7 was proved by ruling out all 6-AND circuits across two independent, solver-free exhaustive enumeration engines:
- Symmetry-reduced engine: explored 31 rotation-orbit first-gate representatives across 47 search nodes.
- Unconstrained engine: explored all 155 first-gate classes without symmetry reductions across 235 search nodes.
Both searches completed with zero valid circuits at K = 6. Recall fidelity was validated against positive controls:
- Full 25/25 recovery of planted 6-AND width-5 instances.
- Recovery of known benchmark circuits: chi_4^2 at K = 5 and chi_5^-1 at K = 6.
The upper bound MC(chi_5^2) <= 7 was confirmed by recovering the 7-AND circuit from MF-142, emitting a netlist, and executing an exhaustive 32/32 truth-table replay against the chi_5^2 specification with zero mismatches.
The evidence tier is FC (solver-free exhaustion) for the lower bound and FR (full replay) for the upper bound.
Discussion
This result rules out all 6-AND implementations of chi_5^2, fixing its exact cost at 7 AND gates.
Because MC(chi_5^2) = 7, the width-5 checkpoint-erasure dividend is eps_5 = 10 - 7 = 3, matching eps_4 = 8 - 5 = 3 from MC(chi_4^2) = 5. The MF-142 seam index remains [1, 2].
Prior-art status: APPARENTLY-NEW. No exact multiplicative complexity for an iterated chi layer had been published, and NIST lists no chi row as re-confirmed on 2026-09-01.
For everyone — the takeaway
What this means
AND gates dominate evaluation costs in secure multi-party computation, zero-knowledge proofs, and fully homomorphic encryption. Proving that two rounds of 5-bit Keccak chi require 7 multiplications instead of 6 gives protocol designers an exact, optimal baseline for implementation efficiency.
Attribution and prior art
Prior art: This appears to be a new result. As re-confirmed on 2026-09-01, no exact MC of any chi iterate has been published, and NIST lists no chi row.
Register references
- Entry: MF-154
- Prior entries referenced: MF-142, MF-134
- Receipt artifacts:
- chi/out_s04_chi5pow2_k6.json
- out_s04b_chi5pow2_k6_nosym.json
- out_s06_controls.json
- out_s07_chi5pow2_k7.json
- out_s09_chi5pow2_k7_replay.json
- circuit_chi5pow2_k7.txt
- Prior art: APPARENTLY-NEW (NIST unlisted, re-confirmed 2026-09-01)
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 6 of 6 receipt files bundled (3 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.