Slop Dealer

Research · Papers · Cipher S-boxes, χ, and quantum gate counts · ML-058

Exact costs of strict syntactic equivariance for widths 3, 5, and 7

E_3 = 3, E_5 = 10, E_7 = 21 with exact taxes 0, 4, 12 over unrestricted inverse-χ multiplicative complexity

ML-058PROVEDCERTIFIED PROOFCipher S-boxes, χ, and quantum gate counts

Published 2026-09-04

For everyone

Plain summary

Cryptographic substitution boxes scramble data to protect against attacks. Many designs are rotationally symmetric: shifting the input bits by a fixed offset shifts the output bits by the exact same offset. Circuit designers often try to preserve this rotational symmetry inside the circuit's internal wiring, a rule called strict syntactic equivariance.

This work calculates the exact number of multiplications required to compute the inverse of the standard Chi permutation under this symmetry constraint for 3-bit, 5-bit, and 7-bit inputs. For 3-bit inputs, requiring internal symmetry adds zero extra multiplications. For 5-bit and 7-bit inputs, the constraint forces 4 and 12 extra multiplications, respectively, compared to unstructured circuits. Forcing internal gate symmetry imposes a steep, quantifiable cost as bit width grows.

Result

In the strict syntactic-equivariant GF(2) XOR-AND graph (XAG) model, the exact multiplicative complexities E_n for inverse-χ on odd widths n ∈ {3, 5, 7} are:

E_3 = 3 E_5 = 10 E_7 = 21

Relative to unrestricted multiplicative complexity MC(inverse-χ), the exact symmetry taxes Tax_n = E_n - MC are:

Tax_3 = 3 - 3 = 0 Tax_5 = 10 - 6 = 4 Tax_7 = 21 - 9 = 12

Upper bounds are certified by constructive straight-line programs; lower bounds are exhaustively established in the syntactic-equivariant model.

Setting and definitions

The target permutations are inverse-χ on odd widths n ∈ {3, 5, 7} over GF(2)^n.

  • Multiplicative complexity in the GF(2) XAG model counts binary AND gates. Linear XOR gates and constant additions carry zero cost.
  • Strict syntactic equivariance requires all internal multiplication steps and wire assignments to be invariant under the cyclic shift group C_n acting on input wire indices. Evaluating an orbit of wires requires n symmetric AND operations (or matching sub-orbit groupings).
  • The equivariance tax is E_n - MC(inverse-χ_n).

Method

Results were established via SAT-based exact circuit synthesis, exhaustive family replays, and proof certificates on widths 3, 5, and 7:

  1. Equivariant circuit encoding: Straight-line programs over GF(2) were formulated as SAT instances with gate assignments partitioned into closed orbits under C_n action.
  2. Upper bounds: Syntactic-equivariant straight-line programs were synthesized at sizes 3 (width 3), 10 (width 5), and 21 (width 7). Schedules appear in zkgolf-decomp/reports/EXP-EQ-TAX.md, zkgolf-decomp/reports/SB-TAX.md, and zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md.
  3. Lower bounds: UNSAT proofs were generated for all candidate syntactic-equivariant graph topologies below 3 gates for n=3, below 10 gates for n=5, and below 21 gates for n=7.
  4. Certificate verification: Deterministic AX162 execution verified all artifacts:
  • Full family replay: zkgolf-decomp/exp-eq-scratch/equivariant-family-replay.json (SHA-256 3203a1f94016c6d0f3ab302a5c145748b5a19835dd814fac7af7b485b89a9ed4).
  • Equivariance tax certificate: zkgolf-decomp/exp-eq-scratch/eq-tax-certificate.json (SHA-256 7d1e0bc24abf7b71b1a937aa0301211d82c342f3c171bc9f42360aaec9e9f628).
  • Width-7 plain receipt: zkgolf-decomp/sb-tax-scratch/n7_plain_receipt.json (SHA-256 4b8f60c073f5d282778a0c7d8e97c34009bf52ca1195fed2c11aa5dcf9bb50df).
  • Width-7 seeded receipt: zkgolf-decomp/sb-tax-scratch/n7_seeded_receipt.json (SHA-256 ed7b3be7554901f1fdb59b16b349f804d1e8727749d97c6e77d23b224c7d54d1).

Discussion

  • The values E_3 = 3, E_5 = 10, and E_7 = 21 apply strictly to the syntactic-equivariant model. Unrestricted multiplicative complexities remain MC(inverse-χ) = 3, 6, and 9 for widths 3, 5, and 7.
  • These results do not establish an asymptotic closed form for E_n across arbitrary odd n.
  • The symmetry penalty grows superlinearly: 0 extra AND gates at width 3, 4 at width 5, and 12 at width 7.
  • Broader structural context is documented in entry MF-116.

For everyone — the takeaway

What this means

Engineers often prefer symmetric circuit layouts because they are easier to tile on chips and simpler to verify. For inverse-Chi, that symmetry comes at a steep price in multiplication gates once inputs exceed 3 bits. In zero-knowledge proof systems where every multiplication adds directly to prover time, breaking internal symmetry is necessary to hit the lowest possible gate counts.

Register references

  • Entry ID: ML-058
  • Related entry: MF-116
  • Technical reports:
  • zkgolf-decomp/reports/EXP-EQ-TAX.md
  • zkgolf-decomp/reports/SB-TAX.md
  • zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md
  • Execution receipts:
  • zkgolf-decomp/exp-eq-scratch/equivariant-family-replay.json (SHA-256 3203a1f94016c6d0f3ab302a5c145748b5a19835dd814fac7af7b485b89a9ed4)
  • zkgolf-decomp/exp-eq-scratch/eq-tax-certificate.json (SHA-256 7d1e0bc24abf7b71b1a937aa0301211d82c342f3c171bc9f42360aaec9e9f628)
  • zkgolf-decomp/sb-tax-scratch/n7_plain_receipt.json (SHA-256 4b8f60c073f5d282778a0c7d8e97c34009bf52ca1195fed2c11aa5dcf9bb50df)
  • zkgolf-decomp/sb-tax-scratch/n7_seeded_receipt.json (SHA-256 ed7b3be7554901f1fdb59b16b349f804d1e8727749d97c6e77d23b224c7d54d1)

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 7 receipt files bundled (33 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Changelog

Last reviewed 2026-09-04

  • 2026-09-04Published on this site.

Related in this programme

All papersThe registerThe institute