Boolean circuits

Definition

A Boolean circuit is a directed acyclic graph (DAG) with input nodes, logic gates, and output nodes.

A Boolean circuit with n inputs and m outputs computes a function f : {0,1}ⁿ → {0,1}^m. The function f is called a Boolean function when m=1, and a vectorial Boolean function when m>1.

The gates are connected by wires, which carry bits, and the gates are Boolean operators that implement very simple functions, such as 1-to-1 and 2-to-1. We denote the number of inputs and outputs by “fan-in” and “fan-out”.

For fan-in 1, we are just interested in the NOT function (sometimes also called inverter). For fan-in 2, we are interested in various linear gates (such as XOR and XNOR) and non-linear gates (such as AND, OR, NAND).

Applicability

Boolean circuits play an important role in a wide class of cryptographic and coding applications, such as encryption, hashing, and error correction codes.

Boolean functions can be implemented as electronic circuits, and can also be a basis for more generic circuits, where multiplications and sums can appear in various forms (for example in a larger field). In practice, it is important to be able to minimize the size and depth of these circuits.

Sometimes it is relevant to consider generalizations of Boolean circuits. For example, in arithmetic circuits the values in a wire can be elements of a larger field (instead of just 0 and 1), and the gates, such as XOR and AND, become sum (+) and multiplication (x) in the larger field. Depending on the function, arithmetic circuits may be more efficient than Boolean circuits.

Boolean functions can also be implemented as electronic circuits.

Measures of complexity

The circuit complexity challenge: Given a set of Boolean gates and a set of Boolean functions, construct a circuit that computes the functions and is optimal according to some complexity measure.

Even for functions on very few inputs, it is computationally intractable to find combinational circuits that are optimal for some metrics of interest, or even recognizing whether a solution is optimal. Because of this, new circuit designs are measured against the state of the art.

Examples of complexity measures on circuits:

• Gate size (or simply size): number of gates in the circuit. Also measurable for a particular type of gate:
  • Multiplicative: number of non-linear gates used in the circuit.
  • Additive: number of linear gates used in the circuit.
• Gate depth (or simply depth): length of the longest path from an input gate to an output gate. Also measurable for a particular type of gate:
  • Multiplicative: maximum number of non-linear gates on a path from an input to an output in the circuit.
  • Additive: maximum number of linear gates (excluding 1-to-1 gates) on a path from an input to an output in the circuit.

We often consider complexity in a setting that uses the basis {AND, NOT, XOR}. In those circumstances we sometimes talk more specifically about AND-complexity or XOR-complexity.

Complexity measures on functions:

For each complexity measure for circuits, we can define a metric for functions. For example:

• Multiplicative complexity (MC) of a function f: Number of non-linear gates necessary and sufficient to implement f with a circuit.

Target metrics

Each application can have its own target metric(s). For example:

• Circuits with small size enable hardware implementations that use less energy and occupy smaller area, and are desired for lightweight cryptography applications running on constrained devices.
• Minimizing the number of non-linear gates is useful for secure multi-party computation, zero-knowledge proofs, side channel protection with low-cost requirements, and even certain post-quantum cryptographic signature schemes.
• Circuits with small AND-depth are desired for homomorphic encryption schemes.
• Gate depth affects latency.

Below, we list four problems on which the Circuit Complexity team has been working on. Most of our work is on circuits built using the basis {AND, XOR, NOT}. One problem relates to additive complexity; two problems relate to multiplicative complexity; one problem, related to recurrence relations for binary polynomial multiplication, considers size, depth, and multiplicative complexity. To which extent can better solutions be found by using new optimization techniques?

1. AND-optimization of Boolean functions

Consider the basis {AND, XOR, NOT}. We would like to be able to optimize circuits that implement Boolean functions. However, with currently known techniques, it is intractable to find AND-optimal circuits (i.e., with the number of AND gates being equal to the multiplicative complexity of the function) for most Boolean function with more than 6 input variables.

Generic (informal) question: What computation techniques and heuristics can find good solutions, without having to do an exhaustive search over a large space?

2. AND-optimization of vectorial Boolean functions

We have constructed a circuit for the S-Box of the Advanced Encryption Standard (AES) that uses a total of 113 gates, of which 32 are ANDs and 81 are XOR/XNOR gates.

Open problem: Can the AES-SBox be implemented with fewer than 32 non-linear gates?

The circuit with 32 AND gates uses three multiplications in GF(2⁴), each with 9 ANDs, and one inversion in GF(2⁴) using 5 ANDs. For simplicity, consider the problem of inversion in GF(2⁴). We know how to compute this optimally with 5 non-linear gates. The picture on top of the page shows an example with 7 non-linear gates. Are there good algorithmic approaches to get rid of two non-linear gates? Put differently, without algebraic insights, how to evolve the given circuit to a better solution, with only 6 or 5 non-linear gates?

3. XOR-optimization of linear maps

Problem: Find the XOR-complexity of computing the product y = M . x, over the binary field GF(2), where M is an n (rows) by m (columns) binary matrix and x is a column vector of m input variables (bits), and when assuming no other gate types are allowed?

For an n by m binary matrix M having p ones, the product M . x can be trivially computed using p – t XOR gates, where t is the number of rows with at least one 1. We are interested in methods that enable finding circuits with a smaller (the smallest possible) number of gates.

4. Recurrence relations for binary polynomial multiplication

This means that it is possible to multiply two binary polynomials of degree d*n – 1 using no more than a multiplications of two polynomials of degree n – 1, plus b*n – c XOR gates. For each d, it is a challenge to find techniques supporting a minimal a, and then a minimal b.

We are often aiming at finding combinational circuits—over the basis AND, XOR, NOT— for Boolean functions. Our work has led to a significant reduction in the number of gates and/or the depth of several circuits.

1. MC of Boolean functions

The multiplicative complexity of Boolean functions (n-input variables; a single output variable) is of interest.

• We found the MC of all Boolean functions with n ≤ 6. (ia.cr/2015/848, ia.cr/2018/2, GitHub:usnistgov/Circuits).
• We found closed-form formulas for the number of Boolean functions having MC ≤ 4 (ia.cr/2015/1041, ia.cr/2019/1364)

2. MC of vectorial Boolean functions

• For the AES S-Box, our work has found:
  • a circuit with 32 AND gates (ia.cr/2009/191) -- this is the minimum number of AND gates found so far --- and size 115
  • a circuit with depth 16 (ia.cr/2011/332) and size 128.
• We found the exact MC of the hamming weight function (doi:10.1016/j.tcs.2008.01.030).

3. MC of symmetric Boolean Functions

We have studied the multiplicative complexity of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. We introduced new techniques (ia.cr/2019/708) that yield circuits with fewer AND gates than had been upper bounded in 2000 & 2008. As an example, we generated circuits for all such functions with up to 25 variables.

Open problem: What is the maximum MC of symmetric functions with 22 variables?

4. Some complexity bounds

It is difficult to find good lower-bounds for explicit functions:

• A lower bound better than 3n is known for the size (number of gates) of an explicit function (doi:10.1109/FOCS.2016.19)
• XOR complexity is MAX SNP-complete (doi:10.1007/s00145-012-9124-7)

5. Reed Solomon Codes

The Reed-Solomon code RS(255,223) is widely used in communications and in data storage and retrieval. A standard implementation uses 768 gates (32 linear circuits with about 24 gates each). Our linear circuit optimization techniques yielded a circuit with only 412 gates.

Reed-Solomon code

6. Vectorial quadratic functions

One of the results of our group is the following (Karatsuba-type) recursion formula: M(8n) ≤ 26M(n) + 147n – 40 (doi:10.1109/TC.2018.2874662). This means that to multiply two binary polynomials of degree 8n – 1 we are able to use only 26 multiplications of two polynomials of degree n – 1, plus 147 n – 40 XOR gates. (For concrete values of n we can get better results; e.g., for n=1 we can multiply two polynomials of degree 7 using only 100 gates, although the formula gives 133 gates.)

Using a search in a large space, we could find many solutions with leading term 26, from which we then picked the one with lowest second term (doi:10.1007/978-3-030-34029-2_22). However, it is not computationally feasible to search the full space of possibilities and we do not know whether there is a solution with leading term 25.

Open problem: For the division in 8 blocks, is there a recursion relation using fewer than 26 binary polynomial multiplications? For some perspective, consider the case of multiplying two binary polynomials (p and q), of degree n – 1 = 7. Let the coefficients a_i and b_i be in some ring. The multiplication of polynomials yields a new polynomial of degree 14 (before carry correction), with coefficients c_i. A straightforward computation of the set of coefficients c_i uses the 64 possible quadratic terms a_j*b_k, whereas a solution exists with only 26 multiplications of coefficients (besides some sums).

Previous team members: Andrea Visconti (2011–2012), Magnus Find (2016–2017), Nathan Dykas (2018), Çağdaş Çalık (2016–2021)

External collaborators: Joan Boyar, Murat Cenk, Tolga Yalçın