Regarding the feasibility of MPC protocols

I know that there is a general result stating that any function can be computed in an MPC protocol. In this question, I'm interested in understanding the practicality of MPC protocols.

1. Are any theoretical results regarding the feasibility of MPC protocols? To be more specific, are there any functions that are infeasible to compute in an MPC?
2. Even more specific, are there any 2-party computations that are impractical to run (assuming that both parties are honest), yet are practical to run by a single party that held both inputs?

2 Answers

1. Are any theoretical results regarding the feasibility of MPC protocols? To be more specific, are there any functions that are infeasible to compute in an MPC?

Yes, there are hundreds of paper on MPC feasibility. The answer always depends on the adversarial model. Here are a few of the more well-known/standard results:

• $$n$$ parties can compute any function of their inputs, in the presence of a passive (semi-honest), computationally unbounded adversary that corrupts strictly less than $$n/2$$ parties.

• There are functions that can't be computed in the presence of a passive adversary that corrupts $$\lceil n/2 \rceil$$ parties.

• $$n$$ parties can compute any function of their inputs, in the presence of an active (malicious), computationally unbounded adversary that corrupts strictly less than $$n/3$$ parties.

• There are functions that can't be computed in the presence of a malicious adversary that corrupts $$\lceil n/3 \rceil$$ parties.

• $$n$$ parties can compute any function in the presence of a passive computationally-bounded adversary that corrupts any number of parties.

• Most functions can't be computed against an active adversary in a way that provides universal composability, if there is no setup (like a common reference string).

I have taken all of these examples from a survey chapter that I co-wrote on the topic. You can find the original references there.

1. Even more specific, are there any 2-party computations that are impractical to run (assuming that both parties are honest), yet are practical to run by a single party that held both inputs?

This is a harder question to answer because it is more about concrete efficiency than feasibility. There are theoretical results about how you can compute everything securely with "constant overhead" relative to the plaintext computation, but none of these results are what you would consider practical.

Using a more colloquial interpretation of what's "practical", pretty much everything falls into your category of "impractical" under secure computation. As @SEJPM points out in the other answer, unless you know that your problem has a lot of structure, the only known way to do 2-party secure computation would be to translate it to a boolean/arithmetic circuit and securely evaluate that circuit. This is many orders of magnitude slower than just computing something on raw data.

I know very few examples where the secure computation is reasonably close in efficiency to the plaintext computation. One such example is private set intersection, which is only ~ 6-8x slower than insecurely computing the intersection.

• Thanks for the great response Mike. A quick question: Do you know any pointers, or have a quick comment about MPC in different models like plain/CRS/PKI? I have found this recently in the literature but I have no intuition about what these models imply and what is feasible or not in each of them. I just asked a question about this: crypto.stackexchange.com/q/81233/13843 – Daniel Jun 8 at 13:52
• Thanks for the detailed answer @Mikero! Another (somewhat related) question: is there a specific computation that can be, regardless of the setting, considered as an MPC resistant, i.e., impractical to perform in an MPC, yet practical if performed insecurely? (This question is theoretical - independent of any particular MPC protocol) – Avilan Jun 11 at 14:01
• As I said above, in a theoretical sense anything you can compute insecurely in n operations, you can compute in O(n) operations securely (depending on the attack model). These protocols aren't actually practical in the real world, but they settle the question theoretically. – Mikero Jun 11 at 18:11

To be more specific, are there any functions that are infeasible to compute in an MPC?

Anything you can express as a non-cyclic circuit of AND and XOR gates or as a non-cyclic circuit of (finite field) ADD and MULTIPLY gates can be computed via MPC using standard techniques.

This imposes some natural restrictions on what is "annoying": If you do conditional operations, you have to evaluate both branches, you can't do unbounded recursion and your loops also must have a bounded, input-independent number of iterations. Of course if you want to compute a function that is sufficiently annoying it might as well be infeasible, e.g. if you can only guarantee the loop count being smaller than $$2^{128}$$ it is practically infeasible to compute that in an MPC setting.

Even more specific, are there any 2-party computations that are impractical to run (assuming that both parties are honest), yet are practical to run by a single party that held both inputs?

Standard two-party MPC scales in effort linear to the amount of AND gates. One number I was able to find (PDF) there was that it took 0.83 seconds to compute 800k AND gates using all available optimizations with an MPC protocol suited to that task. Even assuming a rather slow CPU at 1GHz it would be able to evaluate this many gates (especially with the AND-depth of 38 they used) at 1 AND per cycle, so even this super-optimized protocol is still at least 1000x slower than direct hardware evaluation. Now find some workload that takes say a couple of minutes on your computer and uses operations which expand easily into multiple ANDs and you're looking at a task that generic multi-party computation can't do in a reasonable amount of time.

• Sorry, for the link to the paywalled paper. – SEJPM Jun 4 at 13:00