Research · Papers · Cipher S-boxes, χ, and quantum gate counts · ML-066
Failure of Keccak-family score reduction via inverse-χ exactness
Exact inverse-χ_5 and Ascon inverse circuits yield zero solver score reductions over forward-χ (MC(χ_n) = n).
Published 2026-09-04
For everyone
Plain summary
Keccak (the hash function behind SHA-3) and Ascon use small substitution steps called S-boxes to mix data. In zero-knowledge proof systems, builders try to minimize nonlinear operations, such as AND gates, to keep circuits small and fast.
This project tested whether synthesizing exact, minimal circuits for the mathematical inverses of these S-boxes could reduce circuit costs on active benchmark boards. It did not. The benchmark boards score the forward substitution step, which already runs at the theoretical minimum number of nonlinear gates. Because the inverse operations are inherently more complex and require more gates than the forward maps, routing through inverse paths increases circuit size. The forward implementations remain optimal.
Result
Exact circuit synthesis of the inverse maps χ₅⁻¹ and the affine-conjugate Ascon inverse yields zero solver score reductions over forward-χ on GF(2) XAG benchmarks. Forward multiplicative complexity is already minimal at MC(χ_n) = n.
Setting and definitions
Let χ_n : GF(2)ⁿ → GF(2)ⁿ denote the Keccak-family non-linear mapping. The cost metric is multiplicative complexity MC(f) over GF(2) in the XOR-free cost model (GF(2) XAG). Target functions are χ₅, its inverse χ₅⁻¹, and the affine-conjugate inverse mapping used in Ascon.
Method
Receipt zkgolf-decomp/REDEPLOY-KECCAK-FAMILY.md records the evaluation of exact inverse-χ implementations against existing forward-χ circuit rows. Exact reference circuits and optimality certificates were synthesized for χ₅⁻¹ and the affine-conjugate Ascon inverse to test rowwise replacements across active scored circuit boards.
Discussion
The redeployment route is dead. Scored circuit boards evaluate the forward map χ_n, which already hits the theoretical floor of n products. The inverse map χ₅⁻¹ has strictly higher multiplicative complexity than forward χ₅.
Prior inverse-critical constructions do not transfer reductions to the GF(2) XAG model: they either depend on the involutive case χ₃, linearize the inverse over restricted subspaces, or count cryptanalytic work rather than hardware AND gates. Introducing exact inverse synthesis increases rowwise cost and uncovers no new solver reductions.
The investigation leaves two shelf-grade exact inverse rows—covering χ₅⁻¹ and the affine-conjugate Ascon inverse—as verified reference circuits and optimality certificates.
For everyone — the takeaway
What this means
Building exact inverse S-boxes does not speed up or shrink Keccak and Ascon benchmark circuits. The standard forward step already runs at the absolute floor of one nonlinear operation per bit. While these inverse circuits cannot improve forward scores, they serve as certified minimal references for tools that explicitly require the inverse step.
Register references
- Entry ID: ML-066
- Receipt:
zkgolf-decomp/REDEPLOY-KECCAK-FAMILY.md
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 0 of 1 receipt files bundled (1 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.