# Limitations of boolean and arithmetic circuits

Much of modern cryptography is based around working with boolean or arithmetic circuits. For example in Multi-Party Computation the 'famous' results allow for the secure computation of any function that can be represented as a boolean or arithmetic circuit.

I am wondering what the limits of these circuits are, what are some examples of functions are we not able to compute securely --- that is what functions are not representable as a boolean or arithmetic circuit? And in the real world does this reduce the effectiveness of modern cryptography or are these circuits enough to implement everything we require?

• There is no limit. It can be really slow, but there is no limit. Aug 15, 2019 at 19:23
• @kelalaka: there are limits (you can only compute functions that can be computed in a bounded period of time), for just about everything we're interested in falls in that category, and so there is effectively no limit... Aug 17, 2019 at 11:15
• @poncho yes, in terms of compatibility, there are limits. Aug 17, 2019 at 13:10

## 1 Answer

The question should be which functions can we build a small circuit to solve. Any function mapping a fixed number of bits to a fixed output can be represented as a boolean circuit. But it may be very large. This brings is to a difficult topic with few lower bounds: https://en.m.wikipedia.org/wiki/Circuit_complexity