Communication requirements for secure computation
Deepesh Data, Vinod M. Prabhakaran · 2013
The question of whether and how mutually distrusting parties can collaborate is a central theme in cryptography. The goal of secure function computation is to ensure that parties may correctly compute functions of their data without learning additional information. A remarkable result of Ben Or, Goldwasser, and Wigderson from 1988 shows that it is possible for parties connected by pairwise, private, noise-free links to compute functions with zero error and perfect information theoretic security provided the number of parties who may collude meets a certain threshold; specifically, if the colluders form a strict minority for the honest-but-curious model and they are strictly less than a third for the malicious model. In this paper we provide basic lowerbounds on the amount of communication required to compute with zero-error and perfect security in a three-party setting under the honest-but-curious model.