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.