Colloquium - Juan Garay

In the problem of Secure Message Transmission in the public discussion model (SMT-PD), a Sender wants to send a message to a Receiver privately and reliably. Sender and Receiver are connectedly channels, up to  of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multi-party computation on sparse networks, where a subset of the nodes are able to realizea broadcast functionality, which plays the role of the public channel. However,the {\em implementation} of such public channel in point-to-point networks is highly costly and non-trivial, which makes minimizing the use of this resource an intrinsically compelling issue.In this talk, after a brief introductory survey, we present the first SMT-PD protocol with \emph{sublinear} (i.e., logarithmic in, the message size)communication on the public channel. In addition, the protocol incurs a privatecommunication complexity of, which, as we also show, is \emph{\optimal}. By contrast, the best known bounds in both public and private channels were linear. Furthermore, our protocol has an optimal round complexity of, meaning three rounds, two of which must invoke the public channel. Finally, we ask the question whether some of the lower bounds on resource use for a single execution of SMT-PD can be beaten {on average} through amortization. In other words, if Sender and Receiver must send several messages back and forth (where later messages depend on earlier ones), can they do better than the solution of repeating an SMT-PD protocol each time? We show that amortization can indeed drastically reduce the use of the public channel: it is possible to limit the total number of uses of the public channel to no matter how many messages are ultimately sent between two nodes. (Since two uses of the public channel are required to send any reliable communication whatsoever, this is best possible.)

 

Bio: Juan A. Garay received his Ph.D. in Computer Science from Penn State in 1989, and is currently a Lead Member of Technical Staff at AT&T Labs - Research.  Before joining AT&T he was a a Member of Technical Staff at Bell Labs, and from 1990 to 1998 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, and he spent 1996 as a visiting scientist at the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam.  Juan's current research interests include theoretical and practical aspects of cryptographic protocols and schemes and privacy-preserving computation.  Besides many contributions of a foundational nature, Juan has been involved in the design, analysis and implementation of a variety of secure systems. He has published extensively in the areas of cryptography, network security, distributed computing, and algorithms, and served on the committees of many conferences and international panels.