Colloquia, Seminars and Conference News
Title : Almost-everywhere Secure Computation
Date : October 24, 2007. (11:00 am) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Dr. Juan Garay
Abstract:
Secure multi-party computation (MPC) is a central problem in cryptography. At a high level, the problem is concerned with n parties, each holding a private input, who want to compute a function of those inputs so that each party learns his 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, contract signing, electronic voting, etc.
Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity---specifically, $\Omega(t)$, where $t$ is the number of potential corrupted parties (or nodes) in the network. This impossibility result renders existing MPC results far less applicable in practice, since most deployed networks have in fact a very small degree.
In this talk, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call {\em almost-everywhere MPC}, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corrupted nodes. In essence, our definition allows the adversary to implicitly wiretap some of the good nodes by corrupting sufficiently many nodes in the ``neighborhood'' of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.
Instrumental in our constructions is a new model and protocol for the {\em secure message transmission} (SMT) problem, which we call {\em SMT by public discussion}, and which we use for the establishment of pairwise secure channels in limited connectivity networks.
This is joint work with Rafail Ostrovsky (UCLA).
Bio: Juan A. Garay received his Ph.D. in Computer Science from The
Pennsylvania State University in 1989. He also holds the degree of
Electrical Engineer from the University of Rosario (Argentina), and a
Master's in Electrical Engineering from the Eindhoven Technical
University (The Netherlands). He has been with Bell Labs since
1998. From 1990 until 1998 he was a research staff member at the IBM
T.J. Watson Research Center. In 1992 he was a postdoctoral fellow at
The Weizmann Institute of Science in Israel; in 1996 a visiting
scientist at the Centrum voor Wiskunde en Informatica (CWI) in
Amsterdam, The Netherlands; and in 2006 a core participant of the
"Securing Cyberspace" program at the Institute for Pure and Applied
Mathematics of UCLA. His current research interests include
theoretical and practical aspects of cryptographic protocols and
privacy-preserving computation. Besides many contributions of a
foundational nature, Dr. Garay has been involved in the design,
analysis and implementation of a variety of secure systems,
including authentication and key exchange for fixed and wireless
networks, electronic payment schemes, and distributed storage. He has
published extensively in the areas of cryptography, distributed
computing, algorithms, and fault tolerance, and served on the program
committees of many conferences and international panels.
[Back]
