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

Computer Science Colloquia

Thursday, December 6, 2012
Chih-hao Shen
Advisor: abhi shelat
Attending Faculty: Gabe Robins (Chair); Worthy Martin, Jonathan Katz, and Aaron Mackey (Minor representative)

10:00 AM, Rice Hall, Rm. 204

PhD Proposal Presentation
Efficient Two-Party Secure Computation against Malicious Adversaries


Secure 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 a goal 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; a driver on the road may want to query the nearest gas station but hesitate to disclose her GPS coordinates; an end user may consider using cloud computation service over her genetic information but feel insecure to upload it to the Internet; and so forth. More and more ubiquitously, privacy has become a huge concern in many real-world situations.

In this thesis, we are going to propose four protocols that securely evaluate a given goal function while allowing computationally bounded participants to cheat arbitrarily. Not only are our constructions provably secure, they also enjoy the performance that is comparative to the state-of-the-art approaches and practical for real world problems. Note that a protocol is secure in the malicious model if either a cheater gets caught or both participants get their outputs. More specifically, our four constructions include (1) a hybrid approach, which uses light-weight witness-indistinguishable proofs and requires no extra gates to the goal functions; (2) a unified approach, which uses auxiliary circuits to ensure honest behavior and requires no extra intractability assumptions (given access to an oblivious transfer oracle); (3) a parallelized approach, which uses a pipelining technique and the state-of-the-art optimization techniques to have computation time (in terms of wall clock) in the malicious model roughly the same as that in the honest-but-curious model; and (4) a pre-processing approach, which reduces the computation and communication overhead by a factor of log(C), where C is the size of the boolean circuit computing the goal function. It is worth-mentioning that all of our constructions enjoy constant round complexity.