Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-129
Exact multiplicative complexity of the forward χ mapping
MC(χ_n) = n for every n ≥ 3, with coordinate rule χ_i = Rule210_{i+1}
Published 2026-09-04
For everyone
Plain summary
The forward χ transformation is the nonlinear building block in the Keccak hashing standard. When using this function in zero-knowledge proofs or privacy-preserving cryptography, additions modulo two (XOR gates) are essentially free, while bit multiplications (AND gates) drive circuit size and proving time.
This work proves that evaluating an n-bit forward χ transformation strictly requires n AND gates for every register width n ≥ 3. No algebraic shortcut can lower this cost below one multiplication per coordinate. The transformation also maps directly to elementary cellular automaton Wolfram rule 210, up to a shift in output index.
Result
For every integer n ≥ 3, the multiplicative complexity of the forward χ transformation χ_n over GF(2) in the XOR-free additive model is:
MC(χ_n) = n
Modulo affine functions, the n output coordinates of χ_n consist of the n distinct cyclic degree-two monomials x_{i+1}x_{i+2} for i ∈ {0, ..., n-1} (indices taken modulo n). These monomials span a subspace of dimension n modulo affine functions. Because the standard coordinatewise decomposition evaluates each coordinate using one distinct quadratic product, it achieves the lower bound with exactly n AND gates.
Under standard lexicographic indexing for three-input Boolean functions, the coordinate truth table evaluates to 11010010_2 = 210. The mapping corresponds to elementary cellular automaton Wolfram rule 210 shifted by one index:
χ_i = Rule210_{i+1}
Setting and definitions
Let GF(2) denote the field of two elements. The multiplicative complexity MC(f) of a Boolean function f : GF(2)^n → GF(2)^m is the minimum number of two-input AND gates required to compute f in an XOR-AND graph (XAG) with unrestricted XOR, NOT, and constants.
The forward χ mapping χ_n : GF(2)^n → GF(2)^n acts on x = (x_0, x_1, ..., x_{n-1}) via coordinates:
χ_i(x) = x_i ⊕ ((x_{i+1} ⊕ 1) ∧ x_{i+2}) = x_i ⊕ x_{i+2} ⊕ x_{i+1}x_{i+2}
with indices modulo n.
Wolfram rule 210 is the elementary 1D cellular automaton whose local truth word is 11010010_2 = 210 in the standard neighborhood order.
Method
The formula was established by quotient rank analysis and verified with finite-cell SAT checks:
- Quotient Rank Lower Bound: Modulo the affine subspace GF(2)[x_0, ..., x_{n-1}]_≤1, the nonlinear part of coordinate χ_i is the quadratic monomial x_{i+1}x_{i+2}. For n ≥ 3, the cyclic edge monomials {x_{i+1}x_{i+2} : 0 ≤ i < n} are linearly independent over GF(2). Computing m linearly independent quadratic forms modulo affine functions requires at least m multiplications in GF(2), establishing MC(χ_n) ≥ n. The direct coordinatewise implementation matches this bound, giving MC(χ_n) = n.
- Finite Verification: Evidence tier is P (Proved), with fully closed verification (FC) on the base case MC(χ_3) = 3 and independent finite-width checks through n = 8.
3.
Discussion
This result completely determines the multiplicative complexity of the forward χ mapping for all n ≥ 3.
Key properties:
- The lower bound MC(χ_n) ≥ n matches direct coordinatewise evaluation. No joint optimization, gate sharing, or linear coordinate transformation can eliminate an AND gate across the forward layer.
- The identity χ_i = Rule210_{i+1} places Keccak's nonlinear layer within the Wolfram cellular automaton classification.
- In the GF(2) XAG model, zero-knowledge circuits implementing Keccak χ on n-bit registers cannot beat n multiplications.
For everyone — the takeaway
What this means
Evaluating an n-bit forward χ block requires at least n bit multiplications for any register size of three bits or more. In zero-knowledge proof systems where bit multiplications determine memory footprint and proving runtime, the standard coordinate-by-coordinate implementation is already optimal. No algebraic restructuring can reduce the number of AND gates.
Register references
- Entry: MF-129
- Receipts:
- zkgolf-decomp/surface-verify-scratch/independent-surface.receipt.json (SHA-256 44fee010c465c25c5f7c41c4fb3978a825d87e65db09479eb9c8a76d588b8391)
- zkgolf-decomp/surface-verify-scratch/independent-proof-audit.md (SHA-256 ff828f2a98a8c8825cec56a3a04365b5800ef2e3464640c1e2e8c364d5d8cd63)
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 3 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.