Efficient Secure Two-Party Computation Against Malicious Adversaries

Secure 2PC (Two-Party Computation) is a research problem that abstracts a wide class of real- world applications with privacy concerns. In this problem, two parties want to collaboratively compute an objective function over their private inputs while the inputs are too valuable or sensitive to share with each other. For example, competing insurance companies may be interested in finding out the statistics of their aggregated client database but reluctant to reveal their own databases; drivers on the road may want to query the nearest gas station but hesitate to disclose their GPS coordinates.

In this thesis, we constructed a framework for secure 2PC. This framework consists of a two-party interactive protocol and a few cryptographic building blocks. More specifically, the former comes from applying the cut-and-choose technique to the Yao protocol with the support of the latter, which are formally defined to capture the security properties needed in order to tackle the known attacks. We first proved that the main protocol indeed securely computes any single-output objective function even in the presence of malicious adversaries. Next, to demonstrate the power of this framework, we explicitly instantiated the building blocks by using number-theoretic assumptions and the technique of auxiliary circuits. We also presented techniques that allow our framework to handle from any single-output to any two-output objective functions. Finally, we implemented the framework to demonstrate its performance empirically. In particular, this implementation benefits from the embarrassingly parallelizable nature of our framework.