People/Web Search Calendar Emergency Info A-Z Index UVA Email University of Virginia

Computer Science Colloquia

Tuesday, July 23, 2013
Chih-hao Shen
Advisor: abhi shelat
Attending Faculty: Gabriel Robins (Chair), Aaron Mackey (Minor Representative), Worthy Martin and Steven Myers

3:00 PM, Rice Hall, Rm. 242

PhD Dissertation Presentation
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; end users may consider using cloud computation service over their genetic information but feel insecure to upload it to the Internet. More and more ubiquitously, privacy has become a huge concern in many real-world situations. 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.