Research · Papers · Cipher S-boxes, χ, and quantum gate counts · ML-076
Multiplicative complexity bracket for GF(2^4) multiplication
MC(GF(2^4) multiplication) ∈ [8, 9] in the unrestricted model
Published 2026-09-04
For everyone
Plain summary
Multiplying numbers in finite fields is a core operation in cryptography and error-correcting codes. Multiplicative complexity measures the minimum number of nonlinear AND gates needed to evaluate a function when linear XOR gates are free.
Standard structured designs for multiplication in the 16-element field GF(2^4) use 9 multiplications. In the unrestricted Boolean circuit model, the exact multiplicative complexity lies in [8, 9]. If an 8-multiplication circuit exists, it cannot be bilinear or quadratic; it must feed intermediate nonlinear outputs directly into later multiplication gates. Whether the minimum is 8 or 9 remains open.
Result
In the unrestricted circuit model over GF(2):
MC(GF(2^4) multiplication) ∈ [8, 9]
The same [8, 9] bracket applies to 4-bit polynomial multiplication, polymul_4.
Because quadratic complexity is 9 (MF-167), any 8-AND circuit for GF(2^4) multiplication must feed at least one non-affine intermediate wire into an AND gate.
Setting and definitions
Let MC(f) denote the multiplicative complexity of a multi-output Boolean function f over GF(2), defined as the minimum number of 2-input AND gates in an XOR-AND graph (XAG) computing f from primary inputs and the constant 1.
The unrestricted model permits arbitrary XAG topologies, allowing AND gate inputs to be affine combinations of primary inputs and preceding AND outputs. The quadratic model restricts every AND gate input to affine combinations of primary inputs.
Let V denote the 4-dimensional class space associated with the GF(16) multiplication tensor. The 3-form transfer is the structural condition under which lower bounds from trilinear or quadratic forms transfer directly to unrestricted XAGs.
Method
The upper bound of 9 AND gates comes from the quadratic model classification in MF-167.
The lower bound constraints follow from THEOREM E (MF-147) and its refutation R4 at k = 4, which establish that this lower-bound mechanism cannot exceed 8 at dimension k = 4.
Scoping calculations and sweep data from wave1-gf16/REPORT.md §3 (recorded in m3_sweep_result.json) show that brute-force refutation of all 8-AND XAG candidate architectures on 8 inputs with dim V = 4 chained structure requires execution times >> 1e6 s without symmetry breaking.
Discussion
Settling the exact value within [8, 9] requires one of two paths:
- Algebraic: prove the 3-form transfer specifically for the 4-dimensional class space V of GF(16) multiplication. This is a targeted claim on V rather than a proof for arbitrary tensors.
- Direct refutation: run an exhaustive search or SAT refutation over all 8-AND XAGs on 8 inputs with dim V = 4 chained structures. As shown in wave1-gf16/REPORT.md §3, an unoptimized search requires >> 1e6 s; closing via this route requires symmetry breaking.
The [8, 9] bracket is also inherited by polymul_4. The problem remains open.
For everyone — the takeaway
What this means
Multiplying elements in GF(16) is a basic operation in cryptographic hardware. Standard circuits use 9 multiplications, and no known proof rules out a design with 8. Saving that single gate requires a non-standard layout where multiplication outputs feed directly into subsequent multiplications. Deciding whether 8 gates suffice will take either an algebraic transfer proof for this specific space or automated SAT verification with symmetry breaking.
Register references
- Entry: ML-076
- Theorem E: MF-147 (with refutation R4)
- Quadratic model classification: MF-167
- Artifacts:
wave1-gf16/REPORT.md§3,m3_sweep_result.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 2 of 2 receipt files bundled (10 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.