Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-116
Strict syntactic-equivariant inverse-χ costs at widths 3, 5, and 7
E_3 = 3, E_5 = 10, E_7 = 21 for strict syntactic-equivariant inverse-χ; equivariance taxes are 0, 4, 12 over unrestricted costs 3, 6, 9
Published 2026-09-04
For everyone
Plain summary
Ciphers like Keccak (used in SHA-3) and Ascon scramble data using nonlinear substitution blocks called χ S-boxes. These blocks have natural rotational symmetry: shifting the input bits shifts the output bits by the same offset. Circuit designers often preserve this internal symmetry when building the inverse operation to simplify hardware wiring and formal verification.
Preserving internal symmetry increases the required number of nonlinear multiplications. This penalty is the equivariance tax. This work establishes the exact multiplicative costs for strict syntactic-equivariant inverse-χ mappings at widths 3, 5, and 7. The exact costs are 3, 10, and 21 multiplications. Compared to unrestricted costs of 3, 6, and 9 multiplications, maintaining internal symmetry adds a tax of 0, 4, and 12 multiplications respectively.
Result
Let E_n denote the exact multiplicative complexity of the inverse-χ mapping at width n under strict syntactic equivariance in the XOR-free GF(2) XAG cost model. For odd widths n ∈ {3, 5, 7}:
E_3 = 3 E_5 = 10 E_7 = 21
Relative to unrestricted multiplicative complexity bounds MC(χ_n⁻¹) = (3, 6, 9) for n = (3, 5, 7), the exact equivariance taxes Δ_n = E_n - MC(χ_n⁻¹) are:
Δ_3 = 3 - 3 = 0 Δ_5 = 10 - 6 = 4 Δ_7 = 21 - 9 = 12
This resolves the former open bracket at width 7 and fixes E_7 = 21 unconditionally.
Setting and definitions
The target functions are the bitwise inverse mappings χ_n⁻¹ : GF(2)ⁿ → GF(2)ⁿ for odd bit-widths n. Complexity is measured in the standard XOR-free GF(2) XOR-AND graph (XAG) model: XOR and NOT gates have zero cost, and the metric counts the minimum number of 2-input GF(2) AND gates.
An implementation is strictly syntactic-equivariant if the circuit graph structure and internal nonlinear gate definitions are invariant under the cyclic shift action on GF(2)ⁿ, mapping every internal wire family to itself under index translation modulo n.
Method
Bounds were established under evidence tier P + FC + FR (Proof, Full Certificate, Full Replay).
Lower bounds and exact values were resolved via certified Boolean satisfiability encodings of the equivariant decomposition space:
- Exact equivariant family replays were verified with
equivariant-family-replay.json(SHA-2563203a1f94016c6d0f3ab302a5c145748b5a19835dd814fac7af7b485b89a9ed4). - Exact tax lower bounds and synthesis proofs were verified with
eq-tax-certificate.json(SHA-2567d1e0bc24abf7b71b1a937aa0301211d82c342f3c171bc9f42360aaec9e9f628). - The exact resolution at width 7 was verified with
n7_plain_receipt.json(SHA-2564b8f60c073f5d282778a0c7d8e97c34009bf52ca1195fed2c11aa5dcf9bb50df) andn7_seeded_receipt.json(SHA-256ed7b3be7554901f1fdb59b16b349f804d1e8727749d97c6e77d23b224c7d54d1).
Discussion
These bounds apply strictly to syntactic equivariance under cyclic group actions for χ⁻¹ at widths 3, 5, and 7.
The tax of strict equivariance grows rapidly with block size:
- At width 3, the tax is 0 (cost equals unrestricted synthesis at 3).
- At width 5, equivariance requires 10 multiplications instead of 6 (tax of 4).
- At width 7, equivariance requires 21 multiplications instead of 9 (tax of 12).
The exact value E_7 = 21 closes the previous bounds bracket. This result does not constrain asymmetric implementations or circuits that are equivariant only at the output interface without internal syntactic symmetry.
For everyone — the takeaway
What this means
Hardware designers implementing algorithms like Ascon or Keccak must balance clean structural layout against circuit size. Rotational symmetry simplifies layout and verification, but demanding full internal symmetry on inverse operations carries a steep multiplication penalty. At width 7, maintaining full symmetry requires more than twice the multiplications of an unrestricted design.
Register references
- Entry: MF-116
- Report:
zkgolf-decomp/reports/EXP-EQ-TAX.md - Report:
zkgolf-decomp/reports/SB-TAX.md - Report:
zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md - Receipt:
zkgolf-decomp/exp-eq-scratch/equivariant-family-replay.json(SHA-2563203a1f94016c6d0f3ab302a5c145748b5a19835dd814fac7af7b485b89a9ed4) - Receipt:
zkgolf-decomp/exp-eq-scratch/eq-tax-certificate.json(SHA-2567d1e0bc24abf7b71b1a937aa0301211d82c342f3c171bc9f42360aaec9e9f628) - Receipt:
zkgolf-decomp/sb-tax-scratch/n7_plain_receipt.json(SHA-2564b8f60c073f5d282778a0c7d8e97c34009bf52ca1195fed2c11aa5dcf9bb50df) - Receipt:
zkgolf-decomp/sb-tax-scratch/n7_seeded_receipt.json(SHA-256ed7b3be7554901f1fdb59b16b349f804d1e8727749d97c6e77d23b224c7d54d1)
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.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.