Projects 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(26) using irreducible polynomial x6 + x3 + 1
Multiplication in GF(27)
- Using irreducible polynomial x7 + x4 + 1
- Using irreducible polynomial x7 + x3 + 1
Multiplication in GF(28) using the AES polynomial x8 + x4 + x3 + x + 1
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) ≤ 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.
- 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 S-box of AES
- Circuit for the S-box of AES. The circuit is described as a straight-line 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 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.
- Circuit for the reverse direction of the S-Box, with size 121 and depth 21. We have not 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.
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 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.
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 6-bit 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