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
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.
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.
- April 1998-present: Member of Technical Staff,
Computing Sciences Research Center,
Bell Labs.
- 1990-March 1998: Research Staff Member,
IBM T.J. Watson Research Center, Yorktown Heights, NY. Co-founder of the
Network Security Group,
with Mihir Bellare,
Pau-Chen Cheng,
Amir Herzberg,
Hugo Krawzcyk,
and Moti Yung..
Project leader for IBM Research's e-Vault project; electronic payment systems
(see Research Highlights below);
key management protocol for IBM's firewall; network architecture
and algorithms for personal communication systems;
distributed protocols and algorithms.
- 1996: Visiting Scientist, Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands. Host:
Prof. Paul Vitanyi.
- 1992: Postdoctoral Felow,
Department of Applied Math and Computer Science,
The Weizmann Institute of Science, Rehovot, Israel. Host:
Prof. Yoram Moses.
- 1989-1990: Visiting Assistant Professor,
Dept. of Computer Science,
Bucknell University, Lewisburg, PA.
- 1984-1989: Ph.D. in Computer Science at
Penn State, University Park, PA. Adviser:
Prof. Piotr Berman.
- Before:
- EE Master's from Philips International Institute of
Technological Studies/Netherlands Universities Foundation,
Eindhoven, Holland;
- Systems Engineer, IBM Argentina;
- Electrical Engineering
degree from University of Rosario,
Argentina.
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).
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).
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.
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).
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).
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
- interacting with a single server,
- tolerating malicious server failures, and
- maitaining an (asymptotically) optimal storage blow-up.
SSRI paper (Theoretical Computer Science,
September 2000).
Design and implementation paper (IFIP Security 1998).
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).
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).
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).
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).
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].
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).
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).
(Mail me
for any other publication not listed here.)
- J. Garay and M. Jakobsson,
``Timed Release of Standard Digital Signatures.''
To appear in Proc. Financial Cryptography 2002,
Southampton, Bermuda, March 2002.
- M. Fitzi, J. Garay, U. Maurer, and R. Ostrovsky,
``Minimal Complete Primitives for
Secure Multi-Party Computation.''
In Proc. Advances in Cryptology - CRYPTO 2001,
Joe Kilian (Ed.),
LNCS (2139), Springer-Verlag, pp. 80-100, August 2001.
- J. Garay and P. MacKenzie,
``Concurrent Oblivious Transfer.''
In Proc. FOCS 2000, pp. 314-324,
Redondo Beach, CA, November 2000.
- J. Garay, J. Staddon and A. Wool,
``Long-Lived Broadcast Encryption.'' In
Proc. Advances in Cryptology - CRYPTO 2000, Mihir Bellare (Ed.),
LNCS (1880), Springer-Verlag, pp. 333-352, August 2000.
- J. Brustoloni and J. Garay,
``Micro-ISPs: An Architecture for
Providing Ubiquitous Low-Cost Internet Access.'' (pdf file) In
Proc. 9th International World Wide Web Conference, Elsevier,
pp. 789-802, Amsterdam, May 2000.
- J. Brustoloni and J. Garay,
``Application-Independent End-to-End
Security in Shared-Link Access Networks.'' Proc.
IFIP Networking 2000, LNCS (1815), Springer-Verlag, pp. 608-619,
Paris, May 2000.
- J. Garay and P. MacKenzie,
``Abuse-free Multi-party Contract Signing.'',
Proc.
13th International Symposium on DIStributed Computing (DISC '99),
Prasad Jayanti (Ed.), LNCS (1693), Springer-Verlag, pp. 151-165,
Bratislava, September 1999.
- J. Garay, M. Jakobsson and P. MacKenzie,
``Abuse-free Optimistic
Contract Signing.''
Proc. Advances in Cryptology - CRYPTO '99, Michael Wiener (Ed.), LNCS (1666), Springer-Verlag,
pp. 449-466, August 1999.
- R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and
B. Pinkas ``Multicast Security: A Taxonomy
and Efficient Constructions.''
In Proc. INFOCOM '99, Vol. 2, pp. 708-716, New York, NY, March 1999.
-
A. Iyengard, J. Garay, R. Cahn, and C. Jutla.
``Design and Implementation of a Secure Distributed Data
Repository.''
Proc. 14th IFIP International Conference on Information Security
(SEC '98), Vienna, Austria, and Budapest, Hungary, pp. 123-135, August 31-Sept. 4, 1998.
- M. Bellare, J. Garay, C. Jutla, and M. Yung.
``Variety Cash: a Multi-Purpose Electronic Payment System.''
In Proc.
3rd Usenix Workshop on Electronic Commerce, Boston, MA, August-Sept. 1998.
-
M. Bellare, J. Garay and T. Rabin.
``Fast Batch Verification for Modular Exponentiation and Digital
Signatures.''
Proc. Advances in
Cryptology--Eurocrypt '98, Kaisa Nyberg (Ed.), LNCS (1403),
Springer-Verlag, pp. 236-250, Helsinki, Finland, May 1998.
- M. Bellare, J. Garay and T. Rabin.
``Batch Verification, with Applications to Program Checking
and Cryptography.''
Invited paper,
Proc. 3rd
Latin American Symposium on Theoretical Informatics--LATIN '98,
C. Lucchesi and A. Moura (Eds.), LNCS(1380), Springer Verlag,
pp.170-191, Campinas, Brasil, April 1998.
- P. Chen, J. Garay, A. Herzberg, and H. Krawczyk.
``A Security Architecture for the Internet Protocol,''
IBM Systems Journal
37, No. 1 (1998), special issue on the Internet.
- J. Garay, R. Gennaro, C. Jutla, and T. Rabin.
``Secure Distributed Storage and Retrieval,''
to appear in Theoretical Computer Science. Preliminary version
appeared in Proc. 11th International Workshop on Distributed Algorithms
(WDAG '97), LNCS (1320), Springer-Verlag, pp. 275-290,
Saarbruecken, Germany, September 1997.
- M. Bellare, J. Garay, and T. Rabin.
``Distributed Pseudo-Random Bit
Generators - A New Way to Speed Up Shared Coin Tossing,''
Proc. 15th Annual Symp.on Principles of Distributed Computing
pp. 191-200, Philadelphia, May 1996.
- M. Bellare, J. Garay, R. Hauser, A. Herzberg, H. Krawczyk,
M. Steiner, G. Tsudik, and M. Waidner ``iKP - A Family of
Secure Electronic Payment Protocols'', Proc. 1st USENIX Workshop on
Electronic Commerce, pp. 89-106, New York, NY, July 1995.
- M. Franklin, J. Garay and M. Yung,
``Self-Testing/Correcting Protocols.'',
Proc. 13th International Symposium on DIStributed Computing
(DISC '99),
Prasad Jayanti (Ed.), LNCS (1693), Springer-Verlag, pp. 269-283,
Bratislava, September 1999.
- J. Garay and Y. Moses.
``Fully Polynomial Byzantine Agreement in t+1 Rounds,''
SIAM J. of Computing 27, No. 1 (1998), pp. 247-290. Preliminary
version in STOC '93.
- J. Garay, S. Kutten, and D. Peleg,
``A Sub-Linear Time Distributed Algorithm for
Minimum-Weight Spanning Trees,''
SIAM J. of Computing 27, No. 1 (1998). Preliminary version in
FOCS '93.
- H. Buhrman, J. Garay, J. Hoepman, and M. Moir.
``Long-Lived Renaming Made Fast,'' Proc. 14th.
Annual Symp.on Principles of Distributed Computing, pp. 194-203,
Ottawa, Canada, August 1995.
- A. Bar-Noy, X. Deng, J. Garay, and T. Kameda,
``Optimal Amortized Distributed Consensus,''
Information and Computation
120, No. 1 (1995), pp. 93-100. Preliminary version in WDAG '91.
- J.A. Garay,
``Reaching (and Maintaining) Agreement in the Presence of Mobile Faults,''
Proc. 8th International Workshop on Distributed Algorithms
(WDAG '94), LNCS (857), Springer-Verlag, pp. 253-264, Terschelling,
The Netherlands, September 1994.
- P. Berman and J.A. Garay,
``Randomized Distributed Agreement Revisited,''
Proc. 23rd Annual International Symp. on
Fault-Tolerant Computing
(FTCS '93),
Toulouse, France, pp. 412-421, June 1993.
- P. Berman and J. Garay.
``Fast Consensus in Networks of Bounded Degree,''
Distributed Computing 7, Vol. 2 (1993), pp. 67-73.
Preliminary version in WDAG '90.
- P. Berman and J. Garay.
``Cloture Votes: n/4-Resilient, Polynomial Time Distributed Consensus
in t+1 Rounds,'' Mathematical Systems Theory 26,
No. 1 (1993), pp. 3-20, special issue on Fault-Tolerant Distributed Algorithms
(ed. H.R. Strong).
- J. Garay and K. Perry,
``A Continuum of Failure Models for Distributed Computing.''
Parts of this paper appeared under the same title
in
Proc. 6th International Workshop on Distributed Algorithms
(WDAG '92), LNCS (647), Springer-Verlag, pp.153-165,
Haifa, Israel, 1992, and as "Synchronizing Clocks in a System Resilient to a
Wide Class of Failures" in Proc. 1994 IEEE Workshop on Fault-Tolerant
Parallel and Distributed Systems, IEEE Computer Society Press,
pp.260-267, 1995.
- P. Berman, J. Garay and K. Perry,
``Optimal Early Stopping in Distributed Consensus,''
Proc. 6th International Workshop on Distributed Algorithms
(WDAG '92), LNCS (647), Springer-Verlag, pp.153-165,
- P. Berman, J. Garay. and K. Perry.
``Bit Optimal Distributed Consensus,''
Computer Science Research (eds. R. Yaeza-Bates and
U. Manber), Plenum Publishing Corporation, NY, NY, pp. 313-322, 1992.
- P. Berman, J. Garay. and K. Perry.
``Asymptotically Optimal Distributed Consensus,''
a combination of results from ICALP '89, FOCS '89, and
WDAG '91. Introduces the Phase King paradigm for Distributed
Consensus.
- J. Garay, S. Naor, B. Yener and P. Zhao.
``On-line Admission Control and Packet
Scheduling with Interleaving.''
DIMACS TR 2001-15. To appear in Proc. INFOCOM'02, New York City,
June 2002.
- P. Berman and J. Garay.
``Adaptability and the Usefulness of Hints.''
Proc. 6th Annual European Symp. on Algorithms--ESA '98,
G. Bilardi, G.F. Italiano, A. Pietracaprina and
Geppino Pucci (eds.), LNCS Vol. 1461, pp. 271-282.
Venice, Italy, August 1998.
- H. Buhrman, J. Garay, J. Hoepman, M. Franklin, J. Tromp, and P. Vitanyi,
``Mutual Search.''
Journal of
the ACM, 46:4(1999), 517--536.
Preliminary version in
Proc.
Ninth Annual ACM-SIAM Symposium on Discrete Algorithms - SODA '98,
pp. 481-489, S. Francisco, CA, January 1998.
- A. Bar-Noy, J. Garay, A. Herzberg, and S. Aggarwal.
``Sharing Video on Demand.''
Parts of this paper
appeared as ``Adaptive Video on Demand'' in
Proc. 3rd Annual European Symp. on Algorithms, Corfu, Greece,
September 1995,
and parts were presented at the
Workshop on Algorithmic Aspects of Communication,
Bologna, Italy, July 1997.
- J. Garay, I. Gopal, S. Kutten, Y. Mansour, and M. Yung.
``Efficient On-Line Call Control Algorithms,''
Journal of Algorithms 23 (1997), pp. 180-194.
- J. Garay and I. Gopal.
``Call Preemption in Communication Networks,''
Proc. INFOCOM '92, pp. 1043-1050, Florence Italy, May 1992.
Introduces the on-line call control problem.
Last modified:
December 2001
Copyright © 1996
Lucent Technologies. All rights reserved.