Secure Computation: From Theory Towards Practice

  • Date
    January 17, 2012
  • Time
    10:30 AM
  • Location
    366 WVH

Abstract

In 1982, Yao introduced the field of “secure computation”, in which n parties, holding private inputs x_1,…,x_n, engage in a protocol to compute some function f(x_1,…,x_n), while revealing nothing more than the output. In the decade that followed, the topic of secure computation was thoroughly explored, and almost every theoretical question was answered. In the past decade, the focus has shifted towards improving efficiency, and building implementations. Today, secure computation is poised to become an extremely powerful tool with wide-ranging application. Both bodies of research were essential in bringing this about.

In this talk, we review several recent results. We first provide insight into one of the few remaining theoretical questions in secure computation. We then demonstrate improved efficiency for secure computation in several particular settings of interest. On the theoretical side, we discuss the problem of “fairness” in secure computation, which is a security property guaranteeing simultaneous output delivery to both parties. Until recently, this was widely believed to be impossible to achieve; we demonstrate that some interesting functions can in fact be computed with complete fairness. In the second half of the talk, we will focus on several settings that arise in more modern, real-world environments, and show how we can tailor the theoretical results to greatly improve efficiency. In presenting this selection of research, we hope to demonstrate the importance of both foundational and applied cryptographic theory.

Brief Biography

After receiving a B.A. in computer science and physics from Columbia University, Dov worked in the research and development group at Bloomberg Inc. before returning to graduate school. In 2010, he received his PhD in cryptography under Jonathan Katz at the University of Maryland. He is currently a postdoc at Columbia University, where he is working with Tal Malkin as a recipient of the Computing Innovation Fellowship.