Secure Two-Party Computation in Two Rounds

David Omer Horvitz, Ph.D. Candidate
Department of Computer Science
University of Maryland, College Park

Abstract

A long-standing goal of modern cryptography has been to devise general protocols that allow two (or multiple) parties to securely-compute *any* functionality of their interest. The task is now known to be feasible, yet obtaining *efficient* solutions remains a challenge.

In this talk, I will show that the secure computation of any two-party functionality can be performed in only *two* rounds of communication, even in a setting that accounts for concurrent execution with other protocols; previous solutions took a non-constant number of rounds. I rely on a commonly-used setup assumption (the availability of a common reference string to the participating parties), keeping in mind that some sort of setup is known to be necessary in this setting. Since two rounds are necessary, this provides a tight characterization of the round complexity for this problem.

I discuss how the result may be applied to obtain round-efficient protocols for the doubly-blind evaluation of trust policies on sets of credentials; and for blind signatures.

Speaker Bio

Omer Horvitz has just defended his doctoral thesis at the Computer Science department in the University of Maryland. He is interested in cryptography and network security.