1
$\begingroup$

Communication complexity is generally discussed among many papers on secure multi-party computation (MPC). However, I do not still understand the importance of it.

What communication complexity affects is total computation time in a protocol depending on available bandwidth rate (10Mbps, 1Gbps, etc).

Is the communication complexity really important? When is it captured as primary result of some paper?

With a specific programming implementation detail, I can understand the total execution time including data transmission during the protocol. But from the communication complexity (even if some paper reduced it significantly compared with prior works), I wonder when and why it makes sense.

What is the advantage of reducing communication cost (in general at the expense of computation time on some nodes) in practice?

$\endgroup$

1 Answer 1

1
$\begingroup$

It's safe to say that any Cryptographer would want his/her protocol to be implemented and used by the public. Ideas in MPC have been floating around for quite some time now and have been proven to be theoretically sound. The challenge now is to make them efficient enough that it is feasible to use them in practice. In the domain of MPC, sizes of the messages blow up very easily in most protocols as you may have already noticed.

Given that in most situations the network speed is a bottle neck compared to local execution times, it becomes very important to reduce communication complexity if one is serious about implementing the protocol.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.