Boolean functions for a wide class of applications (such as encryption, digital signatures, hashing, and error correction codes) can be implemented as electronic circuits. In practice, it is important to be able to minimize the size and depth of these circuits. The Circuit Complexity Project aims at finding combinational circuits—over the basis AND, XOR, NOT—for boolean functions.
The problem, even for functions on very few inputs, is computationally intractable. This means that optimal solutions can not be found or even recognized. Because of this, new circuit designs are measured against the state of the art. This project has two main goals: improve our understanding of the circuit complexity of boolean functions in general, and produce better circuits for use by industry.
Our work has led to a significant reduction in the number of gates and/or the depth of many circuits used in cryptography. These include a circuit of depth 16 and size 125 for the AES S-Box, as well as reduced size/depth circuits for binary and finite-field multiplication. Additionally, circuits with a small number of multiplications can be used to significantly improve the communication complexity of secure multiparty computations, as well as the size of non-interactive zero-knowledge proofs of knowledge.
Any boolean function can be described as a circuit with operations modulo 2. If the circuit only contains additions, then the function is linear. Nonlinearity, which is fundamental to cryptographic applications, can only be achieved by the use of multiplications (i.e. AND gates). The field's standard measure of nonlinearity of a function F is the Hamming distance of the spectrum of F to the closest linear spectrum.
A different measure of nonlinearity is the number of multiplications necessary and sufficient to compute the function. This measure is called "multiplicative complexity". Minimizing the number of multiplications as a first step in Boolean circuit optimization is a powerful tool. A second step is to minimize the size and depth of the linear parts of a circuit. We have shown both of these subproblems to be computationally hard (inapproximable unless P = NP). But we have also designed heuristics for each of these steps that yield significant improvements to the state of the art.