Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-156
The k-window law for joint multiplicative complexity of Chi iterates
MC(chi_n, ..., chi_n^k) = k n for 1 <= k <= floor(n/2), sharp in k; joint rank drops below k n at k = floor(n/2) + 1
Published 2026-09-04
For everyone
Plain summary
Ciphers such as Keccak (the basis of SHA-3) and Xoodoo process data in rounds using a non-linear mixing step called Chi. In hardware and secure computation, the cost of these steps is measured by the number of AND gates (multiplications), while XOR gates (additions) are treated as free.
This work determines the exact AND-gate cost of evaluating several consecutive rounds of Chi simultaneously. For an n-bit Chi transformation across the first k rounds, the total cost is exactly k times n, provided k does not exceed floor(n/2). Within this window, later rounds cannot reuse multiplications from earlier ones. Once k reaches floor(n/2) + 1, algebraic shortcuts emerge and the combined cost drops strictly below k times n. Unrolling rounds within the window yields zero non-linear savings, but savings begin immediately past it.
Result
For the Chi permutation chi_n on n bits over GF(2), the joint multiplicative complexity of exposing the first k iterates satisfies:
MC(chi_n, chi_n^2, ..., chi_n^k) = k n
for all integers k in the range 1 <= k <= floor(n/2).
The bound is sharp in k: at k = floor(n/2) + 1, the joint nonlinear rank drops strictly below k n for every tested width:
- For n = 4 and n = 5, the three-power joint complexity MC(chi_n, chi_n^2, chi_n^3) equals 2n rather than 3n.
- At n = 5, this drop occurs because chi_5^3 = chi_5^-1.
- At n = 3, chi_3^2 = id, yielding MC(chi_3^2) = 0 and MC(chi_3, chi_3^2) = 3, confirming that the condition n >= 4 in iterate-chain bounds is necessary and tight.
Setting and definitions
Let chi_n: GF(2)^n -> GF(2)^n denote the quadratic Chi permutation with coordinate functions chi_n(x)_i = x_i + (x_{i+1} + 1) x_{i+2}, with index arithmetic modulo n.
The cost metric is standard GF(2) XOR-free multiplicative complexity MC(f), defined as the minimum number of 2-input AND gates in a straight-line Boolean circuit computing target vector f using unbounded XOR gates and arbitrary constants.
For an iterate chi_n^j, the top form is its homogeneous algebraic component of maximal degree. Degree layer independence across powers j = 1, ..., k is determined by the joint nonlinear rank of the combined coordinate forms.
Method
The proof evaluates the top algebraic forms of the coordinates of chi_n^j for j <= floor(n/2).
- Top form structure: For each j <= floor(n/2), the top form of coordinate i in chi_n^j is the single monomial x_{i+1} x_{i+3} ... x_{i+2j-1} x_{i+2j} of degree j + 1.
- Degree layer independence (Lemma A): Each successive iterate raises the monomial degree by 1 without algebraic wrap-around interference in this window, leaving the k distinct degree layers linearly independent over GF(2). The joint nonlinear rank of (chi_n, ..., chi_n^k) is therefore exactly k n.
- Upper bound construction: Cascading k literal Chi layers evaluates (chi_n, ..., chi_n^k) using exactly k n multiplications.
Evidence tiers:
- Analytical proof tier P for odd n given Lemma A (Kriepke–Kyureghyan, MF-157).
- Full certificate verification tier FC for all n <= 13 (including even n).
- k-sharpness verification tier FC for widths n = 3 through 11.
Verification artifacts:
- chi/out_s02_powers_joint.json
- out_s03_degree_layers.json
- out_s03c_topform.json
- out_s01_basics.json
- out_s12_eps.json
Discussion
The window law holds strictly for k <= floor(n/2). At k = floor(n/2) + 1, algebraic relations across iterates collapse the independence of the degree layers.
Boundary behaviors:
- At n = 3: chi_3^2 = id gives MC(chi_3^2) = 0 and MC(chi_3, chi_3^2) = 3. This establishes that the n >= 4 restriction in related bounds (such as MF-134) is necessary, and that the literal formula value eps_3 = 6 is an artifact whose true value is 3.
- At n = 4: the target (chi_4, chi_4^2, chi_4^3) has joint rank 2n = 8 instead of 3n = 12.
- At n = 5: the relation chi_5^3 = chi_5^-1 prevents the third power from introducing independent nonlinear degrees beyond the second, fixing the joint rank at 2n instead of 3n.
Prior art relationship: Kriepke and Kyureghyan bounded Hadamard products for a single iterate of Chi using degree arguments. The joint-exposure vector formulation across multiple iterates and the exact threshold k = floor(n/2) are new here. The identity chi_3^2 = id is known from the Schoone–Daemen order formula for small Chi permutations.
For everyone — the takeaway
What this means
Hardware and side-channel implementations of Keccak or Xoodoo often unroll consecutive rounds to increase throughput. This result shows that across the first floor(n/2) rounds, unrolling cannot reduce total non-linear gate counts: computing k rounds together requires k times the cost of a single round. Multiplicative savings become possible only once unrolling depth exceeds floor(n/2) rounds.
Attribution and prior art
Prior art: Kriepke–Kyureghyan previously bounded Hadamard products for a single iterate using degree arguments, and the Schoone–Daemen order formula already established `chi_3^2 = id`. The joint-exposure vector statement and the `k = floor(n/2)` threshold were not located in prior literature.
Register references
- Register Entry: MF-156
- Related Register Entries: MF-134, MF-157
- Prior Art: Kriepke–Kyureghyan (Hadamard product single iterate bounds); Schoone–Daemen (order formulas for Chi permutations)
- Receipt Artifacts: chi/out_s02_powers_joint.json, out_s03_degree_layers.json, out_s03c_topform.json, out_s01_basics.json, out_s12_eps.json
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 (4 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.