[cryptography] New small circuits for predicates on four bits and AES sbox

Jack Lloyd lloyd at randombit.net
Thu Jul 18 10:13:32 EDT 2013

An interesting result, and the link also has circuit representations
of the AES Sbox which they claim are smaller than any so far found -
one of them 32 AND gates, 83 XOR/NXOR, and depth 28.

----- Forwarded message from "Peralta, Rene" <rene.peralta at nist.gov> -----

Date: Thu, 18 Jul 2013 08:22:21 -0400
From: "Peralta, Rene" <rene.peralta at nist.gov>
To: Multiple recipients of list <hash-forum at nist.gov>
Subject: predicates on four bits, 4-bit S-boxes

I am posting this to the hash forum because the algebraic properties of functions on few bits should be of interest to this community.

There are more than 64,000 predicates on 4 bits, and no known algorithm for building optimal circuits for these predicates under the various metrics of interest for industrial applications or cryptanalysis.

The multiplicative complexity of a function is the number of AND gates needed to implement it over the basis AND,XOR,1 (the 1 is for negation). One cannot build a hash function without incurring a linear multiplicative cost (sort of) uniformly across every circuit that implements it.

The algebraic normal form of a function does not say much about this metric For example, it is not easy to build a circuit with minimum number of AND gates for a function such as

g(a,b,c,d) = abcd + abc + abd + acb + acd + ab + ac + ad + bc + bd + cd.

The following unexpected facts have been verified:

1) Every predicate on four bits can be implemented with at most 3 AND gates;
2) Every predicate on four bits, but of degree 3, can be implemented with 2 AND gates.

The circuits can be downloaded from


(see item 6: All predicates on 4 bits).

The circuits were verified by Chris Wood. Thanks to Meltem Turan, Cagdas Calik, and the rest of the Circuit Minimization Team.

Rene Peralta.

----- End forwarded message -----

More information about the cryptography mailing list