7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to narrow down what you are really asking: do you understand what a "circuit" is? Are you aware that It is a basic concept of computer science and not specific to cryptography? $\endgroup$ – Guut Boy Apr 20 '17 at 19:51
  • $\begingroup$ I attempted to answer your question, but it is quite broad. Either you got the tags wrong, as circuits are a notion way more general than garbled circuits or multiparty computation, or you have a more specific question in mind on MPC and GC, in which case you should edit your question to make your question more precise. $\endgroup$ – Geoffroy Couteau Apr 20 '17 at 19:56
17
$\begingroup$

Boolean circuits and arithmetic circuits are two different ways of representing a computation. The main difference is with respect to their inputs types and their gates 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 fonctions 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 of 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 a 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.