Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-142
Multiplicative complexity bounds for chi_5^2
6 ≤ MC(chi_5^2) ≤ 7
Published 2026-09-04
For everyone
Plain summary
The Chi transformation is the nonlinear building block in the Keccak (SHA-3) hash function. In zero-knowledge proofs and secure computation, linear operations (XOR gates) are essentially free, while multiplications (AND gates) dominate the cost. Multiplicative complexity measures the minimum number of AND gates needed to evaluate a function.
Running the 5-bit Chi permutation twice in a row, written chi_5^2, previously required between 6 and 10 AND gates. This work tightens that bracket to either 6 or 7. An algebraic proof on the output polynomials establishes the lower bound of 6. A working 7-AND circuit, verified against all 32 possible 5-bit inputs, establishes the upper bound of 7.
Result
For the squared 5-bit Chi permutation chi_5^2 over GF(2)^5, multiplicative complexity in the XOR-free GF(2) XAG cost model satisfies:
6 ≤ MC(chi_5^2) ≤ 7
This improves on the prior bracket of [6,10]. The seam index for the state partition into Fix(chi_5^2) and the period-four stratum tightens from [1,5] to [1,2].
Setting and definitions
The target function is chi_5^2: GF(2)^5 → GF(2)^5, the composition of the 5-bit Keccak Chi S-box with itself. The metric MC(f) is the minimum number of 2-input AND gates over GF(2) required to compute multi-output Boolean function f in a straight-line program over {AND, XOR, NOT}, where XOR and NOT gates carry zero cost.
The state space GF(2)^5 under chi_5^2 decomposes into the fixed-point set Fix(chi_5^2) and the period-four stratum. The seam index parameterizes the structural complexity of this partition.
Method
The lower bound of 6 (evidence tier P) follows from common degree filtration. All 31 nonzero linear combinations of the output coordinate algebraic normal forms have degree 3, and the cubic module has rank 5, yielding:
3 - 2 + 5 = 6
The upper bound of 7 (evidence tier FR) derives from an explicit 7-AND circuit. An independent replay harness verified the circuit across all 32 input vectors in GF(2)^5 without referencing the SAT model, CNF representation, or selector map. Circuit descriptions and verification logs reside in zkgolf-decomp/CHI5SQ-SEAM.md.
Discussion
Prior work placed MC(chi_5^2) in [6,10]. The 7-AND synthesis eliminates candidates 8, 9, and 10, narrowing the value to two possibilities. Resolving the remaining gap requires either constructing a valid 6-AND circuit or proving no such circuit exists over GF(2).
For everyone — the takeaway
What this means
Multiplication gates dominate the running time and hardware footprint of zero-knowledge proof systems and multi-party computation protocols. Reducing the AND count for hash functions like Keccak cuts proof generation overhead. Bounding two consecutive Chi rounds to at most 7 AND gates leaves only a single-gate gap to the theoretical minimum and rules out higher implementation costs.
Attribution and prior art
Prior art: Prior bracket was [6,10].
Register references
- Register Entry: MF-142
- Receipt artifact:
zkgolf-decomp/CHI5SQ-SEAM.md
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 0 of 1 receipt files bundled (1 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.