Importance of round complexity in determining the efficiency of an MPC protocol

Question

Literature has different ways of specifying complexity of an MPC protocol:

• computation complexity that measures the number of (assumed primitive) operations performed by all the parties;
• communication complexity, which measures the number of bits communicated between parties during the protocol;
• round complexity that measures the number of sequential steps in the algorithm (discounting on operations that can be done in parallel).

I feel that all the above parameters are important, to be discussed, when analyzing the efficiency of any proposed MPC protocol. However, I observed that round complexity is discussed in only few of the works. Hence I wanted to know, how important a role does the round complexity play in determining the efficiency of any proposed protocol. That is, when is considering round complexity of a protocol important?

It would be helpful if you could point me to literature that discusses the nature of functions that can be achieved, using MPC, in constant round and those that cannot.

Answer 1

First note that all polynomial-time functions can be securely computed with a constant number of rounds (Yao and BMR families) and all can be securely computed with protocols that have rounds dependent on the depth of the circuit computing the function (GMW families). The question is when is one type better than another.

The answer to this question is not straightforward, and depends on many parameters. Clearly, if you are on a slow network (Internet with 30ms round-trip time), then any protocol that has many rounds will be very very slow. However, if you are on a fast network, then many rounds has less of an influence (except in very extreme circumstances of incredibly deep circuits). It turns out that the constant-round protocols that we know of have much higher bandwidth than those that have complexity that depends on the depth of the circuit. Thus, in a very fast network, many-round protocols often out-perform constant round ones. As I mentioned, this is NOT the case in a slow network.

There isn't too much published that directly relates to this question. However, for semi-honest adversaries there is one paper that comes to mind by Schneider and Zohner, titled: GMW vs. Yao? Efficient secure two-party computation with low depth circuits that appeared at Financial Crypto 2013. This is a good place to start reading.

Answer 2

Just to complement prof. Lindell's answer, although one cannot have a formal description of the case in which round complexity will matter more than communication or computation, a colleague of mine did some estimations two years ago, for a paper we were writing on round-efficient primitives for zero-knowledge. It's just a particular case, but having figures in mind might help getting an intuition on how much round complexity might matter.

I'm just pasting the paragraph here:

"If we consider a protocol between a client in Europe, and a cloud provider in the US, for example, we expect a latency of at least 100ms (and even worse if the client is connected with 3g or via satellite, which may induce a latency of up to 1s [Bro13]). Concretely, using Curve25519 elliptic curve of Bernstein [Ber06] (for 128 bits of security, and 256-bit group elements) with a 10Mbps Internet link and 100ms latency, 100ms corresponds to sending 1 flow, or 40,000 group elements, or computing 1,000 exponentiations at 2GHz on one core of current AMD64 microprocessor. As a final remark on latency, while speed of networks keeps increasing as technology improves, latency between two (far away) places on earth is strongly limited by the speed of light: there is no hope to get a latency less than 28ms between London and San Francisco, for example."

Keep in mind that this example is a bit contrived, but it gives you an interesting equivalence: if the players are far apart, one flow is as costly as sending thousands of elliptic curve group elements, or computing hundreds of exponentiations. This was just to make slightly more precise the "very very slow" statement of the previous answer.

(Source)