Research · Papers · Cipher S-boxes, χ, and quantum gate counts · ML-064
Infeasibility of K12 score reduction via banked rowwise chi5 replacements
Rowwise chi5 in Keccak-p[1600,12] is optimal at 5 products per row (19,200 total); no banked rowwise replacement reduces the score.
Published 2026-09-04
For everyone
Plain summary
Keccak-p[1600,12] is the core permutation inside the Kravatte and KangarooTwelve (K12) hash functions. When implemented as an arithmetic circuit, its cost is measured by the total number of multiplications it performs. The reference construction uses 3,840 separate 5-bit chi5 operations, each taking 5 multiplications, for a baseline cost of 19,200 multiplications.
Swapping in alternative precomputed formulas for individual rows cannot lower this score. Each forward 5-bit row already runs at the theoretical minimum of 5 multiplications, while inverse formulas require 6. Direct row-by-row replacements provide zero savings.
Result
Direct rowwise replacement of forward chi5 mappings in Keccak-p[1600,12] cannot reduce multiplicative complexity below 19,200 products in the GF(2) XAG cost model. Under the reference identity-C construction, each of the 3,840 forward chi5 evaluations is already minimal at 5 products per 5-bit row.
Setting and definitions
The target function is the 12-round permutation Keccak-p[1600,12]. The cost model is the XOR-free GF(2) straight-line program / XAG metric, counting strictly non-linear AND products.
Each round applies an affine layer (theta, rho, pi), a non-linear substitution layer (chi), and an affine constant addition (iota). The chi layer evaluates parallel 5-bit chi5 mappings per round, totaling 3,840 rowwise forward evaluations across the 12 rounds.
Method
The banked catalog of rowwise forward and inverse chi5 implementations was evaluated against the reference circuit:
- Multiplicative complexity certification confirmed that each forward chi5 instance requires 5 products, matching the theoretical rowwise lower bound.
- The verifier relation uses no inverse operations. A rowwise chi5^-1 evaluation costs 6 products, strictly increasing circuit size.
- The algebraic identity chi5^3 = chi5^-1 cannot be leveraged across successive rounds because intermediate affine steps (theta, rho, pi, iota) disrupt direct composition.
Certification receipts are recorded in zkgolf-decomp/REDEPLOY-K12.md and zkgolf-decomp/SURFACE-VERIFY.md.
Discussion
This result closes localized rowwise substitution as an optimization route: the 19,200-product baseline cannot be lowered by swapping isolated 5-bit chi5 implementations.
This does not establish a global lower bound for Keccak-p[1600,12]. Product reductions below 19,200 must rely on non-local strategies, such as cross-row linear combinations or multi-round algebraic factorizations that bridge the affine layers.
For everyone — the takeaway
What this means
You cannot make the 12-round Keccak circuit cheaper by optimizing individual 5-bit rows. The standard formula already uses the minimum number of multiplications possible for a single row. Any circuit savings will have to come from combining operations across multiple rows or rounds at once.
Register references
- Entry ID: ML-064
- Artifact:
zkgolf-decomp/REDEPLOY-K12.md - Artifact:
zkgolf-decomp/SURFACE-VERIFY.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 2 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.