|
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:
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. |
Circuit for inversion in GF(24) |
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).
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.
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.
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.
For each complexity measure for circuits, we can define a metric for functions. For example:
Each application can have its own target metric(s). For example:
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?
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?
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?
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.
|
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*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.
The multiplicative complexity of Boolean functions (n-input variables; a single output variable) is of interest.
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?
It is difficult to find good lower-bounds for explicit functions:
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).
Previous team members: Andrea Visconti (2011–2012), Magnus Find (2016–2017), Nathan Dykas (2018)
External collaborators: Joan Boyar, Murat Cenk
