Circuit Minimization Work

We plan to post in this page results obtained by the "circuit minimization team" (CMT). This is an informal group of friends and colleagues that are working on the problem of finding "good" circuits over GF2 (alternatively, circuits using only XOR and AND gates). The definition of "good" varies: small, low-depth, few AND gates, and so on.

  1. Multiplication in GF(2^6) using irreducible polynomial x^6 + x^3 + 1 . Here is the straight-line program for a circuit with 57 gates and depth 5.
    Here
    is a pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates.
    The Ai's and Bi's are the coefficients of polynomials A, B. The Ci's are the coefficients of C = A*B.
    The best circuit we can find in the literature for this problem, here, has depth 5, size 61.  

  2. Multiplication in GF(2^7). 
    1. Using irreducible polynomial x^7 + x^4 + 1 .
      The best published circuit we can find for this has depth 7 and 100 gates.
      Here
      is the straight-line program for a circuit with 84 gates and depth 5.
      Here
      is a pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 
    2. Using irreducible polynomial x^7 + x^3 + 1 .
      The best published circuit we can find for this has depth 7 and 100 gates.
      Here
      is the straight-line program for a circuit with 85 gates and depth 5.
      Here
      is a pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 

  3. Multiplication in GF(2^8) using the AES polynomial x^8 + x^4 + x^3 + x + 1 . The best published circuit we can find for this has 135 gates and depth 7 ( link ).
    Here
    is the straight-line program for a circuit with 117 gates and depth 6.
    The Ai's and Bi's are the coefficients of polynomials A, B. The Ci's are the coefficients of C = A*B.

  4. Binary Multiplication.
    This is an old and much-studied problem. It can also be viewed as that of multiplication of polynomials of degree n over GF(2).
    Dan Bernstein's results at High-speed 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 n-1 .
    It is not hard to show that M(n) \leq M(n-1) + 4(n-1).
    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. 
    1. M(11) \leq 186.
      Here
      is the straight-line program for a circuit with 186 gates and depth 7. 
      Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates.  
    2. M(12) \leq 207 (and therefore M(13) \leq 255).
      Here
      is the straight-line program for a circuit with 207 gates and depth 7. 
      Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates.  
    3. M(15) \leq 312.
      This illustrates why I think we don't really know the values of M(n).
      Bernstein's 2009 circuit has 329 gates. Cenk and Hasan improved this to 317 gates in 2015.
      Here
      is an optimization of the latter circuit with 312 gates and depth 9 (send me email for lower-depth circuits).  
    4. M(16) \leq 349 (and therefore M(17) \leq 413).
      Here
      is the straight-line program for a circuit with 349 gates and depth 8. 
      Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 
    5. M(18) \leq 454.
      Here
      is the straight-line program for a circuit with 454 gates and depth 8. 
      Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 
    6. M(19) \leq 498.
      Here
      is the straight-line program for a circuit with 498 gates and depth 8. 
      Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 
    7. M(20) \leq 527.
      Here
      is the straight-line program for a circuit with 527 gates and depth 8. 
      Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 

  5. The S-Box of AES. Here is a circuit for the S-Box of AES. The circuit is described as a straight-line program using ANDs, XORs, XNORs.
    Here is the pdf rendering of the circuit. The red nodes are AND gates, the yellow nodes are XOR gates and the gray nodes are XNOR gates. 
    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 non-linear 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 SAT-solver 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 sub-optimal 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. The circuit is Here .


    Here is a circuit for the reverse direction of the S-Box. The circuit has size 121 and depth 21. We haven't worked much on this. The size can probably be reduced.

    The S-Box can be reduced to depth 16 with a size of 128 in the forward direction and 127 in the reverse direction.
    Here is a circuit for the forward directions of the S-Box. The circuit is described as a straight-line program using ANDs, XORs, XNORs.
    Here
    is the pdf rendering of the forward direction of the S-box. he red nodes are AND gates, the yellow nodes are XOR gates and the gray nodes are XNOR gates. 
    Here is a circuit for the reverse direction of the S-Box. The circuit is described as a straight-line program using ANDs, XORs, XNORs.
    Here
    is the pdf rendering of the reverse direction of the S-box. he red nodes are AND gates, the yellow nodes are XOR gates and the gray nodes are XNOR gates. 

  6. 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:
    1) 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)
    2) Every predicate on four bits, but of degree 3, can be implemented with 2 AND gates.


    The following (large) file contains straight-line 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 AND-optimal 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 sub-optimal 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.

    Predicates on four bits.


  7. All predicates on 5 bits. Meltem Turan, Cagdas Calik, and I have shown that all predicates on 5 bits have multiplicative complexity at most 4. I lost a bet about this with Cagdas (I thought it would be 5 or more). Multiplicative complexity grows exponentially with the number of input bits, so one of these days I will win a bet.

Currently, CMT is Magnus Find, Ramon Collazo, Larry Bassham, Bruce Strackbein, Joan Boyar, Morris Dworkin, Michael Fischer, Rene Peralta, Meltem Turan, Past collaborators include: Michael Bartock, Cagdas Calik, Christopher Wood, Andrea Visconti, Chiara Schiavo, Holman Gao .