Regarding the feasibility of MPC protocols

Question

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?

Answer 1

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.

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?

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.

Answer 2

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.