Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-130
Exact multiplicative complexity of all powers of the width-four chi map
MC(χ₄⁰)=0, MC(χ₄)=4, MC(χ₄²)=5, MC(χ₄³)=4; MC(χ₄^k)=5 for even k≥2, MC(χ₄^k)=4 for odd k≥1
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity counts the minimum nonlinear multiplication gates needed to evaluate a Boolean function when linear operations like additions cost nothing. Cryptographic designs like the Keccak chi layer rely on these transformations, and evaluating repeated rounds inside zero-knowledge proofs or arithmetic circuits makes these nonlinear gates the primary cost bottleneck.
This entry gives the exact multiplicative complexity for every power of the 4-bit chi map over binary arithmetic. The identity map at power zero takes zero multiplications. The base mapping takes four. Squaring it takes five, and cubing it takes four. Beyond the second power, the map enters an alternating period-two cycle: every higher even power matches the square and costs five multiplications, while every higher odd power matches the cube and costs four. The full sequence of exact costs is 0, 4, 5, 4, 5, 4, ... repeating indefinitely.
Result
Let χ₄ : GF(2)⁴ → GF(2)⁴ denote the standard width-four chi transformation. Under the GF(2) XOR-free multiplicative complexity model MC, the complexity of the powers χ₄^k for k ≥ 0 is:
MC(χ₄⁰) = 0 MC(χ₄) = 4 MC(χ₄²) = 5 MC(χ₄³) = 4
For all k ≥ 2: MC(χ₄^k) = 5 when k is even MC(χ₄^k) = 4 when k is odd
The sequence of costs across all non-negative integer powers k = 0, 1, 2, 3, 4, 5, ... is exactly 0, 4, 5, 4, 5, 4, ...
Setting and definitions
The cost metric MC(f) of a multi-output Boolean function f : GF(2)⁴ → GF(2)⁴ is the minimum number of binary AND gates in an XOR-AND graph (XAG) computing f over GF(2), where XOR and NOT gates have zero cost.
The width-four mapping χ₄ acts on 4-bit state vectors x = (x₀, x₁, x₂, x₃) with cyclic indexing modulo 4: xᵢ ↦ xᵢ ⊕ ((xᵢ₊₁ ⊕ 1) ∧ xᵢ₊₂)
The power χ₄^k denotes the k-fold functional composition of χ₄ with itself, where χ₄⁰ is the identity on GF(2)⁴.
Method
The bounds follow from semigroup analysis and replay of explicit witness circuits:
- Semigroup collapse: Exhaustive evaluation across GF(2)⁴ shows that χ₄² is an idempotent retraction onto a 10-state image. Thus χ₄⁴ = χ₄², giving χ₄^(2m) = χ₄² and χ₄^(2m+1) = χ₄³ for all m ≥ 1.
- Lower bounds: Symbolic nonlinear rank and algebraic degree yield MC(χ₄) ≥ 4, MC(χ₄²) ≥ 5, and MC(χ₄³) ≥ 4.
- Upper bounds and verification: Explicit witness circuits match each lower bound over the 16-row domain. Verification passes at tier P + FR with independent FC corroboration.
Discussion
Determining MC(χ₄^k) reduces entirely to the algebraic collapse of the semigroup generated by χ₄. Because χ₄² acts as an idempotent retraction on its 10-state image, the semigroup contains only four distinct functions: χ₄⁰, χ₄¹, χ₄², and χ₄³. Higher powers produce no new functions on GF(2)⁴.
The result applies strictly under the GF(2) XAG model with free linear operations. Extensions to widths other than four are not covered in this entry.
For everyone — the takeaway
What this means
If you build zero-knowledge proofs or arithmetic circuits using iterated Keccak-style chi layers, this result pins down the exact circuit size. Applying the 4-bit chi map twice requires five multiplication gates, but applying it three or more times never takes more than five. Every odd power after the first drops back to four multiplications because the map collapses onto a smaller set of active states. These circuit sizes are provably minimal, so there's no need to search for smaller circuits when chaining higher powers.
Register references
- Entry ID: MF-130
- Primary Source:
zkgolf-decomp/FREE-06.md - Verdict Source:
zkgolf-decomp/FREE-VERIFY.md(SOUND) - Receipt:
zkgolf-decomp/free-06-scratch/chi-square-symbolic.receipt.json(SHA-2568ce501a3ee462356e92213a96e612d4153dd9ad38f537bc00ee20491d31f38cb) - Receipt:
zkgolf-decomp/free-06-scratch/chi4-semigroup.receipt.json(SHA-256ab8532e0c809a4d9318015be95fede8d0287ebfc6cd4f224fca1fdb2975596be)
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.