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).
   See Dan Bernstein's High-speed cryptography in characteristic 2 for a summary of known results. Improvements on Dan's results 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 2010.
   Our software needs to be rewritten in order to synthesize circuits for polynomials of degree larger than 20 or so. 
1. 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. 
2. M(15) \leq 326.
   Here is the straight-line program for a circuit with 326 gates and depth 8. 
   Here is the pdf rendering of the circuit. The red nodes are AND gates. The yellow nodes are XOR gates. 
   Here is the straight-line program for a circuit with 328 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(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. 
4. 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. 
5. 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. 
6. 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 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. 

Currently, CMT is Michael Bartock, Joan Boyar, Morris Dworkin, Michael Fischer, Rene Peralta, Bruce Strackbein, Catie Baker, Andrea Visconti, Chiara Schiavo, Johnny Svensson. Past collaborators include: Holman Gao, Scott Zimmermann, Matteo Bocchi.