Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-079
Exact multiplicative complexity of χ₅⁻¹ and S_Ascon⁻¹
MC(χ₅⁻¹) = MC(S_Ascon⁻¹) = 6
Published 2026-08-29
For everyone
Plain summary
The 5-bit χ inverse and the inverse Ascon S-box (from NIST SP 800-232) each require exactly six AND operations when linear steps come free. We verified a six-AND recipe against all 32 five-bit inputs, and an independent checker verified the transfer to the Ascon S-box across the same 32 rows. A matching lower bound proves no recipe can evaluate either function with five or fewer ANDs. These counts set exact circuit costs for secure multi-party computation, masking, and homomorphic encryption. The six-AND construction itself is known prior art; claims presenting it as a new record or citing 9 ANDs as the best published count are incorrect. The lower bound and the exact equality are plausible priority records, qualified with “to our knowledge” because the prior-art search was bounded.
Result
Let χ₅ denote the five-bit χ map and let S_Ascon denote the Ascon S-box. In the multiplicative-complexity model:
MC(χ₅⁻¹) = MC(S_Ascon⁻¹) = 6.
The lower bound on χ₅⁻¹ is 6 at n = 5. An explicit six-AND circuit with an affine decoder matches this bound. Because S_Ascon is affine-equivalent to χ₅, affine invariance of multiplicative complexity transfers the exact cost to S_Ascon⁻¹.
Setting and definitions
Multiplicative complexity MC is the minimum number of AND gates needed to evaluate a Boolean map over XOR/AND circuits, treating affine decoders as free linear overhead. The maps χ₅⁻¹ and S_Ascon⁻¹ are permutations on five bits (32 truth-table rows). Affine equivalence means two maps differ only by invertible affine coordinate transformations at input and output, which preserve MC. Establishing an exact count requires exhibiting a 6-AND circuit and proving the nonexistence of any 5-AND circuit.
Method
The lower bound follows from the n = 5 case of the χ-inverse lower-bound theorem. The upper bound evaluates an explicit six-AND circuit with an affine decoder, replayed over all 32 inputs.
The transfer to S_Ascon⁻¹ was verified from scratch by checking the affine-equivalence relations across all 32 rows against standard specification data.
The full mathematical derivations, verification scripts, and raw execution outputs are provided in this paper's downloadable evidence pack.
Discussion
We establish the exact value MC = 6. The upper-bound circuit is prior art: KeccakTools commit 62736978 (2014) contains a six-iteration single-& inverse loop, and Amy et al. (SAC 2016) report 30w Toffoli gates for inverse χ over 5w rows. These citations refute claims that the six-AND circuit is a new record, the first published six-AND design, or an improvement over a putative 9-AND best published count.
The matching lower bound and resulting exact value are plausible priority claims. Because the literature search was bounded, any priority assertion must be qualified with “to our knowledge.” The practical consequence is a settled multiplicative complexity for a NIST-standardized inverse S-box in masking, MPC, and FHE schemes.
For everyone — the takeaway
What this means
Both inverse functions take exactly six AND operations when linear steps are free. A six-AND circuit works for all inputs, and mathematical proof shows five ANDs can never be enough. The Ascon inverse shares this exact count because swapping linear coordinates doesn't change the number of ANDs needed.
This gives engineers exact numbers when budgeting for masked hardware, threshold cryptography, or encrypted computing. Because the six-AND recipe already existed in older codebases, the new contribution is the matching lower bound and proof of optimality, claimed strictly to our knowledge.
Attribution and prior art
Prior art: The six-AND construction is prior art, refuting earlier claims of a new record, the first published six-AND construction, or a prior best value of 9 ANDs. To our knowledge, the matching lower bound and exact determination remain plausible and likely records based on a bounded search.
Register references
- MF-079.
independent_chi5_verifier.pywith SHA-2564f9e5858…5354and output2dcbf958…f63bf.independent_ascon_transfer_verifier.pywith SHA-2569f71b10f…de8a8, output80925648…f1499.ZKGOLF-CHI5INV-SOL-VERDICT-2026-08-14.md.03_PROVED_THEOREMS_AND_LOWER_BOUNDS.md, Thm 1.1.- KeccakTools commit
62736978(2014). - Amy et al. (SAC 2016).
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 4 receipt files bundled (18 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-30
- 2026-08-29Published on this site.
- 2026-08-30The isolated χ₅⁻¹ cell was superseded on 2026-08-30. Its exact value 6 remains valid as the n=5 instance of MF-098, and no new priority claim is made.