Boolean Circuits vs Arithmetic Circuits

Question

I am just wondering what's the differences between boolean circuits and arithmetic circuits? I know the basic notions of circuits. My question is their applications in cryptography. For example, why we should consider them separately (e.g., why we should consider functional encryption for boolean circuits and functional encryption for arithmetic circuits separately)?

I cannot find any literature that explain this clearly currently. If you have read such literature, please tell me.

Answer 1

Boolean circuits and arithmetic circuits are two different ways of representing a computation. The main difference is with respect to their input types and their gate types: boolean circuits work on bit inputs, and the gates of the circuit correspond to boolean operations (such as XOR, AND). On the other hand, arithmetic circuits work on inputs that are elements of some field $\mathbb{F}$, and the gates of the circuit correspond to arithmetic operations, id est, field operations (such as additions and multiplications).

The class of functions that can be computed by Boolean circuits of polynomial size coincide with the class of functions computable by arithmetic circuits of polynomial size. Indeed, one can always use some representation of the field elements and translate the field operations to boolean operations (with a blow-up polynomial in the length of field elements). Conversely, one can always translate a boolean circuit to an arithmetic one, by interpreting $0$ as the neutral for addition over $\mathbb{F}$, $1$ as the neutral for multiplication over $\mathbb{F}$, and translating the boolean gates to arithmetic operations (e.g. $a\phantom{i}\mathsf{OR}\phantom{i}b$ becomes $a + b - a*b$).

Deciding whether a boolean circuit is better than an arithmetic circuit in a particular application depends on the type of computation you want to perform. In cryptography, it is quite common to rely on computation on-field elements, and we have cryptographic tools that allow us to manipulate field elements in an atomic way, id est, treating a given field element as a single input (and not as a string of bits). In this case, it makes sense to represent the computation with an arithmetic circuit. However, many applications of, say, secure computation involve non-arithmetic operations (for example, integer comparison, which is a basic procedure in many computations). In this case, implementing this non-arithmetic operation as an arithmetic one would be very inefficient, and boolean circuits are more natural representations.

Another way of seeing it is the following: arithmetic circuits are a generalization of boolean circuits to arbitrary fields; boolean circuits correspond to arithmetic circuits over the field $\mathbb{F}_2$. There have been many papers that worked on extending cryptographic methods that work well for computations represented as boolean circuit to the setting of computations which are best captured by arithmetic circuits, to get efficiency improvements for those circuits (e.g. Yao's garbled circuit method has been extended to garbled arithmetic circuits), or on bridging between methods adapted to boolean circuits and methods adapted to arithmetic circuits, to capture computation whose best representation is a mix between the two.

Answering a question in comments

I am looking for a reference that establishes the result that "the class of functions that can be computed by Boolean circuits of polynomial size coincide with the class of functions computable by arithmetic circuits of polynomial size". Can you provide a reference to a book or a scientific paper? My search was without success...

As I mentioned in the comment, you will likely not find a reference because the result is folklore. Fix an arbitrary field $(\mathbb{F}, +, \cdot)$ and consider a function $f$ which can be computed by a boolean circuit of size polynomial in its input size, say, over the standard basis $\{\mathsf{XOR}, \mathsf{AND}, \mathsf{NOT}\}$. To emulate the computation over $\mathbb{F}$, encode the bit $0$ as $0_\mathbb{F}$ (the neutral for addition in $\mathbb{F}$) and the bit $1$ as $1_\mathbb{F}$ (the neutral for multiplication). The boolean gates can be emulated as follows:

• To compute an $\mathsf{AND}$ gate on input $(x,y)$, return $x \cdot y$
• To compute an $\mathsf{XOR}$ gate on input $(x,y)$, return $x + y - 2\cdot x\cdot y$
• To compute a $\mathsf{NOT}$ gate on input $x$, return $1_\mathbb{F}-x$.

I'll let you check that this correctly emulates the boolean operations. Since emulating each boolean gate requires at most 4 arithmetic operations, the arithmetic circuit emulating the boolean circuit over $\mathbb{F}$ is of polynomial size as long as the boolean circuit is polynomial size. The converse direction is trivial since a boolean circuit is just an arithmetic circuit over $\mathbb{F}_2$.

For the sake of generality, I'll add that you can generally emulate field operations over an arbitrary field $\mathbb{F}$ using boolean circuit; indeed, this is what your computer is doing every day: fix a field $\mathbb{F}$, and consider the binary decomposition of any element $x$ of $\mathbb{F}$: $x = \sum_{i=0}^{\lceil \log |\mathbb{F}| \rceil-1} b_i \cdot 2^i$, with $b_i \in \{0_\mathbb{F}, 1_\mathbb{F}\}$.

• To emulate addition over $\mathbb{F}$, use the schoolbook binary addition method, which only requires using $\mathsf{XOR}$ and $\mathsf{AND}$ gates, by observing that $\mathsf{XOR}$ gives you the $i$-th value, while $\mathsf{AND}$ gives you the $i$-th carry.
• To emulate a multiplication over $\mathbb{F}$, use the textbook multiplication algorithm, which relies only on $\mathsf{AND}$ gates plus field additions, which we already showed can be emulated.

Overall, the size increase is dominated by the $O(\log^2 |\mathbb{F}|)$ cost for the schoolbook binary multiplication.