Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-128
Exact unrestricted multiplicative complexity of binary GF(8) multiplication
MC_XAG,F_2(F_8 × F_8 → F_8) = 6 in basis F_2[r]/(r^3 + r + 1)
Published 2026-09-04
For everyone
Plain summary
Digital chips, cryptography, and zero-knowledge proofs build logic out of basic gates. XOR gates (addition modulo two) are cheap in hardware area and cryptographic cost. AND gates (bit multiplication) are expensive. Multiplicative complexity measures the minimum number of AND gates needed to compute a function when XOR gates are free.
Multiplying two elements in the eight-element field GF(8) over binary bits requires exactly six AND gates in general feedforward circuits. Six gates suffice, and no circuit can do it in five or fewer. This lower bound holds in the unrestricted circuit model, which allows arbitrary intermediate wiring reuse rather than restricting the computation to simple algebraic formulas.
Result
Let F_8 be the degree-3 finite field extension of F_2 represented in the canonical polynomial basis F_2[r]/(r^3 + r + 1). The unrestricted 2-XAG multiplicative complexity of the field multiplication map is:
MC_XAG,F_2(F_8 × F_8 → F_8) = 6.
The lower bound MC_XAG,F_2(F_8 × F_8 → F_8) ≥ 6 is solver-independent: every two-plane in the 3-dimensional nonlinear output space requires at least 5 AND gates, and the prefix-section lemma rules out any 5-gate realization for the full three-component output. The upper bound MC_XAG,F_2(F_8 × F_8 → F_8) ≤ 6 is realized by the standard six-product circuit, verified against all 64 input pairs in F_8 × F_8.
Setting and definitions
The target map is binary field multiplication F_8 × F_8 → F_8, sending two 3-bit inputs (a0, a1, a2) and (b0, b1, b2) to the 3-bit product (c0, c1, c2) modulo the reduction polynomial r^3 + r + 1 = 0.
The execution model is the unrestricted acyclic XOR-AND graph (2-XAG) over F_2:
- Inputs are arbitrary F_2-affine combinations of primary inputs and the constant 1.
- XOR gates and F_2-affine transformations carry zero cost.
- AND gates compute the product of two F_2-affine forms over preceding node values and primary inputs.
- Multiplicative complexity MC_XAG,F_2(f) is the minimum count of 2-input AND gates in an acyclic circuit computing the vector-valued Boolean function f.
The output space is the 3-dimensional vector space spanned by the three nonlinear coordinate functions of the multiplication map over F_2.
Method
The exact complexity was proved via structural lower bounds combined with verified execution receipts:
- Lower bound: Analysis of the 3-dimensional linear span of the output coordinate functions over all 2-dimensional linear subspaces (two-planes) proved that each two-plane requires at least 5 AND gates. The prefix-section lemma then showed that computing the remaining output component within a 5-gate budget is impossible, ruling out any 5-gate acyclic XAG for the complete map.
- Upper bound: The standard 6-product algebraic construction was compiled into an explicit 2-XAG and evaluated against the complete 64-row truth table of F_8 × F_8, matching the target map on all inputs.
- Clean-room verification: The result was verified across eight independent evaluation seats in FREE-VERIFY.md, yielding sound verdicts with no solver dependency in the lower-bound proof.
Artifacts include the bootstrap receipt gf8-prefix-bootstrap.receipt.json, the exhaustive replay receipt gf8-six-product-replay.receipt.json, the clean-room verification receipt gf8-cleanroom.receipt.json, and the rerun receipt decisive-rerun.receipt.json.
Discussion
This result establishes the exact unrestricted acyclic 2-XAG multiplicative complexity of GF(8) multiplication. It applies across all unrestricted feedforward circuits with arbitrary XOR integration, not just bilinear circuits, symmetric-bilinear forms, or depth-one tensor rank decompositions.
Scope limits:
- The proof targets the canonical irreducible polynomial r^3 + r + 1 over F_2.
- The result applies specifically to the 3-output field multiplication map and does not imply an identical quadratic normal form cost for general multi-output Boolean maps with three or more outputs.
- Audit classification confirms evidence tier P + FR (proved with finite corroboration receipts), with all eight verification seats passing.
For everyone — the takeaway
What this means
This proof fixes the exact floor for GF(8) multiplication in hardware and zero-knowledge circuits. Optimizing nonlinear gates directly reduces circuit area, execution latency, and masking overhead in cryptographic implementations.
Because six AND gates is an absolute lower bound in this basis, circuit designers and synthesis compilers do not need to search for five-gate implementations. Existing six-gate designs are optimal.
Register references
- Entry: MF-128
- Verification record:
zkgolf-decomp/FREE-VERIFY.md - Proof documentation:
zkgolf-decomp/FREE-05.md - Bootstrap receipt:
zkgolf-decomp/free-05-scratch/gf8-prefix-bootstrap.receipt.json - Replay receipt:
zkgolf-decomp/free-05-scratch/gf8-six-product-replay.receipt.json - Clean-room receipt:
zkgolf-decomp/free-verify-scratch/gf8-cleanroom.receipt.json - Decisive rerun receipt:
zkgolf-decomp/free-verify-scratch/decisive-rerun.receipt.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 0 of 6 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.