Research · Papers · Cipher S-boxes, χ, and quantum gate counts · MF-176
Exact multiplicative complexity of all 16 optimal 4-bit S-box classes and standard ciphers
MC=5 for G0,G1,G2,G5,G8,G9,G12,G15,G4,G10,G14; MC=4 for G3,G6,G7,G11,G13; MC(PRINCE)=5, MC(PRESENT,GIFT,RECTANGLE,Piccolo,SKINNY)=4
Published 2026-09-04
For everyone
Plain summary
Block ciphers protect digital data by running bits through substitution tables called S-boxes. These tables provide the non-linear scrambling that keeps encrypted data secure against mathematical attacks. In zero-knowledge proofs, secure multi-party computation, and tiny microchips, non-linear AND gates cost far more time and energy than linear XOR gates. Multiplicative complexity counts the minimum number of AND gates needed to build an S-box.
This work settles the exact multiplicative complexity for all 16 optimal 4-bit S-box equivalence classes classified by Leander and Poschmann, along with the S-boxes of six major lightweight ciphers: PRESENT, GIFT, RECTANGLE, Piccolo, PRINCE, and SKINNY. Every optimal 4-bit S-box requires either 4 or 5 AND gates.
Result
For all 16 Leander-Poschmann affine equivalence classes G0 through G15 of optimal 4-bit S-boxes F: GF(2)⁴ → GF(2)⁴ and six lightweight cipher S-boxes, the exact multiplicative complexity MC(F) is:
- Classes G0, G1, G2, G5, G8, G9, G12, and G15:
Every nonzero linear combination of coordinate functions has algebraic degree 3 (zero quadratic components among the 15 nonzero combinations). The packing parameter is mu(V) = 2, giving MC(F) ≥ 4 + 2 - 1 = 5. Explicit 5-AND circuits match this lower bound, establishing MC(F) = 5.
- Classes G3, G6, G7, G11, and G13:
Each class contains 1 quadratic and 14 cubic output combinations. The packing parameter is mu(V) = 1, giving a lower bound of 4. Explicit 4-AND circuits match this bound, establishing MC(F) = 4.
- Classes G4, G10, and G14:
Each class contains 1 quadratic and 14 cubic output combinations. Circuit synthesis establishes MC(F) = 5.
- Lightweight cipher S-boxes:
- PRESENT: MC = 4
- GIFT: MC = 4
- RECTANGLE: MC = 4
- Piccolo: MC = 4
- PRINCE: MC = 5 (all 15 nonzero output combinations have degree 3, giving MC ≥ 5 via packing)
- SKINNY: MC = 4
Setting and definitions
Let F: GF(2)⁴ → GF(2)⁴ be a 4-bit S-box with coordinate functions (f₀, f₁, f₂, f₃). A Boolean circuit over (AND, XOR, NOT) computes F using 2-input XOR and NOT gates alongside a minimal number of 2-input AND gates. The multiplicative complexity MC(F) is the minimum number of AND gates across all valid circuit realizations of F over this basis.
The 16 Leander-Poschmann classes G0 through G15 comprise all optimal 4-bit S-boxes under affine equivalence, maximizing differential and linear resistance.
For an S-box F, the linear span V of coordinate functions contains 15 nonzero components v · F = c₀ f₀ + c₁ f₁ + c₂ f₂ + c₃ f₃ for nonzero c in GF(2)⁴. The algebraic degree deg(g) is the degree of the algebraic normal form of g. The packing parameter mu(V) measures the dimension of high-degree components in V, yielding the packing bound (MF-137): MC(F) ≥ n + mu(V) - 1
Method
Exact values were established through analytical lower bounds paired with verified synthesis:
- Lower bounds (Tier P):
For G0, G1, G2, G5, G8, G9, G12, G15, and PRINCE, degree profiling confirms that all 15 nonzero coordinate combinations have algebraic degree 3. Applying the packing lemma (MF-137) gives mu(V) = 2, yielding the lower bound MC(F) ≥ 4 + 2 - 1 = 5 without SAT solving. For G3, G6, G7, G11, G13, G4, G10, and G14, the single quadratic component sets the baseline lower bound MC(F) ≥ 4.
- Upper bounds and synthesis (Tier FR):
Synthesized circuits using 4 AND gates (for G3, G6, G7, G11, G13, PRESENT, GIFT, RECTANGLE, Piccolo, and SKINNY) and 5 AND gates (for G0, G1, G2, G5, G8, G9, G12, G15, G4, G10, G14, and PRINCE) were verified against full truth tables across all 16 inputs in GF(2)⁴.
Synthesis and verification routines are implemented in wave2-sbox-atlas/sbox_atlas.py, with results logged in wave2-sbox-atlas/sbox_atlas_results.json.
Discussion
This classification settles the multiplicative complexity of all optimal 4-bit S-box affine equivalence classes.
The results delineate the scope of the packing lemma (MF-137). For the eight all-cubic classes (G0, G1, G2, G5, G8, G9, G12, G15), the packing parameter mu(V) = 2 gives a tight lower bound of 5 directly. For G4, G10, and G14, mu(V) = 1 yields a lower bound of 4, but structural circuit constraints raise the actual complexity to MC = 5.
For cipher deployments, PRINCE belongs to the all-cubic family and requires 5 AND gates, while PRESENT, GIFT, RECTANGLE, Piccolo, and SKINNY achieve the optimal 4-bit minimum of 4 AND gates.
The register notes no prior-art disputes or corrections.
For everyone — the takeaway
What this means
In privacy-preserving cryptography, such as multi-party computation and homomorphic encryption, AND gates account for nearly all computational and communication overhead.
Determining the exact AND-gate cost for every optimal 4-bit S-box lets cipher designers pick optimal components without running heuristic circuit searches. Implementers know in advance which S-box classes achieve the theoretical floor of 4 AND gates and which require 5.
Register references
- Entry ID: MF-176
- Prior entry: MF-137 (packing lemma)
- Receipts: wave2-sbox-atlas/sbox_atlas_results.json, wave2-sbox-atlas/sbox_atlas.py
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 (3 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.