[cryptography] New small circuits for predicates on four bits and AES sbox
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.
----- End forwarded message -----
More information about the cryptography