Boolean Circuit Discovery

Boolean circuits implement functions with elementary gates such as AND, XOR and NOT. In cryptographic applications, nonlinear AND gates can be especially costly, while circuit depth affects latency. These are related but distinct objectives.

The public index currently records three verified AES S-box circuits with 29 AND gates: 161 XOR at depth 31; 158 XOR at depth 30; and 159 XOR at depth 29. The latter two results form a trade-off rather than a single winner.

These releases improve affine realizations of a fixed 29-AND construction. They are not claims to the smallest or shallowest AES S-box circuit overall; established 32-AND circuits can use fewer total gates or have lower ordinary depth.

Public record

The NIST Circuit Complexity list credits Nicolas for the 158-XOR / depth-30 and 159-XOR / depth-29 transformations. These are public entries in a technical circuit collection, not journal publications.

René Peralta separately confirmed that an earlier 161-XOR circuit had been verified. That email does not extend the verification to the later 158-XOR or 159-XOR circuits. A Zenodo record archives the later results.