Projects Circuit Complexity Circuit Problems
Circuit Complexity
Circuit Problems
The Circuit Minimization Team has been studying the following problems.
PDF renderings use the following notations (when present):
Red nodes: AND gates;
Yellow nodes: XOR gates;
Gray nodes: XNOR gates;
Ai, Bi: coefficients of polynomials A, B;
Ci: coefficient of C = A*B.

Multiplication in GF(2^{6}) using irreducible polynomial x^{6} + x^{3} + 1

Multiplication in GF(2^{7})
 Using irreducible polynomial x^{7} + x^{4} + 1
 Using irreducible polynomial x^{7} + x^{3} + 1

Multiplication in GF(2^{8}) using the AES polynomial x^{8} + x^{4} + x^{3} + x + 1

Binary Multiplication
This is an old and muchstudied problem. It can also be viewed as that of multiplication of polynomials of degree n over GF(2). Dan Bernstein's results at Highspeed cryptography in characteristic 2 have been recently improved by Murat Cenk and M. Anwar Hasan (see Some New Results on Binary Polynomial Multiplication.) Further improvements are shown below.
Here, M(n) is the minimum number of bit operations (ANDs and XORs) needed to multiply two polynomials of degree n1 .It is not hard to show that M(n) ≤ M(n1) + 4(n1).
Below are a few circuits synthesized in the last few years. Our software needs to be rewritten in order to synthesize circuits for polynomials of degree larger than 20 or so.
 M(11) ≤ 186
 M(12) ≤ 207 (and therefore M(13) ≤ 255)
 M(15) ≤ 312
 This example illustrates why we think the values of M(n) are mostly unknown. Bernstein's 2009 circuit has 329 gates. Cenk and Hasan improved this to 317 gates in 2015.
 Circuit with 312 gates and depth 9.
 M(16) ≤ 349 (and therefore M(17) ≤ 413)
 M(18) ≤ 454
 M(19) ≤ 498
 M(20) ≤ 527

The Sbox of AES
 Circuit for the Sbox of AES. The circuit is described as a straightline program using ANDs, XORs, XNORs (PDF rendering). As far as we know, this circuit improves over all previously published constructions. It uses 32 AND gates and 83 XOR/XNOR gates and has depth 28.
 The above circuit contains three parts: a top linear part, a middle nonlinear part, and a bottom linear part. For several years we believed the top and bottom linear parts could not be reduced in size. This was proved by the SATsolver community for the top linear part (size 23), but they were unable to do the same for the bottom linear part. In 2013, Visconti and Schiavo showed that our circuit for the bottom linear part was suboptimal by at least one gate. Cagdas Calik then pointed out that the BP heuristic,when run exploring all ties, yields a circuit with 113 gates. Further processing yields a circuit with size 113 and depth 27.
 Circuit for the reverse direction of the SBox, with size 121 and depth 21. We have not worked much on this. The size can probably be reduced.
 The SBox can be reduced to depth 16 with a size of 128 in the forward direction and 127 in the reverse direction.

All predicates on 4 bits
 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). 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 facts have been verified:
 Every predicate on four bits can be implemented with at most 3 AND gates and at most 7 XOR gates; (for functions that have the constant 1 in their algebraic normal form, the last gate would have to be negated; there are only two functions  modulo permutation of inputs  which appear to require 7 XOR gates)
 Every predicate on four bits, but of degree 3, can be implemented with 2 AND gates.
 Predicates on four bits (4.85MB).This file contains straightline programs (SLPs) for all predicates f(x1,x2,x3,x4) with f(0,0,0,0) = 0. The SLPs are indexed by fn, where n is the decimal number corresponding to the truth table of the function. For example the function x1*x2*x3*x4 has truth table 0000 0000 0000 0001 = 1. So you can find it under "f1". The circuits were independently verified by Chris Wood (many thanks!).
 If you denote by C_n[A,X] the set of functions with multiplicative complexity A for which an ANDoptimal circuit requires exactly X XOR gates, then C_n[A,X] is closed under permutation of inputs (but not under arbitrary affine transformations). This property allows for detection of suboptimal circuits. I have not coded this yet, so many of the circuits below are likely to be suboptimal.
 There are the two functions (up to permutation of inputs) that use 7 XOR gates and 3 AND gates. These functions do not appear to be special in any way. Magnus Find used a SAT solver to look into this. The SAT solver "proved" that neither function has a circuit with 6 XOR gates. Given other functions, the SAT does find circuits with 6 XOR gates. So it would appear that these two functions are special in some way.

All predicates on 5 bits
 Meltem Turan, Cagdas Calik, and Rene Peralta have shown that all predicates on 5 bits have multiplicative complexity at most 4. This is somewhat surprising given that multiplicative complexity grows exponentially with the number of input bits.

All predicates on 6 bits
 Cagdas Calik, Meltem Sonmez Turan and Rene Peralta studied the multiplicative complexity of all predicates on 6 bits by analyzing circuits with a particular number of AND gates and utilizing the affine equivalence of functions. The work showed that any predicate on 6 bits can be implemented using at most 6 AND gates. The SLP’s for the representatives of 150,357 affine equivalence classes on 6bit predicates are provided at https://github.com/usnistgov/Circuits/tree/master/slp. The details are provided at https://eprint.iacr.org/2018/002.pdf.
Created December 29, 2016, Updated March 29, 2018