Research · Papers · Cipher S-boxes, χ, and quantum gate counts · ML-082
Multiplicative complexity bounds for chi_6^2 and chi_7^2
chi_6^2 ∈ [8, 12], chi_7^2 ∈ [9, 14]
Published 2026-09-04
For everyone
Plain summary
Modern ciphers and hash functions rely on nonlinear operations to scramble data. In hardware and zero-knowledge proof systems, circuit cost is measured by multiplicative complexity: the smallest number of multiplication (AND) gates needed when additions (XOR) cost nothing.
This entry tracks the multiplicative complexity of running the cryptographic chi transformation—the core permutation in designs like Keccak—twice in a row at block widths of 6 and 7 bits, written chi_6^2 and chi_7^2. The exact costs sit in unresolved intervals: 8 to 12 multiplication gates for 6-bit blocks, and 9 to 14 multiplication gates for 7-bit blocks. Exhaustive computer searches proved the lower bounds by ruling out all smaller circuits. Stacking two independent single-round layers gives the upper bounds.
Result
Under the GF(2) XOR-and-inverter graph (XAG) multiplicative complexity model:
chi_6^2 ∈ [8, 12]
chi_7^2 ∈ [9, 14]
Setting and definitions
Let chi_n denote the standard n-bit nonlinear permutation layer over GF(2), and chi_n^2 its two-round composition chi_n ∘ chi_n. The multiplicative complexity MC(f) is the minimum number of two-input AND gates required to evaluate multi-output Boolean map f in a straight-line program over the basis (AND, XOR, NOT), with zero-cost XOR and NOT.
Method
Lower bounds follow from exhaustive gate-budget synthesis recorded in MF-155. For width 6, the chi engine completed an exhaustive no-symmetry search across 651 first-gate equivalence classes at budget K = 7 without finding a valid circuit, proving MC(chi_6^2) ≥ 8 (out_s04b_chi6pow2_k7_nosym.json).
The trivial two-layer construction 2n provides the upper bounds: 12 gates for n = 6 and 14 gates for n = 7.
Theoretical packing and THEOREM E arguments cannot improve these lower bounds without the 3-form transfer framework (ML-075).
Discussion
The bounds for chi_6^2 and chi_7^2 remain unresolved. Resolving chi_6^2 centers on an exhaustive gate-budget sweep at K = 8:
- A witness at K = 8 yields MC(chi_6^2) = 8, supporting the candidate family scaling chi_n^2 = n + 2 for n = 4..6.
- Exhaustion without a witness raises the lower bound to MC(chi_6^2) ≥ 9.
The K = 8 search at width 6 is estimated at roughly 30× the K = 7 sweep (651 first-gate classes) and requires AX162 hardware.
For everyone — the takeaway
What this means
Exact multiplicative complexity directly drives circuit optimization for cryptographic primitives. Designers of Keccak-like hashes and zero-knowledge protocols need exact gate counts to minimize hardware area and proof overhead. Determining whether chi_6^2 needs 8 gates will either validate a linear scaling pattern across small widths or show that wider permutations demand non-linear gates at a steeper rate.
Register references
- ML-082
- MF-155
- ML-075
- chi/REPORT.md §5
- out_s04b_chi6pow2_k7_nosym.json
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 2 receipt files bundled (10 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.