Communication Complexity and Characterization Results in Secure Computation

Information theoretically secure multi-party computation (MPC) has been a central primitive of modern cryptography, in which mutually distrusting parties collaborate to compute a function of their private data without revealing any additional information about their data to the other parties. It is known that information theoretically secure MPC is possible among $n$ parties against the collusion of less than $n/2$ parties in the honest-but-curious model; the threshold is $n/3$ in the malicious model.

Despite the huge success in many frontiers of cryptography, many basic questions in the study of secure MPC have seen a little progress. Two of these questions are the subject of this thesis: communication and randomness complexity of secure MPC; and characterization of which functions are securely computable. We study these questions in two and three party settings against the corruption of a single party in the honest-but-curious model. In the three party setting, we develop new information theoretic tools to obtain tight lower bounds on communication and randomness complexity of secure MPC. We derive lower bounds for both the perfect security case (i.e., zero-error and no leakage of information) and asymptotic security (where the probability of error and information leakage vanish as block-length goes to infinity); and they are shown to be tight for several interesting functions.

In the two party setting, we consider secure computation of randomized functions. When both the parties (Alice and Bob) are required to produce outputs, even the characterization of which {\em randomized} functions are securely computable is not known; however, the {\em deterministic} counterpart of this problem was resolved by Kushilevitz (FOCS 1989) around three decades ago. We make some progress in this long standing open problem and give a couple of characterizations: for randomized functions that have up to ternary output alphabet, and for randomized functions that are securely computable by up to two-round protocols. The problem becomes easier when only one party is required to produce the output. We study this problem further in four cases: (i) when privacy is required against both the parties; (ii) when privacy is required only against Alice; (iii) when privacy is required only against Bob; and (iv) when there is no privacy requirement. For all the four cases we obtain optimal rate expressions in both perfect and asymptotic security settings.