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?

  • $\begingroup$ There is no limit. It can be really slow, but there is no limit. $\endgroup$
    – kelalaka
    Aug 15 '19 at 19:23
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Aug 17 '19 at 11:15
  • $\begingroup$ @poncho yes, in terms of compatibility, there are limits. $\endgroup$
    – kelalaka
    Aug 17 '19 at 13:10

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


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.