Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-157
Iterate structure, degree, and attributions for the Keccak chi mapping
deg chi_n^j = j+1 for j ≤ ⌊n/2⌋ (FC-verified n=3..13); |im(chi_n)| = 2^n - 2^{n/2} for even n; Ascon S-box is B ∘ chi_5 ∘ A
Published 2026-09-04
For everyone
Plain summary
The Keccak hash function, standardized as SHA-3, uses a nonlinear step called chi. Applying chi repeatedly increases its algebraic degree—a measure of polynomial complexity—by exactly 1 each round, up to half the state length.
This entry corrects internal project records and verifies the mapping across small bit-widths. Earlier internal notes misattributed the degree growth theorem to a 2024 paper by Schoone and Daemen, which contains no algebraic normal form calculations. The analytical proof for odd bit-lengths is due to Kriepke and Kyureghyan (CRYPTO 2024). Exhaustive computer checks here confirm the rule across all dimensions from 3 to 13 bits, establishing that it holds for even dimensions as well. The entry also records exact image sizes for non-invertible even dimensions and clarifies citations for related designs, including Ascon and inverse chi circuits.
Result
Let chi_n: GF(2)^n → GF(2)^n be the quadratic Boolean mapping defined componentwise by
(chi_n(x))_i = x_i + (x_{i+1} + 1) * x_{i+2}
with coordinate indices taken modulo n. Let chi_n^j denote the j-th iterate of chi_n.
- Degree and Monomial Structure:
For every dimension n ∈ {3, 4, ..., 13} and every iteration index j ≤ ⌊n/2⌋, the algebraic degree of every coordinate function satisfies
deg (chi_n^j)_i = j + 1
with a single top-degree monomial in the algebraic normal form.
- Image Size for Even Dimensions:
For even n, chi_n is non-bijective. For n ∈ {4, 6, 8, 10}, the image cardinality satisfies
|im(chi_n)| = 2^n - 2^{n/2}
yielding image sizes 12, 56, 240, and 992 respectively.
- Affine Equivalence:
The Ascon 5-bit substitution box S_Ascon decomposes as S_Ascon = B ∘ chi_5 ∘ A, where A and B are explicit affine transformations over GF(2)^5.
Setting and definitions
Let GF(2) denote the two-element finite field with addition + (XOR) and multiplication * (AND). For a Boolean function f: GF(2)^n → GF(2), the algebraic normal form (ANF) is its unique representation as a multilinear polynomial over GF(2). The algebraic degree deg(f) is the maximum degree among all monomials with coefficient 1 in its ANF. For a vectorial Boolean function F: GF(2)^n → GF(2)^n, deg(F) is the maximum algebraic degree among its coordinate functions.
The multiplicative complexity MC(F) in the XOR-free GF(2) straight-line program model is the minimum number of two-input AND gates needed to evaluate F over {AND, XOR, NOT}.
Method
Truth-table transforms for n = 3 through 13 up to iterate j = ⌊n/2⌋ yielded the ANFs, degrees, and monomial counts recorded in chi/out_s03c_topform.json and out_s01_basics.json.
Exhaustive image evaluation over GF(2)^n for even n ∈ {4, 6, 8, 10} verified the cardinality |im(chi_n)| = 2^n - 2^{n/2}. Multiplicative complexity bounds and affine decompositions were checked against candidates BC-08 and BC-11 in chi/BANK-CANDIDATES.md. Prior-art reconciliation followed manual audit of wave1-priorart/VERDICTS.md §1 and sources/kriepke-kyureghyan-2024-801.txt.
Discussion
This entry resolves registry misattributions and distinguishes analytic proofs from computational bounds:
- The degree growth theorem (deg chi_n^j = j + 1 for j ≤ ⌊n/2⌋ with a unique top monomial) was proven analytically for odd n by Kriepke and Kyureghyan (CRYPTO 2024, Theorem 1 and Lemma 2). Prior internal citations to Schoone and Daemen (2024) were incorrect; their paper contains no ANF or degree derivations.
- Kriepke and Kyureghyan's proof covers only odd n. The exhaustive evaluation here confirms that the degree growth rate and single-monomial structure hold for even dimensions through n = 13.
- Daemen (1995) proved that chi_n is bijective if and only if n is odd. For even n, the verified image sizes |im(chi_n)| = 2^n - 2^{n/2} match the collision counts in Schoone and Daemen (2024, §8.2).
- The affine decomposition S_Ascon = B ∘ chi_5 ∘ A is taken directly from the Ascon v1.2 specification.
- The multiplicative complexity upper bound of 3(n-1)/2 AND gates for chi_n⁻¹ (odd n) belongs to Liu, Sarkar, Meier, and Isobe (2022) and Biryukov, Bouillaguet, and Khovratovich (2014, Appendix D), not KeccakTools alone.
For everyone — the takeaway
What this means
This entry fixes attribution errors in internal records and confirms that the Keccak chi mapping gains exactly one degree of polynomial complexity per round up to half the state size, for both even and odd dimensions. These invariant properties help cryptanalysts evaluate how quickly ciphers like SHA-3 and Ascon resist algebraic attacks.
Attribution and prior art
Prior art: Lemma A for odd n is due to Kriepke-Kyureghyan (CRYPTO 2024), while even n collisions match results from Schoone-Daemen (2024). The inverse chi is credited to Liu et al. (2022) and Biryukov et al. (2014). Sources: ePrint 2024/801 · ePrint 2014/474
Register references
- Entry ID: MF-157
- Verification Receipts:
chi/out_s03c_topform.json,out_s01_basics.json,chi/BANK-CANDIDATES.md(BC-08, BC-11) - Audit and Prior Art:
wave1-priorart/VERDICTS.md§1,sources/kriepke-kyureghyan-2024-801.txt - Prior-Art Works:
- Kriepke & Kyureghyan, "Algebraic Structure of the Iterates of χ", CRYPTO 2024 (IACR ePrint 2024/801)
- Daemen, PhD thesis, 1995
- Schoone & Daemen, Designs, Codes and Cryptography 92 (2024)
- Liu, Sarkar, Meier, & Isobe, Journal of Cryptology 35(4):28 (2022)
- Biryukov, Bouillaguet, & Khovratovich, IACR ePrint 2014/474
- Ascon Specification v1.2
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 5 of 5 receipt files bundled (25 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.