Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-098
Exact multiplicative complexity of odd inverse chi
For odd n ≥ 1, MC(χₙ⁻¹) = 3(n−1)/2; in particular MC(χ₇⁻¹) = 9
Published 2026-08-29
For everyone
Plain summary
The chi map is a small, reversible nonlinear step used inside cryptographic permutations. This paper finds the exact number of nonlinear binary multiplications needed to invert chi at every odd width when XOR and constants are free. For every positive odd n, the count is 3(n−1)/2. At seven bits the exact cost is 9, closing the gap between a nine-product theoretical floor and an unverified ten-product upper bound. The proof pairs a general lower-bound argument with a matching acyclic circuit construction, verified from definitions in a clean-room script. At n=7, the verification script ran two distinct nine-product circuits across all 128 inputs with zero errors. This result applies specifically to the acyclic 2-XAG multiplicative-complexity model, not every physical gate library. No priority or novelty claim is made. The upper construction is prior art and is credited below; this paper's contribution is the matching lower bound and exactness.
Result
For every positive odd integer n,
MC(χₙ⁻¹) = 3(n−1)/2.
When n=1, chi is the identity and both sides evaluate to zero. For n=2m+1 ≥ 3, the matching lower and upper bounds give m+n−1=3(n−1)/2. In particular:
MC(χ₅⁻¹)=6, MC(χ₇⁻¹)=9, and MC(χ₉⁻¹)=12.
The theorem is proved symbolically for all odd widths. Finite circuit replays verify the base cases independently.
Setting and definitions
An acyclic 2-XAG is a Boolean circuit where affine operations over GF(2) are free and two-input AND gates carry unit cost. MC(F) denotes the minimum number of AND gates needed to compute F. Set n=2m+1 with cyclic coordinate indices.
The inverse coordinate functions satisfy
F_i(y)=y_i+sum_(j=1)^m y_(i+2j) product_(k=1)^j (1+y_(i+2k−1)).
Each coordinate has algebraic degree d=m+1. Its unique top-degree monomial is the cyclic shift
H_i=y_(i−1)y_(i+1)y_(i+3)…y_(i+2m−1).
Because these n monomials are distinct, every nonzero affine combination of inverse coordinates has degree d. The target space modulo affine functions therefore has dimension n.
Method
The lower bound analyzes gate classes modulo affine functions. In a minimal p-AND circuit, these classes are linearly independent, and the class of gate j has degree at most j+1. The first d−2=m−1 gate classes have degree strictly below d. Their span intersects the n-dimensional target space trivially, as every nonzero element in the target space has degree d. Since both subspaces lie inside the p-dimensional space of gate classes,
p ≥ n+(d−2)=n+m−1=3(n−1)/2.
The matching upper bound starts with an m-gate Horner chain for a single seed coordinate. The recurrence
x_i=y_i+(1+y_(i+1))x_(i+2)
yields each subsequent coordinate with one additional AND gate while stepping by −2 cyclically. Because gcd(2,n)=1, this sweep covers all coordinates. The seed requires m gates and the remaining sweep takes n−1 gates, totalling m+n−1. The resulting acyclic circuit matches the lower bound.
The standalone script synth-i-scratch/cleanroom_checks.py validates the construction using only the Python standard library. It builds chi, inverts the truth table, applies the Möbius transform, evaluates output-combination degrees and top-layer ranks, and simulates the circuits. At n=5, all 31 nonzero combinations have degree 3 with top rank 5 (floor 6); the sweep circuit evaluates correctly on all 32 inputs using 6 gates. At n=7, all 127 combinations have degree 4 with top rank 7 (floor 9); both the CHT sweep and an independently transcribed CHU circuit use 9 gates and pass all 128 inputs. Further CHT replays pass at n=5,7,9,11 with gate counts 6,9,12,15.
Discussion
MF-098 integrates the lower bound from PROVER-CHS-SPAN.md with the rotation-sweep synthesis from PROVER-CHT-UPPER.md. The clean-room checks confirm the small instances n=5 and n=7 without relying on precomputed lookup tables. The general formula across all odd widths follows from the two symbolic proofs.
This result supersedes the lower-bound-only scope of MF-078 and the single-instance determination of MF-079 at n=5. Those specific results remain consistent within the general theorem. Equivariant complexity under strict symmetry constraints is a separate model and is not resolved here. This proof does not evaluate physical silicon area, critical-path latency, Toffoli count, or libraries with nonzero XOR cost.
Attribution correction (2026-08-30): the prior-art sweep is complete. The upper construction is credited to the Keccak team below; MF-098 records the matching unrestricted lower bound and all-odd-width exactness, with its independent evidence retained as corroboration. No priority, novelty, or world-first claim is made.
For everyone — the takeaway
What this means
This result gives a single formula for inverting chi at any odd width instead of relying on case-by-case searches. Adding two bits to the state width adds three nonlinear multiplications to the inversion circuit. Seven-bit inversion takes 9 multiplications, and the script proved a 10-gate estimate unnecessary by testing two working 9-gate designs on every input. High algebraic degree establishes the lower bound, while a cyclic recurrence provides an exact circuit that hits it without waste. The clean-room code checks the concrete small cases, while the general proof guarantees the formula holds for every odd width. Costs under different gate libraries or hardware models require separate analysis.
Attribution and prior art
Construction credit. The matching upper family was not first constructed here. Credit belongs to the Keccak team. In KeccakTeam/KeccakTools, Sources/Keccak-f.h, function inverseChi, lines 2678–2701 as inspected on 2026-08-30, line 2685 sets length = 5, line 2691 uses the literal loop bound 3*(length-1)/2, and line 2695 contains the loop's one binary &. Commit 62736978de1206fdd4421fc74874705d774add89 (2014-03-11) is titled Improved inverse of χ (algorithm generic in length).
What MF-098 adds. The division contribution is the matching unrestricted lower bound and therefore exactness for every positive odd n. The independent proof, clean-room checks, and replay receipts remain valid corroboration; no numerical or mathematical claim changes.
Published iteration identities. Schoone and Daemen, The state diagram of χ, *Designs, Codes and Cryptography* 92 (2024), 1393–1421, Corollary 9, doi:10.1007/s10623-023-01349-8, proves ord(χ_n)=2^ceil(log2((n+1)/2)). Thus χ₃²=id and ord(χ₅)=4, hence χ₅³=χ₅⁻¹.
Sources: doi:10.1007/s10623-023-01349-8
Register references
- MF-098.
SYNTH-I-FAMILIES.md.PROVER-CHS-SPAN.md.PROVER-CHT-UPPER.md.synth-i-scratch/cleanroom_checks.py.prover-cht-scratch/upper_replay_receipt.json.prover-cht-scratch/independent_audit_receipt.json.prover-chu-scratch/replay_nine_witness.py.- Prior-art position corrected 2026-08-30: upper construction credited to the Keccak team; matching lower bound and all-odd-width exactness are the division contribution; no priority claim is made.
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 2 of 6 receipt files bundled (15 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-30
- 2026-08-29Published on this site.
- 2026-08-30Correction (2026-08-30): The 3(n-1)/2 upper construction family is prior art credited to the Keccak team (KeccakTools, 2014). As recorded in MF-098, our matching lower bound and proof of exactness for every positive odd n remain unchanged and supported by independent replay checks.