U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

This is an archive
(replace .gov by .rip)

Circuit Complexity

Overview

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 our 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. 

Our team, part of the Cryptographic Technology Group, operates within the Computer Security Division, in the Information Technology Laboratory at NIST. Contact us if you would like to visit our group and/or collaborate in research.

Figure circuit for inv-GF24

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.

Figure: Karatsuba circuit

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

2. MC of vectorial Boolean functions

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.

HW-method

Hamming-weight method

Figure: circuit for exactly-counting E84

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.

Circuit for Reed Solomon

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.

Seach quadratic forms

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).

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

Additional Pages

List of circuits References

Contacts

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

René Peralta

Luís T. A. N. Brandão

Morris Dworkin

Meltem Sönmez Turan

Topics

Security and Privacy: cryptography

Technologies: circuits, complexity

Created December 29, 2016, Updated November 08, 2021