Juan A. Garay, Ph.D.
Important: Starting Sept. 2, 2008, I'll be joining
AT&T Labs  Research.
Email: juan.a.garay@gmail.com
Member of Technical Staff
Member of the Security Research Department in the Enabling
Computing Technologies Domain, and former member of the
Computing Sciences Research
Center (Center 1127) of
Bell Labs.
Main: Cryptographic protocols,
secure multiparty computation, privacypreserving computation,
provable security,
cryptographic functions and
primitives, distributed consistency and decision problems,
broadcast encryption, secure multicast, network security.
Other areas: Distributed computing, algorithms,
fault tolerance,
networks.
 The 11th International
Security Conference  ISC '08, September 1518, 2008, Taipei, Taiwan.
 The 6th
Conference on Security and Cryptography for Networks  SCN '08,
September 1012, 2008, Amalfi, Italy.
 The 11th
International Workshop on Practice and Theory in Public Key
Cryptography  PKC '08 , March 912, 2008, Barcelona, Spain.
 The 7th ACM
DRM Workshop, October 29, 2007, Alexandria, VA.
 The 10th International Security
Conference  ISC '07, October 912, 2007, Valparaiso, Chile (PC chair).
 The 10th International Workshop
on Practice and Theory in Public Key Cryptography  PKC '07 , April 1620,
2007, Beijing, P.R. China.
 The 2nd SKLOIS Conference on Information Security and Cryptology (Inscrypt'06  formerly CISC),
Nov. 29Dec. 1, 2006, Beijing, P.R. China.
 1st International Workshop
on Information and Computer Security (ICS'06), September 2930, 2006,
Timisoara, Romania.
 The 26th International Conference
on Distributed Computing Systems (ICDCS'06), July 47, 2006, Lisbon,
Portugal.
 Eurocrypt'06,
May 28June 1, St. Petersburg, Russia.
 The 9th International Workshop
on Practice and Theory in Public Key Cryptography  PKC '06 , April 2426,
2006, New York City.
 The 10th International Conference
on Financial Cryptography and Data Security (FC'06), February 27March 2, 2006,
Anguilla, BWI.
 The 8th Annual International Conference
on Information Security and Cryptology , December 12, 2005, Seoul, Korea.
 10th International Conference
on Financial Cryptography and Data Security (FC'05), February 28March 3, 2005, Roseau, Commonwealth of Dominica.
 8th International Workshop on Practice and Theory in Public Key Cryptography  PKC '05, January 2326, 2005, Les Diablerets, Switzerland.
 11th ACM Conference on Computer and Communications Security  CCS 2004, October 2529, 2004, Washington, DC, USA.
 Advances in Cryptology  EUROCRYPT 2004, May 26, 2003, Interlaken, Switzerland.
 Latin American Theoretical INformatics  LATIN 2004, April 59, 2004,
Buenos Aires, Argentina.
 TwentySecond ACM Symposium on
Principles of Distributed Computing (PODC 2003), July 1316, 2003,
Boston, MA.
 Advances in Cryptology  EUROCRYPT 2003, May 48, 2003, Warsaw, Poland.

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

Advances in Cryptology  CRYPTO 2002, August 1822, Santa Barbara, California.

Latin American Theoretical INformatics  LATIN 2002, April 36, 2002, Cancun, Mexico.
Editor
 Starting Sept. 2, 2008: Lead Member of Technical Staff,
AT&T Labs  Research.
 April 1998August 2008: Member of Technical Staff,
Bell Labs. Member
of the Security Research Department, Enabling Computing Technologies
Domain. Former member of the
Computing Sciences Research Center.
 June 1990March 1998: Research Staff Member,
IBM T.J. Watson Research Center , Yorktown Heights, NY. Cofounder of the
Network Security Group,
with Mihir Bellare,
PauChen Cheng,
Amir Herzberg,
Hugo Krawzcyk,
and Moti Yung..
Project leader for IBM Research's eVault 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.
 19891990: Visiting Assistant Professor,
Dept. of Computer Science,
Bucknell University, Lewisburg, PA.
 19841989: 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 BarNoy (Brooklyn College),
Mihir Bellare (UCSD),
Piotr Berman
(Penn State),
Jose Brustoloni (University of
Pittsburgh),
Harry Buhrman (CWI),
Bob Cahn (AT&T),
Ran Canetti (IBM Research),
PauChen Cheng (IBM Research),
Reza Curtmola (Johns Hopkins),
Xiaotie Deng (City University
of Hong Kong),
Matthias Fitzi (ETH Zurich),
Matt Franklin (UC Davis),
Rosario Gennaro (IBM Research),
Inder Gopal (Reefedge),
Shyamnath Gollakota (MIT),
Els van Herreweghen (IBM Research),
Amir Herzberg (BarIlan University),
JaapHenk Hoepman (University
of Twente),
Gene Itkis (Boston University),
Arun Iyengard (IBM Research),
Markus Jakobsson (RSA Security),
Charanjit Jutla (IBM Research),
Seny Kamara (Johns Hopkins),
Tiko Kameda (Simon Fraser University),
Jonathan Katz (University of Maryland),
Martin Kienzle (IBM Research),
Hugo Krawzcyk (IBM Research),
ChiuYuen Koo (Google),
Dave Kristol,
Shay Kutten (Technion),
Lorenz Huelsbergen (Google),
Phil MacKenzie (Google),
Yishai Mansour (TelAviv University),
Ueli Maurer (ETH Zurich),
Daniele Micciancio (UCSD),
Mark Moir (Sun Microsystems),
Yoram Moses (Technion),
Moni Naor (Weizmann Institute of Science),
Seffi Naor (Technion),
Rafail Ostrovsky (UCLA),
David Peleg (Weizmann Institute of Science),
Ken Perry,
Benny Pinkas (HP Labs),
Carl Pomerance (Dartmouth College),
Manoj Prabhakaran (University of Illinois UrbanaChampaign),
Tal Rabin (IBM Research),
C. Pandu Rangan (IIT Madras),
Berry Schoenmakers (Technical
University Eindhoven),
Kannan Srinathan (International Institute of Information Technology,
Hyderabad),
Jessica Staddon (PARC),
Michael Steiner (IBM Research),
Bill Tetzlaff (IBM Research),
John Tromp (CWI),
Gene Tsudik (UC Irvine),
S. Harsha Vardhan (CMU),
Jose Villegas Bautista (Technical University Eindhoven),
Paul Vitanyi (CWI),
Michael Waidner (IBM Research),
Avishai Wool (TelAviv University),
Ke Yang (Google),
Bulent Yener (RPI),
Moti Yung (Columbia University and Google).
In secure multiparty computation (MPC), n parties attempt
to compute multiparty functionalities in the presence of an adversary
who may corrupt up to t of them. MPC has been extensively studied
since the statement of the problem in [Yao82]. For the standard model
with secure pairwise channels between the parties, the first general
solution to the problem was given by Goldreich, Micali and Wigderson [GMW87]
with respect to computational security. BenOr, Goldwasser and Wigderson
[BGW88] and Chaum, Crepeau and Damgard [CCD88] constructed the first general
protocols with unconditional security. For the model where, in
addition to the pairwise secure channels, a global broadcast channel
is available, Rabin and BenOr [RB89] constructed an unconditional protocol
that tolerates less than half of the parties being actively corrupted.
Traditionally, the models for MPC have assumed that certain communication
"resources" (primitives) are available to the parties (e.g., pointtopoint
secure channels, broadcast). In the first paper below we initiate the study of
what are the
minimal cryptographic primitives needed to implement MPC
among two or more players.
The issue of complete primitives for the case of two players
had been thoroughly studied. However, in the multiparty setting, when
there are n > 2 players and t of them are corrupted, the question of
what are the simplest complete primitives remained open for
t >= n/3. (A primitive is called complete
if any computation can be carried out by the players having access only to the primitive and
local computation.)
We consider this question,
and introduce complete primitives of
minimal cardinality for secure multiparty computation. The cardinality
issue (number of players accessing the primitive) is essential in settings
where primitives are implemented by some other means, and the simpler
the primitive the easier it is to realize. We show that our primitives
are complete and of minimal cardinality possible for most cases.
In the papers below, we study the problem of constructing MPC
protocols that are completely fair  meaning that either
all the parties learn the output of the function, or nobody does 
even when a majority of the parties are corrupted.
In this series of works, we first propose a
framework for fair multiparty computation, within which we formulate
a definition of secure and fair protocols. The definition follows the
standard simulation paradigm, but is modified to allow the protocol to
depend on the runing time of the adversary. In this way, we avoid a
wellknown impossibility result for fair MPC with corrupted majority
(due to [Cleve'86];
in particular, our definition admits constructions that tolerate up to
(n1) corruptions, where n is the total number of parties. Next,
we define a ``commitprovefairopen'' functionality and construct an
efficient protocol that realizes it, using a new variant of a
cryptographic primitive known as ``timelines.'' With this
functionality, we show that some of the existing secure MPC protocols
can be easily transformed into fair protocols while preserving their
security.
Putting these results together, we construct efficient, secure MPC
protocols that are completely fair even in the presence of corrupted
majorities. Furthermore, these protocols remain secure when
arbitrarily composed with any protocols, which means, in particular,
that they are concurrentlycomposable and nonmalleable. Finally, as
an example of our results, we show a very efficient protocol that
fairly and securely solves the socialist millionaires' problem.
In the first paper below, the above is achieved by assuming that the
protocol is aware of (an upper bound on) the running time of the adversary.
In the second paper we get rid of this assumption.
Secret sharing [Blakle'79,Shamir'79] is one of the most important
primitives used for the construction of secure multiparty protocols. In
secret sharing, a "dealer" wants to share a secret s among a set of n
players such that no set of t players will be able to reconstruct the
secret while any set of t+1 or more players will be able to reconstruct
the secret by combining their shares.
Verifiable secret sharing [CGMA'85] (VSS) extends ordinary
secret sharing for the
use in presence of active corruption where an adversary may corrupt up
to t players in an arbitrary way. In VSS, it is required that no t
players get any information about the secret whereas the n players
together can reliably reconstruct the secret even if t of them
deliver wrong information.
The round complexity
of a VSS protocol is defined as the number of rounds performed in the
sharing phase. Gennaro, Ishai, Kushilevitz and Rabin [GIKR'01] showed that three
rounds are necessary and sufficient when n > 3t. Sufficiency, however,
was only demonstrated by means of an inefficient (i.e., exponentialtime)
protocol, and the construction of an efficient threeround protocol was
left as an open problem.
In the paper below, we present an efficient threeround protocol for VSS.
The solution is based on a threeround solution of socalled weak
verifiable secret sharing (WSS), for which we also prove that three
rounds is a lower bound. Furthermore, we also demonstrate that one
round is sufficient for WSS when n > 4t, and that VSS can be achieved
in 1+epsilon amortized rounds (for any epsilon > 0) when n > 3t.
Say Alice has two bits b_1 and b_2 and Bob has one bit e.
An Oblivious Transfer (OT) protocol [Rabin'81] allows Bob to retrieve
b_e, while not revealing anything else: Alice does not learn which of
the two bits Bob received, while Bob does not learn b_(1e).
OT is a fundamental cryptographic primitive that has theoretical
as well
as practical applications (e.g., secure twoparty function evaluation
for the former; coin flipping over the telephone, contract signing,
and password authentication for the latter).
The first paper below investigates how to make an OT protocol work
in an "Internet setting," where many OT protocols may be running
concurrently in an asynchronous fashion. The second, more recent paper
below focuses on the version of OT where each party has committed to
his/her bits, and how in this case each party's actions can be verified.
As an application, the paper also presents efficient protocols for
secure two and multiparty computation based on the Decision DiffieHellman
problem.
While probably the most important pillar of cryptography is the believed
existence of
hard problems, the notion of moderately hard problems also bears
promise.
A moderately hard
problem is one which is not computationally infeasible to solve, but also
not easy. Moderately hard problems allow for socalled "timedrelease
cryptography," where the goal is for a party
to transform (e.g., encrypt) a piece of information,
so that it cannot be retrieved by anyone, until a predetermined amount
of time has passed.
In the two papers below we investigate the timed release and timed fair exchange of
standard digital signatures.
Such signatures, once released and/or exchanged, cannot be
distinguished from signatures of the same type obtained without a timed
release, making it transparent to an observer of the end result.
While previous work has allowed timed release and exchange of signatures,
these have not been standard, but specialpurpose signatures.
For the timed release, we build on recent work by Boneh and Naor [Crypto '00]
on timed commitments, and introduce the notion of a reusable timeline, which,
besides allowing the release of standard signatures, lowers the session
costs of existing timed applications.
Our construction for the timed fair exchange of signatures
follows the gradual release paradigm, and works on
a new ``time'' structure that we call a mirrored timeline.
Using this structure, we design a protocol for the timed fair exchange
by two parties of arbitrary values (values lying on their respective
mirrored timelines). By applying the blinding techniques developed
for the timed release application, we turn this protocol into a protocol
for the timed fair exchange of standard signatures.
The length of these mirrored timelines makes another problem apparent, which
is making sure that the underlying sequence has a period large enough
so that cycling is not observed.
We also show how to construct these structures
so that, under reasonable assumptions, this is indeed the case.
Recently there has been an interest in zeroknowledge protocols
with stronger properties, such as concurrency, unbounded simulation soundness,
nonmalleability, and universal composability.
In the paper below we show a new technique that
uses a signature scheme that is existentially unforgeable
against adaptive chosen message attacks to construct
zeroknowledge protocols with these stronger properties
in the common reference string model.
For instance, using our technique we transform any socalled "Sigmaprotocol"
(which is honestverifier zeroknowledge) into an unbounded
simulation sound concurrent zeroknowledge protocol.
We also introduce a variant of Sigmaprotocols for
which our technique further achieves the properties of nonmalleability
and/or universal composability.
In addition to its conceptual simplicity,
a main advantage of this new technique over previous ones is that
it allows for very efficient instantiation
based on the security of some efficient signature schemes and standard
numbertheoretic assumptions.
For instance, one instantiation of our technique yields an
unbounded simulation sound zeroknowledge protocol under the
Strong RSA assumption, incurring an overhead of
a small constant number of exponentiations, plus the generation of two
signatures.
In this work we consider the problem of fair
exchange of digital signatures, and how two (or more) parties
can sign a contract over a network in a way that is "fair" for both (all)
of them. Typically,
fair means (in the twoparty case) that Alice should not be able to obtain
from Bob a signature on a contract without Bob being able to get the
same signature from Alice, and viceversa.
We extend this definition so that Alice should not even be able to
convince anyone that she has the power to obatin a signature from
Bob, unless Bob also has the power to obtain Alice's signature.
We call this property abuse freeness. The papers below present
efficient twoparty and multiparty contract signing protocols that
have this property.
Multicast communication is becoming the basis for a growing number of
applications. It is therefore critical to provide founded security
mechanisms for multicast communication.
Yet, existing security protocols for multicast offer only very partial
solutions.
That was the motivation for the highly referenced
paper below, where we first present a taxonomy of multicast
scenarios on the Internet and point out the relevant security concerns.
We then address two major security
problems of multicast communication: source authentication,
and key revocation.
Maintaining authenticity in multicast protocols is a much more complex
problem than for unicast; in particular, known solutions are prohibitively
inefficient in many cases. We present a solution that is reasonable
for a range of scenarios.
Our approach can be regarded as a `midpoint' between traditional Message
Authentication Codes and digital signatures.
We also present an improved and very efficient solution to another prevailing problem for multicast protocols, namely the key revocation problem.
In a broadcast encryption scheme, digital content is encrypted to
ensure that only privileged users can recover the content from the
encrypted broadcast. Key material is usually held in a ``tamperresistant,''
replaceable, smartcard. A coalition of users may attack
such a system by breaking their smartcards open, extracting the
keys, and building ``pirate decoders'' based on the decryption keys
they extract.
In the paper below we suggest the notion of longlived broadcast
encryption as a way 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.
When a pirate
decoder is detected in a longlived encryption scheme,
the keys it contains are viewed as compromised and are no longer used for
encrypting content. We regard recarding users as an expensive process, and thus only do so when the number of active keys on a user's card falls below a threshold level. This approach differs from that of most previously known revocation schemes because such schemes aim to preserve the ability to revoke a certain number of users at all times, and hence, must do a substantial amount of key replacement after each revocation. In addition, longlived broadcast encryption schemes are a more comprehensive solution to piracy than
traitortracing schemes, because the latter only seek to identify
the makers of pirate decoders and don't deal with how to maintain
secure broadcasts once keys have been compromised.
Through a stochastic analysis, we show there is a longlived broadcast encryption
scheme that achieves a steady state in which only a small fraction of cards
need to be replaced in each epoch.
Let R(.) be a polynomial timecomputable boolean relation. Suppose we
are given a sequence ins_1,...,ins_n of instances and
asked whether
it is the case that R(ins_i)=1 for all i=1,...,n. The
naive way to figure out the answer is to compute R(ins_i) for each
i and check that we get 1 each time. But this takes n computations
of R. Can one do any better?
The above is the "batch verification" problem. We initiate a broad
investigation of it. We look at the possibility of designing probabilistic
batch verifiers, or tests, for basic mathematical relations R. Our main
results are for modular exponentiation, an expensive operation in terms
of number of multiplications: here g is some fixed element of a
group G and R(x,y)=1 iff g^x=y. We find surprisingly fast batch verifiers
for this relation. We also
find efficient batch verifiers for the degrees of polynomials.
The first application is to cryptography, where modular exponentiation
is a common component of a large number of protocols,
including
digital signatures, bit commitment, and zero knowledge.
Similarly, the
problem of verifying the degrees of polynomials
underlies (verifiable) secret sharing,
which in turn underlies many secure distributed protocols.
The second application is to program checking. We can use batch verification
to provide
faster batch checkers, in the sense of [Rubinfeld92], for modular
exponentiation. These checkers also have stronger properties than standard
ones, and illustrate how batch verification can not only speed up how we
do old things, but also enable us to do new things.
The "batch" papers:
The Byzantine agreement (BA) problem, formulated by Pease, Shostak and
Lamport in the late 70's, 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 nonfaulty processors eventually agree on a value
that was initially held by one of them.
This is a central problem in faulttolerant distributed computing
and secure multiparty computation,
and it abstracts out a variety of situations where conflicting
parties must coordinate their decisions and cooperate towards achieving a
common goal.
Typical quality measures for a BA protocol are the total number
of processors, the number of communication rounds, and its
communication complexity, alternatively given by the maximal message
size, or the total number of transmitted bits. The known lower bounds
are, respectively, n > 3t, t+1, 1, and
n (t+1)/4.
Below is a series of papers that optimize different aspects of
BA protocols for the standard model, as well as for different settings,
such as amortized agreement, agreement in networks of bounded degree,
agreement in hybrid failure models, and under mobile faults.
Of special significance is the paper with
Yoram Moses (Technion),
where we present an efficient
(i.e., polynomialtime) protocol for reaching BA with
the minimal number of processors and in the minimal number of rounds.
Achieving these bounds simultaneously with polynomial communication and
computation had been open since the formulation of the problem.
 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 BA.
 P. Berman and J. Garay,
``Cloture Votes: n/4Resilient, Polynomial Time Distributed Consensus
in t+1 Rounds.'' FOCS'89, Mathematical Systems Theory '93.
 P. Berman, J. Garay and K. Perry,
``Bit Optimal Distributed Consensus.''
Computer Science Research, Plenum Publishing Corporation, NY, NY, 1992.
 P. Berman and J. Garay.
``Fast Consensus in Networks of Bounded Degree.'' WDAG'90, Distributed Computing '93.
 A. BarNoy, X. Deng, J. Garay, and T. Kameda,
``Optimal Amortized Distributed Consensus.''
WDAG'91, Information and Computation '95.
 P. Berman, J. Garay and K. Perry,
``Optimal Early Stopping in Distributed Consensus.''
WDAG'92.
 J. Garay and K. Perry,
``A Continuum of Failure Models for Distributed Computing.''
WDAG'92, 1994 IEEE Workshop on FaultTolerant
Parallel and Distributed Systems.
 P. Berman and J.A. Garay,
``Randomized Distributed Agreement Revisited.''
FTCS'93.
 J. Garay, Reaching (and Maintaining) Agreement
in the Presence of Mobile Faults. WDAG'94.

J. Garay and Y. Moses, Fully polynomial Byzantine agreement in
t+1 rounds. STOC'03, SIAM J. of Computing 1998.
 M. Fitzi and J. Garay,
``Efficient PlayerOptimal Protocols for Strong and Differential
Consensus.''
In Proc. 22nd ACM Symposium on the Principles of Distributed
Computing (PODC '03), Sergio Rajsbaum (Ed.), pp. 211220,
Boston, MA, July 2003.
Minimum Spanning Trees
In this work we consider the question of identifying the parameters
governing the behavior of fundamental global network problems.
Many papers on distributed network algorithms consider the task of
optimizing the running time successful when an O(n) bound is
achieved on an nvertex network.
We propose that a more sensitive parameter is the network's
diameter Diam.
This is demonstrated in the paper by providing a distributed
Minimumweight Spanning Tree algorithm whose time complexity
is sublinear in n, but linear in Diam.
Our result is achieved through the application of graph
decomposition and edge elimination techniques that may be of
independent interest.
Renaming
Online Call Control
In this work we 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.
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 n1
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.
 H. Buhrman, J. Garay, J. Hoepman, M. Franklin, J. Tromp, and P. Vitanyi,
``Mutual Search.'' SODA'98;
Journal of
the ACM '99.
In this work, we present a software scheme for protecting the
integrity of computing platforms using
Timed Executable Agent Systems (TEAS).
A trusted challenger issues an authenticated
challenge to a perhaps corrupt responder. New is
that the issued challenge is an executable program
that can potentially compute any function on the
responder. The responder must compute not only the
correct value implied by the agent, but also must
complete this computation within time bounds prescribed
by the challenger. Softwarebased attestation schemes have
been proposed before  new capabilities introduced in TEAS
provide means to mitigate the existing shortcomings of such
proposed techniques.
TEAS are general and can be adapted to many applications for which
system integrity is to be tested.
Two types of adversaries to TEAS are considered.
First, we address attacks by "offline" adversaries that
attempt to discern agents' functions statically by
analyzing their program texts.
We then consider "online" adversaries, which operate while the agent runs.
For offline adversaries, we show how complexity results
from programming language analysis, as well as
undecidability considerations, can be used to thwart
such
analysis by making it impossible for the
adversary to correctly decipher all potential agents
and reply in a timely fashion. In the online scenario,
adversaries are difficult to stop in general. We do
however present
strategies that make it difficult for
these adversaries to interpret an agent in a
virtual machine and to thereby redirect its actions,
for example.
We also address the problem of creating large libraries of useful and
complicated (and hence difficult to analyze) agents through a new
technique of program blinding  we hide critical functionality
inside randomly generated machinelanguage programs. We implemented a
virtual machine that allows experimentation with this approach.
Experiments reveal that blinded agents whose execution conveys
important integrity information can be efficiently generated in
abundance.
TEAS paper.
In Proc. ACM Symposium on InformAtion, Computer and Communications Security
(ASIACCS'06), pp. 189200,
Taiwan, March 2006.
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 thirdgeneration wide
area wireless networks, e.g. 3G CDMA and UMTS. Endusers 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 (WSKE). We characterize
properties and limitations of WSKE against the requirements formalized
earlier. We also describe an instantiation of WSKE in the context of
802.11/802.1x networks, called EAPSKE. Finally, we contrast EAPSKE against
other wellknown and emerging approaches.
Joint work with Milind Buddhikot, Scott Miller, Sarvar Patel, and Luca
Salgarelli (Bell Labs).
Paper. IEEE Wireless Communication, December 2003.
Internet draft (pdf).
An architecture for providing ubiquitous lowcost
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 endtoend security in an applicationindependent 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), coinvented 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 blowup.
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 storedvalue 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, AugustSept. 1998).
I'm one of the designers of
``iKP  A Family of
Secure Electronic Payment Protocols ,'' the basis for
SET , the credit cardbased
electronic payment system being deployed by Visa and Mastercard.
The protocols implement online credit cardbased transactions between
customers and merchants while the existing financial network is used for
payment clearing and authorization. Protocols
can be applied to any accountbased payment model, such as debit cards and
electronic checks.
They are based on careful and minimal use of publickey 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 precursor and a direct ancestor of the
SET standard being deployed by MasterCard and VISA.
iKPbased payment systems have been in continuous
operation on the Internet since mid1996.
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
realworld 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
metainformation
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
PauChen Cheng,
Amir Herzberg, and
Hugo Krawzcyk.
Paper (IBM Systems Journal
37, No. 1 (1998), special issue on the Internet).
(Mail me
for any other publication not listed here.)
 J. Garay and R. Ostrovsky,
"Almosteverywhere Secure Computation."
To appear in Advances in Cryptology  EUROCRYPT 2008,
Istanbul, Turkey, April 2008.
 J. Garay, J. Katz, C. Koo and R. Ostrovsky,
"Round Complexity of Authenticated Broadcast with Dishonest Majority."
In FOCS '07,
Providence, RI, October 2123, 2007.
 J. Garay, B. Schoenmakers and J. Villegas,
"Practical and Secure Solutions for Integer Comparison."
In Proc. 10th International Workshop
on Practice and Theory in Public Key Cryptography (PKC '07),
Beijing, April 1620, 2007.
 M. Fitzi, M. Franklin, J. Garay and S. Harsha Vardhan,
"Towards Optimal and Efficient Perfectly Secure Message
Transmission."
In Proc. 4th Theory of Cryptography Conference (TCC'07),
Amsterdam, Feb. 2124, 2007.
 R. Curtmola, J. Garay, S. Kamara and R. Ostrovsky,
"Searchable Symmetric Encryption: Improved Definitions
and Efficient Constructions."
In Proc. 13th ACM Conference on Computer and Communications Security
(CCS'07), Alexandria, VA, Oct. 2006.

J. Garay and L. Huelsbergen,
``Software Integrity Protection
Using Timed Executable Agents.''
In Proc. ACM Symposium on InformAtion, Computer and Communications Security
(ASIACCS'06), pp. 189200,
Taiwan, March 2006.
 J. Garay, P. MacKenzie, M. Prabhakaran and K. Yang,
``Resource Fairness and Composability of Cryptographic Protocols.''
In Proc. 3rd Theory of Cryptography Conference (TCC'06), S. Halevi and
T. Rabin (Eds.),
LNCS (3876), SpringerVerlag, pp. 404428,
New York, NY, March 2006.

M. Fitzi, J. Garay, S. Gollakota, C. Pandu Rangan and K. Srinathan,
``RoundOptimal and Efficient Verifiable Secret Sharing.''
In Proc. 3rd Theory of Cryptography Conference (TCC'06), S. Halevi and
T. Rabin (Eds.), LNCS (3876), SpringerVerlag, pp. 329342,
New York, NY, March 2006.
 J. Garay, P. MacKenzie and K. Yang,
``Efficient and Universally Composable Committed Oblivious Transfer
and Applications.''
Preliminary version in
Proc. 1st Theory of Cryptography Conference, Moni Naor (Ed.),
Boston, MA, February 2004.

J. Garay, P. MacKenzie and K. Yang,
``Efficient and Secure MultiParty Computation with Faulty Majority
and Complete Fairness,'' in Cryptology ePrint Archive 2004/009.
 J. Garay, P. MacKenzie and K. Yang,
``Strenghtening ZeroKnowledge Protocols Using Signatures.''
In Advances in Cryptology  EUROCRYPT 2003, Eli Biham (Ed.),
LNCS (2656), SpringerVerlag, pp. 177194,
Warsaw, Poland, May 2003.

L. Salgarelli, M. Buddhikot, J. Garay, S. Miller, and S. Patel
``Efficient Authentication and Key Distribution in Wireless IP Networks.''
IEEE Wireless Communications Magazine, 5261, December 2003.
Special issue on The Evolution of WLANs and PANs,
 J. Garay and C. Pomerance,
``Timed Fair Exchange of Standard Signatures.''
In Proc. Financial Cryptography 2003,
Rebecca Wright (Ed.), LNCS, SpringerVerlag,
Gosier, Guadeloupe, January 2003.
 J. Garay and M. Jakobsson,
``Timed Release of Standard Digital Signatures.''
In Proc. Financial Cryptography 2002, Matt Blaze (Ed.),
LNCS (2537), SpringerVerlag, pp. 168182,
Southampton, Bermuda, March 2002.
 M. Fitzi, J. Garay, U. Maurer, and R. Ostrovsky,
``Minimal Complete Primitives for
Secure MultiParty Computation.''
In Proc. Advances in Cryptology  CRYPTO 2001,
Joe Kilian (Ed.),
LNCS (2139), SpringerVerlag, pp. 80100, August 2001.
 J. Garay and P. MacKenzie,
``Concurrent Oblivious Transfer.''
In Proc. FOCS 2000, pp. 314324,
Redondo Beach, CA, November 2000.
 J. Garay, J. Staddon and A. Wool,
``LongLived Broadcast Encryption.'' In
Proc. Advances in Cryptology  CRYPTO 2000, Mihir Bellare (Ed.),
LNCS (1880), SpringerVerlag, pp. 333352, August 2000.
 J. Brustoloni and J. Garay,
``MicroISPs: An Architecture for
Providing Ubiquitous LowCost Internet Access.'' (pdf file) In
Proc. 9th International World Wide Web Conference, Elsevier,
pp. 789802, Amsterdam, May 2000.
 J. Brustoloni and J. Garay,
``ApplicationIndependent EndtoEnd
Security in SharedLink Access Networks.'' Proc.
IFIP Networking 2000, LNCS (1815), SpringerVerlag, pp. 608619,
Paris, May 2000.
 J. Garay and P. MacKenzie,
``Abusefree Multiparty Contract Signing.'',
Proc.
13th International Symposium on DIStributed Computing (DISC '99),
Prasad Jayanti (Ed.), LNCS (1693), SpringerVerlag, pp. 151165,
Bratislava, September 1999.
 J. Garay, M. Jakobsson and P. MacKenzie,
``Abusefree Optimistic
Contract Signing.''
Proc. Advances in Cryptology  CRYPTO '99, Michael Wiener (Ed.), LNCS (1666), SpringerVerlag,
pp. 449466, 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. 708716, New York, NY, March 1999.

R. Cahn, J. Garay, A. Iyengard 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. 123135, August 31Sept. 4, 1998.
 M. Bellare, J. Garay, C. Jutla, and M. Yung.
``Variety Cash: a MultiPurpose Electronic Payment System.''
In Proc.
3rd Usenix Workshop on Electronic Commerce, Boston, MA, AugustSept. 1998.

M. Bellare, J. Garay and T. Rabin.
``Fast Batch Verification for Modular Exponentiation and Digital
Signatures.''
Proc. Advances in
CryptologyEurocrypt '98, Kaisa Nyberg (Ed.), LNCS (1403),
SpringerVerlag, pp. 236250, 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 InformaticsLATIN '98,
C. Lucchesi and A. Moura (Eds.), LNCS(1380), Springer Verlag,
pp.170191, 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), SpringerVerlag, pp. 275290,
Saarbruecken, Germany, September 1997.
 M. Bellare, J. Garay, and T. Rabin.
``Distributed PseudoRandom Bit
Generators  A New Way to Speed Up Shared Coin Tossing,''
Proc. 15th Annual Symp.on Principles of Distributed Computing
pp. 191200, 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. 89106, New York, NY, July 1995.
 M. Fitzi and J. Garay,
``Efficient PlayerOptimal Protocols for Strong and Differential
Consensus.''
In Proc. 22nd ACM Symposium on the Principles of Distributed
Computing (PODC '03), Sergio Rajsbaum (Ed.), pp. 211220,
Boston, MA, July 2003.
 M. Franklin, J. Garay and M. Yung,
``SelfTesting/Correcting Protocols.''
Proc. 13th International Symposium on DIStributed Computing
(DISC '99),
Prasad Jayanti (Ed.), LNCS (1693), SpringerVerlag, pp. 269283,
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. 247290. Preliminary
version in STOC '93.
 J. Garay, S. Kutten, and D. Peleg,
``A SubLinear Time Distributed Algorithm for
MinimumWeight Spanning Trees,''
SIAM J. of Computing 27, No. 1 (1998). Preliminary version in
FOCS '93.
 H. Buhrman, J. Garay, J. Hoepman, and M. Moir.
``LongLived Renaming Made Fast,'' Proc. 14th.
Annual Symp.on Principles of Distributed Computing, pp. 194203,
Ottawa, Canada, August 1995.
 A. BarNoy, X. Deng, J. Garay, and T. Kameda,
``Optimal Amortized Distributed Consensus,''
Information and Computation
120, No. 1 (1995), pp. 93100. 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), SpringerVerlag, pp. 253264, Terschelling,
The Netherlands, September 1994.
 P. Berman and J.A. Garay,
``Randomized Distributed Agreement Revisited,''
Proc. 23rd Annual International Symp. on
FaultTolerant Computing
(FTCS '93),
Toulouse, France, pp. 412421, June 1993.
 P. Berman and J. Garay.
``Fast Consensus in Networks of Bounded Degree,''
Distributed Computing 7, Vol. 2 (1993), pp. 6773.
Preliminary version in WDAG '90.
 P. Berman and J. Garay.
``Cloture Votes: n/4Resilient, Polynomial Time Distributed Consensus
in t+1 Rounds,'' Mathematical Systems Theory 26,
No. 1 (1993), pp. 320, special issue on FaultTolerant 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), SpringerVerlag, pp.153165,
Haifa, Israel, 1992, and as "Synchronizing Clocks in a System Resilient to a
Wide Class of Failures" in Proc. 1994 IEEE Workshop on FaultTolerant
Parallel and Distributed Systems, IEEE Computer Society Press,
pp.260267, 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), SpringerVerlag, pp.153165,
 P. Berman, J. Garay. and K. Perry.
``Bit Optimal Distributed Consensus,''
Computer Science Research (eds. R. YaezaBates and
U. Manber), Plenum Publishing Corporation, NY, NY, pp. 313322, 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.
``Online Admission Control and Packet
Scheduling with Interleaving.''
DIMACS TR 200115. 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 AlgorithmsESA '98,
G. Bilardi, G.F. Italiano, A. Pietracaprina and
Geppino Pucci (eds.), LNCS Vol. 1461, pp. 271282.
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), 517536.
Preliminary version in
Proc.
Ninth Annual ACMSIAM Symposium on Discrete Algorithms  SODA '98,
pp. 481489, S. Francisco, CA, January 1998.
 A. BarNoy, 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 OnLine Call Control Algorithms,''
Journal of Algorithms 23 (1997), pp. 180194.
 J. Garay and I. Gopal.
``Call Preemption in Communication Networks,''
Proc. INFOCOM '92, pp. 10431050, Florence Italy, May 1992.
Introduces the online call control problem.
Copyright © 1996
Lucent Technologies. All rights reserved.