Cryptography · Swapnil Jain’s repository · Aska contributed
Fewer gates for the arithmetic inside AES
AES, the cipher that protects most web traffic and encrypted disks, does its mixing in a strange 256-number world. Swapnil Jain, searching with AI help and checking every result by machine, cut the wiring for its multiplication from 117 gates to 112 and built its one nonlinear step from 106 gates. Aska added multipliers for four more number systems.
Swapnil Jain’s repository and two preprints. Aska Digital contributed one pull request, merged as #1 on 11 October 2026: verified multiplier circuits for four more number systems, built with the papers’ own method. GF(29) in 136 gates against a 142-gate baseline, GF(210) in 172 (equal to its baseline), GF(211) in 199 against 206, and the GHASH field GF(2128) in 11,972 (equal). They are not records, sit outside the author’s hash commitment, and have no Lean proofs.
RepositoryMultiplier preprintS-box preprintAska’s PR #1Multiplier on the LedgerS-box on the Ledger
All 65,536 products in the AES field, computed by the 112-gate circuit
How to read: row a, column b, both 0 to 255. A lit cell means the chosen output bit of a × b is 1. Point at a cell, or focus the figure and use the arrow keys.
Checking every product against long multiplication…
- 117 → 112gates to multiply in the AES field at the 2010 record’s depth (6); 107 if you allow depth 13multiplier preprint Tables 1–2
- 106gates for the AES S-box from AND, XOR and XNOR gates; the smallest found before was 110 (NIST, 2026), which is shallower: depth 22 against 24S-box preprint Table 1 · On the Ledger
- 109gates for the inverse S-box, against 112 (NIST, 2026); deeper, 30 against 26sbox/verify_results.txt
- 30Lean 4 kernel proofs: 19 multipliers and 11 S-boxes, standard axioms onlymultipliers/lean · sbox/lean
00//Gates
First principlesA computer multiplies with switches.
Underneath every program are gates: tiny switches that take two bits and give back one. An AND gate says “both”. An XOR gate says “exactly one”. Wire enough of them together and you can compute anything. The question here is how few you need.
The arithmetic in question is strange but simple. Write a number as 8 bits. To add two numbers, XOR them bit by bit, with no carries. To multiply, do grade-school long multiplication, but add the columns with XOR instead of ordinary addition. The answer spills past 8 bits, so fold the overflow back in by a fixed rule: wherever x8 appears, write x4 + x3 + x + 1 instead.
AES, the cipher that protects most web traffic and disk encryption, does all of its mixing in this field. Its one nonlinear step, the S-box, takes each byte’s inverse in the field and then scrambles the bits.
Why count gates? On a chip, each gate costs area and power. In “bitsliced” software, each gate is one processor instruction, applied to many blocks at once. Building the arithmetic from gates also avoids lookup tables, which can leak secrets through how long memory takes to answer.
A circuit’s depth is the longest chain of gates a signal passes through, one after another. It stands in for how long the answer takes.
Why is it hard? The number of possible wirings explodes, and even a computer cannot search them all: an exact search for a 16-input circuit of more than 100 gates is out of reach. So records sit still for years. The 117-gate multiplier for the AES field dated from July 2010. Nobody can currently prove that any of these circuits is the smallest possible, and the papers claim no such thing.
01//A 16-number world
Live circuitLong multiplication, without the carries.
Shrink the field to 4 bits and the whole circuit fits on a screen. The 16 numbers multiply by the same recipe, with the fold rule x4 = x + 1. Pick two numbers and watch 30 gates compute their product.
Multiply in GF(24): the working, and the circuit that does it
How to read: set a and b with the bit buttons, or press a cell of the table. Left, the long multiplication and the fold. Right, the circuit, read top to bottom: squares are AND gates, circles are XOR gates; a filled gate or a strong wire carries 1, a hollow gate or a faint wire carries 0. Switch circuits to compare gate counts.
The schoolbook circuit multiplies every bit of a by every bit of b: 16 ANDs. Jain’s circuit first forms a few sums of input bits (8 XORs), multiplies those sums in pairs (only 10 ANDs), then combines the 10 products into the 4 output bits, doing the fold at the same time (12 XORs). Spending a little on preparation buys fewer multiplications.
That is Karatsuba’s 1962 trick, generalised: to multiply two 2-part numbers you need only 3 products instead of 4, if you pay a few extra additions first. For four bits the trick saves one gate overall. For the AES field it saves more, as the next section shows.
02//The size–speed staircase
Smaller or faster: pick one.
There is no single best circuit. At the 2010 record’s speed, multiplication in the AES field drops from 117 gates to 112. Allow twice the depth, and it drops to 107.
Every multiplier of this kind can be drawn in three layers: prepare (XORs that form sums of input bits), multiply (ANDs that multiply pairs of those sums) and clean up (XORs that combine the products into the 8 output bits, folding as they go).
Jain’s search samples many recursive mixes of schoolbook splits and Karatsuba splits, solves exactly for the best clean-up layer of each, and scores every candidate by its total gate count. The earlier approach of Find and Peralta minimised the number of ANDs first.
Compare the layers of the 2010 record and the new 112-gate circuit at the same depth: preparation grows from 8 XORs to 20, but the ANDs fall from 48 to 36 and the clean-up from 61 XORs to 56. Different products, cheaper overall.
AES-field multipliers: gates against depth, 2010 → 2026
How to read: lower is smaller, further left is faster. Slide the depth budget; the ring marks the smallest circuit that fits, and the bars below split it into its three layers. Point at or focus any mark.
- 2010 record · 117 gates
- Jain 2026 · the best at each depth
- Jain 2026 · other steps of the search
Show the numbers
03//AES’s secret ingredient
The one step of AES that is not just XOR, in 106 gates.
Most of AES is XORs and fixed shuffles. The S-box replaces each byte by its inverse in the 256-number world, then scrambles the bits. Software usually looks it up in a 256-entry table; built from gates, it needs no table, so there is no secret-dependent memory access for a timing attack to watch. Run the actual circuit here.
The S-box circuit, gate by gate
How to read: the input byte’s 8 bits enter on the left (at the top on a narrow screen); every gate sits in the column of its depth (squares AND, circles XOR, ringed circles XNOR), and a filled gate is outputting 1. Faint lines are the wires: point at a gate to light the two wires that feed it and the ones it feeds. The 8 bits at the far end are the answer, checked against the standard’s table below. Type a byte, step with the arrows, or press a table cell.
Not run yet. The repository’s Lean proof of the same fact takes 8 to 9 seconds.
Smallest S-box circuits found, AND / XOR / XNOR gates only
Dots on a gate-count scale; the number after each is its depth. Richer gate sets (NAND, NOR, multiplexers) already reach 102 gates (Maximov and Ekdahl, 2019), so the comparison holds only in this model.
Show the comparison as a table
| Circuit | Gates | AND + XOR + XNOR | Depth | Closest published circuit in the same model |
|---|---|---|---|---|
| S-box, Jain 2026 | 106 | 34 + 69 + 3 | 24 | NIST 2026: 110 at depth 22. Boyar–Peralta / Calik: 113 at depth 27 |
| S-box, Jain 2026 | 121 | 34 + 83 + 4 | 16 | CMT: 125 at depth 16 (likely a local edit of it: 86% of gate functions shared). NIST: 125 at depth 15 |
| Inverse S-box, Jain 2026 | 109 | 32 + 71 + 6 | 30 | NIST 2026: 112 at depth 26. CMT: 121 at depth 21 |
Intermediate points (116 at depth 17, 112 at 18, 111 at 21) are in the preprint’s Table 1. The AND count, 32 to 34, is about that of earlier work, so the preprint claims no gain for masked implementations, where ANDs dominate the cost.
The 106-gate circuit came from a sweep over 244,800 ways of writing the field, followed by random walks that keep the gate count while reshaping the circuit. Walks within AES’s usual way of writing the field stalled at 110. The search code is not released, so these circuits can be checked by anyone but not regenerated.
The comparison is honest about its limits. The 106 is smaller than NIST’s 110 but deeper, 24 against 22. NIST’s own list asks for 105 gates or fewer, so the 106 is one gate short of that wish. And the comparison holds only for circuits made of AND, XOR and XNOR gates.
04//Aska’s part
Four more number systems, checked, and not records.
Our agentic team applied the papers’ method to fields of 9, 10, 11 and 128 bits that had no dedicated published circuit, and Swapnil Jain merged the result the same day. You can re-check three of them on every input, here.
The method was Jain’s, applied to new fields. Take the published product circuit of Find and Peralta for m-bit polynomials, keep its products, merge the fold into the clean-up layer, and re-optimise both XOR layers with the repository’s own tool. Then sweep the depth, and try small exact searches (“window SAT”) for local improvements; thousands of windows were tried and none improved.
What it gained. GF(29) came in 6 gates below its baseline and GF(211) 7 below; GF(210) and the GHASH field of AES-GCM only matched theirs, and say “no gain claimed”. The baseline is the published product circuit plus a textbook fold, not a published record: for these fields no dedicated circuit was found. The AND counts (54, 52, 78) are exactly Find and Peralta’s, so every gate saved is an XOR.
Multipliers for other fields: gates saved against a simple baseline
How to read: each row is one field, with its baseline and circuit gate counts; the bar is the number of gates saved, and the percentage is of the baseline. Red-ruled rows are Aska’s contributions; the rest are Jain’s. Point at or focus a row.
- Aska’s contribution
- Baseline · published product circuit + simple fold
5,505,024 products to check: every pair of inputs for GF(29), GF(210) and GF(211).
Show the numbers
| Field | By | Baseline | Circuit (AND + XOR) | Depth | Saved |
|---|---|---|---|---|---|
| GF(24) | Jain | 31 | 30 (10 + 20) | 5 | 1 |
| GF(25) | Jain | 49 | 44 (20 + 24) | 6 | 5 |
| GF(29), x9+x4+1 | Aska | 142 | 136 (54 + 82) | 7 | 6 |
| GF(210), x10+x3+1 | Aska | 172 | 172 (52 + 120) | 8 | 0 |
| GF(211), x11+x2+1 | Aska | 206 | 199 (78 + 121) | 8 | 7 |
| GF(212) | Jain | 229 | 210 (78 + 132) | 17 | 19 |
| GF(213) | Jain | 303 | 283 (94 + 189) | 29 | 20 |
| GF(2128), GHASH | Aska | 11,972 | 11,972 (3,888 + 8,084) | 20 | 0 |
GHASH is left out of the chart because it would dwarf the scale. Aska also built a depth-6 variant of GF(29) with 144 gates.
05//How anyone can check
Re-run by Foundation0 · 13 Oct 2026The search was AI-assisted. The trust comes from somewhere else.
Both preprints say: “Computational search and drafting were assisted by AI tools; all released circuits were machine-verified.” No tool is named. What makes the circuits believable is that anyone can check them in seconds.
- 1
Every input
Each circuit is run on every possible input, 65,536 pairs for an AES-field multiplier and 256 bytes for an S-box, against an independent reference. This page does it again in your browser.
- 2
Every formula
Each output bit’s exact algebraic formula must equal the one multiplication defines. This is how the 128-bit circuits are checked, where listing inputs is impossible.
- 3
Broken on purpose
Deliberately damaged circuits and a wrong field must be rejected. That shows the checker can say no; it is not extra evidence for the circuits.
- 4
Machine proof
Lean 4’s kernel proves 30 of the circuits correct. The theorem checks a generated gate list; for the S-box it proves equality with a written-out table, and that the table is AES’s rests on the Python verifier. Gate counts and depths are not Lean-checked.
- 5
Committed in advance
SHA-256 fingerprints of the circuit files were posted in two public gists on 11 Oct 2026, before the preprints. The author calls this a weak timestamp, since a gist can be edited.
What Foundation0 re-ran
On a scratch copy of the repository: the multiplier verifier on every committed circuit and on Aska’s (all pass, with gate counts exactly as published); the S-box verifier on all 11 circuits (output identical to the saved results); the commitment fingerprints (both match the live gists); and five of the Lean proofs, including the 106-gate S-box, with the official Lean 4.34.1 release. The generator rebuilds the Lean file for the 112-gate circuit byte for byte from the circuit file, so the proof is about that exact circuit.
What remains open
Both papers are single-author preprints from October 2026, posted on ResearchGate and not peer reviewed. “Smallest known” is only as good as the author’s literature check, which the author calls “not a systematic survey”. The author knows of no non-trivial lower bound on total gates, so nobody can say how close any of these circuits is to the smallest possible.
The field is busy: NIST’s list was updated on 6 October 2026 and records S-box circuits contributed by Milad Nasr of Anthropic on 24 September 2026.
The repository
Aska’s contribution
Circuits on this page are copied from Swapnil Jain’s gf2m-circuits (code and circuits Apache-2.0, papers CC BY 4.0, © 2026 Swapnil Jain), including the circuits ahrazzle contributed there; prior-work circuit files by others are not copied, only their published numbers. The evaluators, charts and the schoolbook GF(24) circuit are new code written for this page; the repository itself has no project website.