Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-147
Basis-free lower bound on the multiplicative complexity of GF(2^k) multiplication
MC(GF(2^k) multiplication) ≥ ⌈5k/2⌉ - 2 in the unrestricted XAG model, basis-free
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of AND gates needed to compute a function when XOR gates are free. Finite field multiplication over GF(2^k) is a fundamental building block in symmetric cryptography and error-correcting codes. This paper gives an analytical, basis-independent lower bound for the multiplicative complexity of field multiplication in the unrestricted circuit model: computing the product requires at least ceil(5k/2) - 2 AND gates for any extension degree k.
The bound holds for all field sizes and rests entirely on trace non-degeneracy. It matches exact values for small fields, giving 3 multiplications at k = 2 and 6 at k = 3. For larger fields, it establishes new floors: 8 at k = 4, 11 at k = 5, and 13 at k = 6. Prior bounds focused on restricted bilinear models, while determining the exact multiplicative complexity for functions on 5 or more bits remains an open problem recognized by NIST. The proof technique cannot exceed 8 at k = 4, leaving the bracket [8, 9] open.
Result
Let GF(2^k) denote the finite field of size 2^k, and let MC denote multiplicative complexity over GF(2) in the unrestricted XOR-AND graph (XAG) model.
Theorem E: MC(GF(2^k) multiplication) ≥ ⌈5k/2⌉ - 2
This lower bound is basis-free, holding for any choice of basis used to represent field elements.
Specific bounds established by the theorem include:
- k = 2: MC ≥ 3 (tight; exact MC is 3, matching MF-120)
- k = 3: MC ≥ 6 (tight; exact MC is 6, matching MF-128)
- k = 4: MC ≥ 8 (establishes the bracket [8, 9], where bilinear rank is 9)
- k = 5: MC ≥ 11 (establishes the bracket [11, 13])
- k = 6: MC ≥ 13
Evidence classification:
- Tier P (analytic proof) for all k
- Tier FC (fully certified) for k = 2, 3, 4, 5
Setting and definitions
Let GF(2^k) be the Galois field of 2^k elements viewed as a k-dimensional vector space over GF(2). Field multiplication is the map (x, y) ↦ x · y. A basis-free bound applies under a polynomial basis, a normal basis, or any linear isomorphism to GF(2)^k.
The circuit model is the unrestricted XOR-AND graph (XAG) over GF(2), where two-input XOR gates cost 0 and two-input AND gates cost 1. The multiplicative complexity MC(f) of a multi-output Boolean function f is the minimum number of AND gates across all valid XAG implementations of f.
Trace non-degeneracy refers to the property that the symmetric bilinear trace pairing (x, y) ↦ Tr(x · y) is non-degenerate over GF(2^k), where Tr(z) = sum_{i=0}^{k-1} z^(2^i).
Method
The bound is derived analytically using only the trace non-degeneracy of field multiplication, without selecting a specific coordinate basis for GF(2^k).
The derivation yields the exact multiplicative complexity of 6 at k = 3 directly, without automated search. For dimensions k = 2 through k = 5, the lower bounds and brackets are computationally certified against exhaustive gate-configuration searches.
Receipt artifacts recording the proof and data:
- geometry/REPORT.md §5
- sweep_results.json
Discussion
Classical lower bounds on finite field multiplication (Chudnovsky–Chudnovsky, Shparlinski–Tsfasman–Vlăduţ, Ballet et al.) address bilinear complexity and tensor rank, a restricted model where non-linear gates cannot take intermediate non-linear outputs as inputs. Theorem E bounds the unrestricted XAG model, where non-linear gates compose arbitrarily. This addresses the domain where NIST notes the exact multiplicative complexity of vectorial Boolean functions on 5 or more bits as an open problem.
Scope limitations and refutations:
- Refutation R4: The trace non-degeneracy argument has a structural ceiling at 8 for k = 4. The remaining gap in the bracket [8, 9] at k = 4 cannot be closed using this technique alone (recorded under ML-076).
For everyone — the takeaway
What this means
Multiplication in finite fields is central to cryptography, including AES and zero-knowledge proof systems. In these systems, multiplications carry heavy computational and hardware costs, whereas additions are essentially free. Knowing the minimum number of multiplication steps shows where circuit optimization must stop and provides a baseline for evaluating implementations. Theorem E provides a coordinate-independent floor for all field dimensions, proving that field multiplication requires at least ceil(5k/2) - 2 multiplications regardless of representation.
Attribution and prior art
Prior art: This result appears to be new: existing bilinear and tensor-rank literature (Chudnovsky–Chudnovsky; Shparlinski–Tsfasman–Vlăduţ; Ballet et al.) bounds a different model, and NIST lists the multiplicative complexity (MC) of vectorial functions on `>= 5` bits as an open problem.
Register references
- Register entry: MF-147
- Related entries: MF-120, MF-128, ML-076
- Artifacts: geometry/REPORT.md §5, sweep_results.json
- Prior art: Chudnovsky–Chudnovsky; Shparlinski–Tsfasman–Vlăduţ; Ballet et al.
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.