AES S-box circuit with fewer than 113 gates

Find a smaller Boolean circuit for the AES S-box: a straight-line program over AND, XOR and XNOR gates that maps the 8 input bits to the 8 output bits of the S-box.

Bar to beat. 113 gates — 32 AND plus 81 XOR/XNOR, depth 27 — the Boyar–Peralta circuit. A shallower variant reaches depth 16 with 125 gates. A submission wins by using fewer gates in total, or fewer AND gates at equal size.

Submission format. The straight-line program: one line per gate, naming its operation and two inputs, with the last 8 signals the S-box output.

Verifier sketch. Parse the program, evaluate it on all 256 inputs, compare against the AES S-box table, and count gates by type. The domain is exhaustively checkable in microseconds — this is as cheap as verification gets.

Not written yet because the bar is multi-objective. Gate count, AND count (which dominates masked, threshold and MPC implementations) and depth (which sets latency) trade against each other, so the threshold has to be chosen and frozen before anyone submits. That is a product decision, not a coding one.

Known. The 113-gate circuit has stood as the reference since Boyar and Peralta's work on multiplicative-complexity minimization; incremental improvements are still reported for specific objectives such as AND-depth.

Why. The S-box is instantiated 16 times per AES round; its gate count sets area in hardware and its AND count sets the cost of every side-channel-protected or MPC implementation of AES.

Ref: Boyar–Peralta circuits · Wikipedia: Rijndael S-box