On the practical importance of communication complexity for secure multi-party computation protocols
Florian Kerschbaum, Daniel Dahlmeier, Axel Schröpfer, Debmalya Biswas · 2009
Many advancements in the area of Secure Multi-Party Computation (SMC) protocols use improvements in communication complexity as a justification. We conducted an experimental study of a specific protocol for a real-world sized problem under realistic conditions and it suggests that the practical performance of the protocol is almost independent of the network performance. We argue that our result can be generalized to a whole class of SMC protocols.