Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-155
Multiplicative complexity lower bounds and brackets for chi_6^2 and chi_7^2
MC(chi_6^2) >= 8 (bracket [8, 12]) and MC(chi_7^2) >= 9 (bracket [9, 14])
Published 2026-09-04
For everyone
Plain summary
Ciphers and hash functions rely on non-linear steps to scramble data. A common building block is the Chi permutation, used in designs like Keccak and Xoodoo. A transformation's multiplicative complexity is the minimum number of logical AND gates needed to compute it when XOR additions cost nothing.
Evaluating two consecutive rounds of Chi on 6-bit and 7-bit blocks matters for zero-knowledge proofs and secure multi-party computation, where non-linear operations dominate performance costs. By testing all possible circuit structures across symmetry-reduced linear equivalence classes, this work proves that two rounds of 6-bit Chi require at least 8 AND gates, and two rounds of 7-bit Chi require at least 9 AND gates. Paired with standard two-round implementations, this establishes complexity brackets of [8, 12] on 6 bits and [9, 14] on 7 bits.
Result
For the iterated quadratic permutations chi_6^2 on GF(2)^6 and chi_7^2 on GF(2)^7:
MC(chi_6^2) >= 8 MC(chi_7^2) >= 9
Combined with the composition upper bound MC(chi_n^2) <= 2n, the resulting multiplicative complexity brackets are:
MC(chi_6^2) in [8, 12] MC(chi_7^2) in [9, 14]
Both lower bounds exceed the theoretical packing floors from MF-137 (7 for n = 6 and 8 for n = 7) by one gate.
Setting and definitions
Let GF(2) denote the binary field. The permutation chi_n: GF(2)^n -> GF(2)^n is defined for bit indices i in {0, ..., n-1} modulo n by:
chi_n(x)_i = x_i + (x_{i+1} + 1) * x_{i+2}
where addition and multiplication are in GF(2). The composition chi_n^2 denotes chi_n(chi_n(x)).
The multiplicative complexity MC(f) of a Boolean mapping f: GF(2)^n -> GF(2)^m is the minimum number of 2-input AND gates required to evaluate f over {XOR, AND, NOT, 1}. Under AGL(n, 2) orbit classification, Boolean maps partition into affine equivalence classes, enabling exhaustive gate-budget verification over orbit representatives.
Method
The lower bounds were established via fully checked (FC tier) exhaustive gate-budget exclusions under the AGL(n, 2) orbit cost model, following the framework in MF-154:
- For chi_6^2, sweeping target complexity K = 7 evaluated 117 affine orbit representatives, corresponding to 651 equivalence classes without symmetry reduction. All candidate structures were excluded, ruling out MC(chi_6^2) <= 7.
- For chi_7^2, sweeping target complexity K = 8 across 381 affine orbit representatives excluded all candidates, ruling out MC(chi_7^2) <= 8.
- Control tests on width-6 instances were validated.
Receipt artifacts:
- chi/out_s04_chi6pow2_k7.json
- out_s04b_chi6pow2_k7_nosym.json
- out_s04b_chi7pow2_k8.json
- out_s10_controls_w6.json
Discussion
The bounds MC(chi_6^2) >= 8 and MC(chi_7^2) >= 9 surpass the MF-137 packing floors by one gate.
The upper limits of the brackets ([8, 12] and [9, 14]) derive from the direct two-layer composition MC(chi_n^2) <= 2 * MC(chi_n) = 2n, where each round of chi_n uses n AND gates. Resolving the exact value of MC(chi_6^2) requires evaluating the K = 8 budget sweep. As tracked in ML-082, synthesized circuits at K = 8 would establish MC(chi_6^2) = 8, whereas complete solver exhaustion at K = 8 would prove MC(chi_6^2) >= 9.
The prior-art status is APPARENTLY-NEW (comparable to MF-154, with fewer recorded prior searches).
For everyone — the takeaway
What this means
These results establish hard lower bounds on circuit size for two rounds of the Chi permutation on 6-bit and 7-bit blocks. In protocols where non-linear operations carry heavy overhead—such as zero-knowledge proofs and secure multi-party computation—these bounds prevent wasted search effort for impossible shortcuts. Two rounds of 6-bit Chi cannot run in fewer than 8 AND gates, and two rounds of 7-bit Chi cannot run in fewer than 9.
Attribution and prior art
Prior art: This is an apparently new result cataloged as entry MF-154, achieved using fewer searches.
Register references
- Entry: MF-155
- Related entries: MF-137, MF-154, ML-082
- Prior art: APPARENTLY-NEW (as MF-154, fewer searches)
- Receipts:
- chi/out_s04_chi6pow2_k7.json
- out_s04b_chi6pow2_k7_nosym.json
- out_s04b_chi7pow2_k8.json
- out_s10_controls_w6.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 4 of 4 receipt files bundled (2 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.