Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-078
A lower bound for the multiplicative complexity of χₙ⁻¹
For every odd integer n ≥ 3, MC(χₙ⁻¹) ≥ (3n−3)/2
Published 2026-08-29
For everyone
Plain summary
Reversing the odd-width binary transformation χ requires at least (3n−3)/2 nonlinear multiplications when XOR gates and fixed constants are free. Multiplicative complexity (MC) counts only these nonlinear products. For widths n=3,5,7,9,11, the rule forces at least 3, 6, 9, 12, and 15 multiplications.
The proof combines the established algebraic formula for the inverse with an algebraic degree-and-rank argument. The closed formula, its degree, and the rank lemma come from prior literature. The single contribution here is joining them to prove the lower bound across the entire odd-width family. The result establishes a floor on circuit size, not an exact count or an upper bound.
Result
For every odd integer n ≥ 3,
MC(χₙ⁻¹) ≥ (3n−3)/2.
For n=2m+1, the same bound is MC ≥ n + (n+1)/2 − 2.
Setting and definitions
Let n=2m+1, with m=(n−1)/2. In coordinate i, the closed formula for χₙ⁻¹ has the unique top monomial
Mᵢ = y_{i−1}·∏_{k=1..m} y_{i−2k}
of algebraic degree m+1=(n+1)/2.
The rank-plus-degree lemma sets MC ≥ r + d − 2, where r is the top-symbol rank and d is the degree enforced across all nonzero affine combinations of the inverse coordinates. Distinctness of the n top monomials yields r=n and d=(n+1)/2.
Method
The symbolic proof establishes that the top monomials Mᵢ are distinct. If Mᵢ=M_{i+r}, the monomial support of size m+1 is shift-invariant, so its orbit length divides both 2m+1 and m+1. Because gcd(2m+1, m+1) = 1, no nontrivial shift symmetry exists. Every nonzero affine combination of output coordinates therefore retains degree d=m+1=(n+1)/2, and the top-symbol rank is r=n.
Substituting these parameters into the lemma gives
MC ≥ n + (n+1)/2 − 2 = (3n−3)/2.
Truth tables were generated and inverted for n=3,5,7,9,11. Row-by-row checks confirmed inverse degrees 2,3,4,5,6, top-symbol ranks 3,5,7,9,11, and lower bounds 3,6,9,12,15.
The generation scripts, execution certificates, and verification logs are in this paper's downloadable evidence pack.
Discussion
The truth-table replays verify the formula and symbol metrics on small instances; the coprimality argument carries the bound to all odd n ≥ 3.
Scope is restricted to χₙ⁻¹ at odd n ≥ 3 under standard multiplicative complexity over GF(2). The bound is a lower limit, not an exact evaluation or an upper bound on circuit synthesis. Corrections: none.
Attribution: the inverse formula and degree are due to Liu–Sarkar–Meier–Isobe (ePrint 2022/399). The rank-plus-degree lemma adapts the framework discussed in Boyar–Find (arXiv:1407.6169). The contribution is the family-wide combination. Certificate SHA-256: a1f6afb1…365a. Page verdict: SHOWCASE.
For everyone — the takeaway
What this means
When building circuits where linear XOR mixing is free, undoing the χ operation always requires a minimum number of nonlinear AND operations. This minimum scales upward with the bit width. The paper proves this floor holds for every odd width from 3 bits onward by showing that the highest-degree terms in the algebraic description never cancel each other out. It establishes a hard lower limit on hardware and prover cost, though specific implementations may need more gates.
Attribution and prior art
Prior art: The inverse formula and its degree are from Liu–Sarkar–Meier–Isobe (ePrint 2022/399, Thm 1), while the rank-plus-degree lemma adapts a classical argument by Boyar–Find (arXiv:1407.6169). This work's contribution is combining these techniques to establish the family bound.
Register references
- MF-078.
- Receipts:
zkgolf-transfer-studies/03-mc-lower-bounds-tcount/chi_inverse_family_lower_bound.py+chi_inverse_family_certificate.json(replay PASS, output SHA-256a1f6afb1…365a);ZKGOLF-CHI5INV-SOL-VERDICT-2026-08-14.md. - Prior art: Liu–Sarkar–Meier–Isobe ([ePrint 2022/399](https://eprint.iacr.org/2022/399), Thm 1); Boyar–Find (arXiv:1407.6169).
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 3 of 3 receipt files bundled (16 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-30Superseded on 2026-08-30: Although the inverse-χ family lower statement remains valid, it has been superseded by MF-098, the clean-room checked composed exact family theorem. The updated result is confirmed by an independent audit and a replay check.