photo






Juan A. Garay

Computing Sciences Research Center
Bell Labs - Lucent Technologies
600 Mountain Ave.
Murray Hill, NJ 07974, USA
Phone: (908) 582-5867
Fax: (908) 582-5857
E-mail: garay@research.bell-labs.com







line separator

Research Interests

Conferences I'm Currently Involved in

Brief Bio

Research Collaborators

Recent Projects and Industrial Impact

Some Research Highlights

Selected Publications

line separator

Research Interests

Main: Cryptographic protocols, provable security, multi-party computation, authentication, cryptographic functions and primitives, zero-knowledge, secure network protocols, secure multicast.

Other areas: Distributed computing, algorithms, fault tolerance, networks.

line separator

Conferences I'm Currently (or Have Recently Been) Involved in

Advances in Cryptology - EUROCRYPT 2003, May 4-8, 2003, Warsaw, Poland.

16th International Symposium on DIStributed Computing (DISC 2002), October 28-30, 2002, Toulouse, France.

Advances in Cryptology - CRYPTO 2002, August 18-22, Santa Barbara, California.

Latin American Theoretical INformatics - LATIN'2002, April 3-6, 2002, Cancun, Mexico.

line separator

Brief History

line separator

Research Collaborators

Include:

Amotz Bar-Noy (Brooklyn College), Mihir Bellare (UCSD), Piotr Berman (Penn State), Jose Brustoloni (Bell Labs), Harry Buhrman (CWI), Bob Cahn (AT&T), Ran Canetti (IBM Research), Pau-Chen Cheng (IBM Research), Xiaotie Deng (City University of Hong Kong), Matthias Fitzi (ETH Zurich), Matt Franklin (UC Davis), Rosario Gennaro (IBM Research), Inder Gopal (Reefedge), Els van Herreweghen (IBM Research), Amir Herzberg, Jaap-Henk Hoepman (University of Twente), Gene Itkis (Boston University), Arun Iyengard (IBM Research), Markus Jakobsson (RSA Security), Charanjit Jutla (IBM Research), Tiko Kameda (Simon Fraser University), Martin Kienzle (IBM Research), Hugo Krawzcyk (Technion), Dave Kristol, Shay Kutten (Technion), Phil MacKenzie (Bell Labs), Yishai Mansour (Tel-Aviv University), Ueli Maurer (ETH Zurich), Daniele Micciancio (UCSD), Mark Moir (University of Pittsburgh), Yoram Moses (Technion), Moni Naor (Weizmann Institute of Science), Seffi Naor (Technion), Rafail Ostrovsky (Telcordia), David Peleg (Weizmann Institute of Science), Ken Perry, Benny Pinkas (InterTrust), Tal Rabin (IBM Research), Jessica Staddon (Xerox PARC), Michael Steiner (University of Saarbrucken), Bill Tetzlaff (IBM Research), John Tromp (CWI), Gene Tsudik (UC Irvine), Paul Vitanyi (CWI), Michael Waidner (IBM Research), Avishai Wool (Lumeta Corporation), Bulent Yener, Moti Yung (CertCo).

line separator

Recent Projects and Industrial Impact

Efficient Authentication and Key Distribution in Wireless IP Networks

Emerging technologies such as 802.11 are facilitating the introduction of wireless IP services to an increasing number of users. The market forecasts suggest that a new class of Wireless Internet Service Providers (WISPs) will deploy more and more wireless IP networks based on these new technologies. To offer uninterrupted IP service, these networks will need to be integrated with other wireless technologies, such as the ones used by third-generation wide area wireless networks, e.g. 3G CDMA and UMTS. End-users will be able to roam across different WISP domains, and across networks that employ different access technologies. To provide seamless mobility to customers, authentication, session key establishment, mobility management and billing must be integrated across these different wireless IP networks. Therefore, efficient authentication and dynamic key exchange protocols that support homeogenous domains as well as networks with roaming agreements across trust boundaries are keys to the success of these networks. In this work we describe a simple network model that accounts for heterogeneity in network providers, and formalize the requirements of any authentication and key exchange protocol that has to operate in such model, in terms of network efficiency, security and fraud prevention. We then introduce a new authentication and key exchange protocol, called Wireless Shared Key Exchange (W-SKE). We characterize properties and limitations of W-SKE against the requirements formalized earlier. We also describe an instantiation of W-SKE in the context of 802.11/802.1x networks, called EAP-SKE. Finally, we contrast EAP-SKE against other well-known and emerging approaches.
Joint work with Milind Buddhikot, Scott Miller, Sarvar Patel, and Luca Salgarelli (Bell Labs).

Paper.
Internet draft (pdf).

Long-lived Broadcast Encryption

A new notion of adapting broadcast encryption to the presence of pirate decoders and maintaining the security of broadcasts to privileged users while rendering all pirate decoders useless. More comprehensive than traitor-tracing schemes. We design scheme that achieves a steady state in which only a small fraction of cards need to be replaced in each epoch.
Work done at Bell Labs, with Jessica Staddon and Avishai Wool.

Crypto'00 paper.

MicroISPs

An architecture for providing ubiquitous low-cost internet access. Overcomes conventional ISP architecture's shortcomings of high access link costs and poor mobility support. Novel billing; accomodates a variety of offline and online payment methods.
Work done at Bell Labs, with Jose Brustoloni .

Paper (pdf file; Proc. 9th International World Wide Web Conference, Amsterdam, May 2000).

IPSec/NAT Interoperation

IP Security (IPSec) has often been considered incompatible with Network Address Translation (NAT). We proposed a simple DHCP extension that allows client IPSec implementations to interoperate correctly with NAT. This extension is part of EASE (for EAsy, Secure and Economical Internet Access), an architecture that exploits the higher bandwidths of cable or xDSL to make Internet connectivity easy and economical for SOHO or ``road warrior'' users, without compromising fairness or security. EASE allows for end-to-end security in an application-independent fashion.
Work done at Bell Labs, with Jose Brustoloni .

EASE paper (Proc. IFIP Networking 2000, Paris, May 2000).

The e-Vault

Project leader for IBM Research's electronic vault project. The project is based on the Secure Storage and Retrieval of Information technique (SSRI), co-invented with Rosario Gennaro, Charanjit Jutla and Tal Rabin from IBM Watson. The technique guarantees the secure (including confidentiality) storage and retrieval of data in a distributed storage system, while
  1. interacting with a single server,
  2. tolerating malicious server failures, and
  3. maitaining an (asymptotically) optimal storage blow-up.

SSRI paper (Theoretical Computer Science, September 2000).
Design and implementation paper (IFIP Security 1998).

Variety Cash

A new electronic money system striking a balance between functionality, security, and user privacy. The system can encompass both network and stored-value card based payment mechanisms, with transferability between them, hence the name.
Work done at IBM, with Mihir Bellare, Charanjit Jutla , and Moti Yung.

Variety Cash paper ( Proc. 3rd Usenix Workshop on Electronic Commerce, Boston, MA, August-Sept. 1998).

iKP -- A Family of Secure Electronic Payment Protocols

I'm one of the designers of ``iKP - A Family of Secure Electronic Payment Protocols ,'' the basis for SET , the credit card-based electronic payment system being deployed by Visa and Mastercard.
The protocols implement on-line credit card-based transactions between customers and merchants while the existing financial network is used for payment clearing and authorization. Protocols can be applied to any account-based payment model, such as debit cards and electronic checks. They are based on careful and minimal use of public-key cryptography and can be implemented in either software or hardware. Individual protocols differ in both complexity and degree of security. In addition to being a pre-cursor and a direct ancestor of the SET standard being deployed by MasterCard and VISA. iKP-based payment systems have been in continuous operation on the Internet since mid-1996. This longevity - as well as the security and relative simplicity of the underlying mechanisms - make the iKP experience unique. For this reason, the design and implementation paper below also reports on a number of practical issues arising in the course of implementation and real-world deployment of a secure payment system.

iKP Usenix paper (Proc. 1st USENIX Workshop on Electronic Commerce, New York, NY, July 1995).
Design, implementation and deployment paper (JSAC, special issue on Network Security, Vol. 18, No. 4, Aril 2000).

A Security Architecture for the Internet Protocol

Security architecture for protecting the secrecy and integrity of Internet traffic at the IP layer, allowing for the establishment of a secure channel between any two communicating systems over the Internet. The design includes a key management protocol, called MKMP, for establishing shared secrets between communicating parties and meta-information prescribed by the security policy. The architecture allows for the establishment of a secure channel between any two communicating systems over the Internet. This technology is a component of IBM's Firewall product, and is being ported to other IBM platforms.
Work done at IBM with Pau-Chen Cheng, Amir Herzberg, and Hugo Krawzcyk.

Paper (IBM Systems Journal 37, No. 1 (1998), special issue on the Internet).

line separator

Some Research Highlights

Concurrent Oblivious Transfer

When constructing cryptographic protocols for the real world, and in particular, when they are meant to be run over the Internet, they need to be secure even when instances of the protocols are run concurrently. Oblivious Transfer (OT) is at the heart of many cryptographic protocols, and there have been protocols which are meant to be run in a concurrent setting and which are based on OT. However, all OT protocols in the literature have used zero-knowledge proofs, which, as discussed below, may not necessarily be secure when run concurrently!
In this work we consider the problem of designing an efficient OT protocol that is provably secure in a concurrent setting, i.e., where many OT sessions may be running concurrently with their messages interleaved arbitrarily. Known OT protocols use zero-knowledge proofs, and no concurrent zero-knowledge proofs are known that use less than a poly-logarithmic number of rounds (at least without requiring a pre-processing phase, a public random string, an auxiliary string, timing constraints, or pre-distributed public keys). We introduce a model for proving security of concurrent OT protocols, and present a protocol that is proven secure in this model based on the Decisional Diffie-Hellman problem. The protocol is efficient, requiring only a slightly non-constant number of rounds.
Work done at Bell Labs, with Phil MacKenzie .

Concurrent Oblivious Transter paper (Proc. FOCS 2000, Redondo Beach, CA, November 2000).

Byzantine agreement

The Byzantine agreement problem involves n processors (agents, players), each of which holds an initial value. At most t of the processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. This is a central problem in fault-tolerant distributed computing and secure multi-party computation, and it abstracts out a variety of situations where conflicting parties must coordinate their decisions and cooperate towards achieving a common goal.
Together with Yoram Moses (Technion), we developed an efficient (i.e., polynomial-time) algorithm for reaching Byzantine agreement which requires the minimal number of processors possible (n > 3t), in the minimal number of rounds of communication (t+1). The problem had been open since its formulation by Pease, Shostak and Lamport in 1978.

Paper (SIAM J. of Computing 1998) [Warning: Big ps file].

Adaptability

In this work, Piotr Berman. and I introduce adaptability, a new measure for the quality of algorithms. We study the general problem of designing algorithms in situations where there is some information about the typical conditions that are encountered when the respective problem is solved. The basic goal is to assure efficient performance in the typical case, while satisfying the correctness requirements in every case. The new notion generalizes competitive analysis and related frameworks, and applies to sequential, parallel and distributed algorithms alike.
In a nutshell, a ``hint'' function conveys certain information about the environment in which the algorithm operates. Adaptability compares the performance of the algorithm against that of the ``specialist'' - an algorithm specifically tuned to the particular hint value. From this perspective, finding that no single algorithm can adapt to all possible hint values is not necessarily a negative result, provided that a family of specialists can be constructed.
Our case studies - scheduling of jobs on parallel machines and distributed consensus - provide examples of both kinds.

Adaptability paper (ESA '98).

Mutual Search (Algorithmics for Fun)

Say 2 agents land over a space of n sites and have to locate each other by sending queries of the form ``Anybody at site i?.'' How many queries would it take them? Intuition might suggest that any (deterministic) algorithm would require a total of n-1 queries in the worst case. In this work we formulate this problem, and derive lower and upper bounds for several variants. In particular, for the case posed above, we show that 0.586n total queries suffice.

Mutual Search paper (Journal of the ACM, 46:4(1999), 517-536).

line separator

Selected Publications

(Mail me for any other publication not listed here.)

Cryptographic Protocols and Network Security

Distributed Computing

Algorithms (on-line; network; new quality measures)

line separator

Last modified: December 2001

Copyright © 1996 Lucent Technologies. All rights reserved.