Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-134
Exact joint multiplicative complexity of chi_n and its square
MC(chi_n, chi_n^2) = 2n for all n >= 4
Published 2026-09-04
For everyone
Plain summary
Evaluating both the cryptographic transform chi_n and its two-round composition chi_n^2 at the same time requires exactly 2n nonlinear multiplication gates (AND gates) for any width n >= 4. The chi function is the core nonlinear component of Keccak and SHA-3, where AND gates dominate hardware and proof verification costs.
When a circuit must output both the one-round intermediate state and the two-round final state, no multiplications can be shared between the rounds. At width n = 4, evaluating chi_4^2 alone takes 5 multiplications, but evaluating chi_4 and chi_4^2 together takes 8. The 3-gate savings achieved in a standalone two-round evaluation come entirely from dropping intermediate checkpoint constraints rather than sharing gates across rounds.
Result
For all integers n >= 4, the joint multiplicative complexity of chi_n and its composed square chi_n^2 satisfies:
MC(chi_n, chi_n^2) = 2n.
This establishes the following structural properties:
- The checkpoint-erasure dividend satisfies eps_n = 2n - MC(chi_n^2) >= 0 for all n >= 4.
- At width n = 5, the dividend is eps_5 = 10 - MC(chi_5^2).
- At width n = 4, MC(chi_4, chi_4^2) = 8 while MC(chi_4^2) = 5, demonstrating that the full 3-gate composition defect stems from projection release with zero sharing across exposed layers.
Setting and definitions
Let chi_n be the Keccak nonlinear mapping on GF(2)^n, defined coordinate-wise by x_i + (x_(i+1) + 1)x_(i+2) with indices taken modulo n.
Let chi_n^2 denote the composed mapping chi_n ∘ chi_n.
The multiplicative complexity MC(T) of an explicit vector target T is the minimum number of binary AND gates (multiplications in GF(2)) needed by a straight-line Boolean circuit computing all coordinate functions of T from primary inputs, with unlimited linear XOR and XNOR operations. The joint target (chi_n, chi_n^2) requires simultaneous evaluation of the n-bit intermediate vector and the n-bit composed vector.
The checkpoint-erasure dividend is eps_n = 2n - MC(chi_n^2), measuring the complexity gap between joint round evaluation and isolated composed evaluation.
Method
The result is classified under evidence tier P (symbolic proof) with exhaustive rank verification across small widths:
- Algebraic degree separation: the coordinate functions of chi_n generate n quadratic leader classes of algebraic degree 2. The coordinate functions of chi_n^2 generate n cubic leader classes of algebraic degree 3.
- Rank lower bound: because the quadratic and cubic leader classes occupy disjoint algebraic degree layers, the joint nonlinear quotient space spanned by the coordinate outputs has rank 2n. Consequently, MC(chi_n, chi_n^2) >= 2n.
- Upper bound construction: computing chi_n requires n multiplications, and passing its outputs into a second literal chi_n layer requires n multiplications, producing the joint target in 2n multiplications. Thus MC(chi_n, chi_n^2) = 2n.
- Independent rank verification confirmed the linear independence condition for all widths n <= 13.
The proof was independently derived by three seats: COUNCIL3-INV-TURING.md, COUNCIL3-REF-GODEL.md, and COUNCIL3-REF-ARNOLD.md. Verification artifact zkgolf-decomp/COUNCIL3-VERIFY-EXPOSURE.md validated all three derivations as SOUND with zero solver seconds consumed.
Discussion
This theorem sets an exact lower bound for the explicit joint vector target (chi_n, chi_n^2). The bound characterizes circuit-level minima for exposed joint targets; it does not imply that three specific gates can be subtracted from an arbitrary unoptimized implementation.
The equality MC(chi_n, chi_n^2) = 2n shows that preserving intermediate states across multi-round Keccak evaluations—such as state checkpoints in proof systems—prevents algebraic sharing across round boundaries. Multi-round gate reductions (such as dropping from 8 to 5 multiplications at n = 4) require unconstraining the intermediate state so the circuit can compute the composition via a compressed projection.
The register records no prior-art position.
For everyone — the takeaway
What this means
Zero-knowledge proof systems and secure hardware designs often try to merge consecutive cryptographic rounds to save multiplications. This result shows that if a system must output or check both the single-round state and the two-round state of Keccak's chi function, no AND gates can be shared between the rounds.
Any multiplication savings in multi-round execution come entirely from discarding the intermediate values. Preserving those checkpoints forces the circuit to pay the full cost of two separate layers.
Register references
- Register Entry: MF-134
- Verification Receipt: zkgolf-decomp/COUNCIL3-VERIFY-EXPOSURE.md
- Seat Derivation Receipts:
- COUNCIL3-INV-TURING.md
- COUNCIL3-REF-GODEL.md
- COUNCIL3-REF-ARNOLD.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 4 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.