Practical Secure Two-Party Computation: Techniques, Tools, and Applications

Many compelling applications involve computations that require sensitive data from two or more individuals. For example, as the cost of personal genome sequencing rapidly plummets many genetics applications will soon be within reach of individuals such as comparing one’s genome with the genomes of different groups of participants in a study to determine which treatment is likely to be most effective. Such comparisons could have tremendous value, but are currently infeasible because of the privacy concerns both for the individual and study participants. What is needed is a way to produce the result of the comparison without exposing either party’s private inputs. Our ultimate aim is to make privacy-preserving computation practical and accessible enough to be used routinely in applications such as personalized genetics, medical research, and privacy-preserving biometrics.

Theoretical solutions to this problem, known as secure multi-party computation, have been known for several decades, including a general solution developed by Andrew Yao based on garbled circuits. Because of its extensive memory use and computational cost, however, the garbled circuits approach has traditionally been considered more of a theoretical curiosity than a practical mechanism for building privacy-preserving applications. Recent developments in cryptographic techniques and new implementation approaches are beginning to change this, however, and admit the possibility of scalable, practical secure computation. This project is designing methods for avoiding the memory bottleneck associated with garbled circuit evaluation by aggressively pipelining circuit generation and evaluation, and exploring a variety of techniques for reducing the size of garbled circuits. Another issue the limits the use of secure computation in practice is the need for standard protocols to assume an honest-but-curious adversary who always follows the specified protocol. This project is developing new techniques for dealing with malicious adversaries, improving the standard cut-and-choose and commit-and-prove approaches by using new cryptographic tools and exploring an alternate model in which a verifiable trusted party generates the circuit but is not trusted with any private data. The project is also developing techniques to audit the information that can be inferred from the result of a secure computation. Another goal is to make secure computation more accessible to developers by developing programming tools for defining secure computations at a high level, based on information-flow analysis and program partitioning.