 An official website of the United States government Official websites use .gov
A .gov website belongs to an official government organization in the United States. Secure .gov websites use HTTPS
A lock ( ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

# Circuit Complexity

### Overview

The circuit complexity project, part of the Cryptographic Technology Group, operates within the Computer Security Division, in the Information Technology Laboratory at NIST. The project is focused on researching circuit complexity, and developing reference material about circuits.

 Circuit complexity is a topic of great relevance to cryptography. Optimization of circuits leads to efficiency improvement in a wide range of algorithms and protocols, such as for symmetric-key and public-key cryptography, zero-knowledge proofs and secure multi-party computation. The circuit complexity project has two main goals: improve the understanding of the circuit complexity of Boolean functions and vectorial Boolean functions; develop new techniques for constructing better circuits for use by academia and industry. Circuit for inversion in GF(24)

#### 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}n → {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(24), each with 9 ANDs, and one inversion in GF(24) using 5 ANDs. For simplicity, consider the problem of inversion in GF(24). 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 pt 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

 We consider the problem of obtaining efficient recursions for multiplication of binary polynomials. Let M(n) denote the number of gates, in the basis {XOR, AND}, needed to compute all the binary coefficients of the product of two binary polynomials of degree n – 1, which yields a new polynomial of degree 2n – 2. A Karatsuba-type recursion formula for a "d-way split" is of the form M(d*n) ≤ a*M(n) + b*n – c, where a, b, c and d are fixed integers, and n is a variable positive integer. Karatsuba circuit

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*nc XOR gates. For each d, it is a challenge to find techniques supporting a minimal a, and then a minimal b. We list some examples in our circuit library.

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:

#### 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. Hamming-weight method Circuit for the exactly-counting function E84 Legend: ∧ (AND); ⊕ (XOR); bar over ⊕ (XNOR); FA (full adder)

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:

#### 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

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 ai and bi be in some ring. The multiplication of polynomials yields a new polynomial of degree 14 (before carry correction), with coefficients ci. A straightforward computation of the set of coefficients ci uses the 64 possible quadratic terms aj*bk, whereas a solution exists with only 26 multiplications of coefficients (besides some sums).

Current team members: René Peralta, Meltem Sönmez Turan, Luís Brandão

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

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

#### Contacts

Reach the Circuit Complexity team at:
circuit_complexity@nist.gov

René Peralta - NIST

Meltem Sönmez Turan - NIST

Luís T. A. N. Brandão - NIST/Strativia

#### Group

Cryptographic Technology

#### Topics

Security and Privacy: cryptography

Technologies: circuits, complexity

#### Related Projects

Created December 29, 2016, Updated September 05, 2023