March 23, 2005
3:00, IMU Maple Room

Fair Multi-Party Computation

Juan Garay

Abstract:
Secure multi-party computation (MPC) has been one of the most fundamental problems in cryptography. At a high level, the problem is concerned with n parties, each holding a private input, that want to compute a function of those inputs so that each party learns its own output, but no other information is revealed, even in the presence of malicious parties that may deviate arbitrarily from the protocol. Instances of MPC include password authentication, distributed auctions, on-line bidding, etc. MPC is called "fair" if either all the parties learn the output of the function being computed, or nobody does. A well-known result due to [Cleve'86] shows that fair MPC is impossible when a majority of the parties are corrupted (which in particular applies to the case of two parties and one corruption). In this talk, we show how to circumvent this impossibility result, and present fair MPC constructions that tolerate up to (n-1) corruptions. The constructions make use of some recent results in timed-release cryptography.

Biography:
Juan A. Garay received his Ph.D. in Computer Science from Pennsylvania State University in 1989. He has been a member of the Computing Sciences Center of Bell Labs since 1998. Before that, he was a research staff member at the IBM T.J. Watson Research Center. He was also a post-doc at the Weizmann Institute of Science in Israel, and a visiting scientist at the Centrum voor Wiskunde en Informatica (CWI) in The Netherlands. He has been involved in the design and analysis of a variety of secure systems, encompassing secure communication, electronic payments, and distributed storage. He has published extensively in the areas of cryptography, network security, distributed computing, and algorithms. He has served on the program committees of many conferences.