Research and Selected Publications
Cryptography
Networked Cryptographic Devices Resilient to Capture
We develop simple techniques to allow mobile devices to perform
cryptographic operations in networked applications, such that the local
private key is not vulnerable (even to an offline dictionary attack, if
the key is "protected" by a password or PIN) when the device is
captured. We assume no hardware tamper resistance, but require the the
device to interact with a remote server
in order to perform the cryptographic operation. This remote server can
be untrusted in the sense that its compromise does not reduce the
security of the private key unless the device is also captured. Our
techniques further support key disabling, by which the rightful owner
of the stolen device may
disable further use of the private key, even if the attacker already
knows
the user's password.
Password-Authenticated Key Exchange
How do you achieve strong security for mutual authentication and key
exchange, while only requiring users to remember short passwords? The
papers below describe some protocols that achieve just that. The first
set of papers describe
a protocol based on Diffie-Hellman, while the second set describe a
protocol
based on RSA. In each paper, we also show how the protocols can be
extended
to similar client/server protocol in which the server does not actually
know the password, and compromise of the server does not allow someone
to
masquerade as the client. All of these protocols are proven secure
against
the strongest type of adversary: one that can perform active attacks
(such
as impersonation of servers!) and that may perform offline dictionary
attacks
if some verification information about the password is obtained.
Against
our protocols, we show that the best this attacker can do is guess
passwords
online one-by-one. Such an attack can easily be detected. One could
compare
our protocols to: (1) telnet, which sends passwords unencrypted, and
thus
is vulnerable to passive eavesdropping attacks, (2) challenge-response
protocols,
which are vulnerable to offline dictionary attacks by an eavesdropping
adversary,
(3) ssh, which requires the user to know the public key of the server
in
order to prevent active adversary attacks.
Diffie-Hellman based:
RSA-based:
Threshold server protocols (compromise of fewer servers than the
threshold
does not allow an offline dictionary attack):
Other work on password-authenticated key exchange:
See Integrity Sciences
and SRP
for
information on other work in this area.
Encryption
It is widely believed that for an public-key encryption scheme to be
secure, it must be non-malleable. That is, no malicious party
should be able to take a given encryption and produce a new encryption
of a related value, at least not with any better probability than if he
had not seen the given encryption in the first place. We
investigate slightly weaker forms of non-malleability, and where
encryption schemes satisfying these weaker requirements may be used.
Commitments
A basic commitment scheme consists of a commit phase and an open phase
with the following properties. Alice may commit to a value v in
the commit phase, and later reveal v in the open phase such that
(binding) Alice may not change the value v once she has committed, and
(hiding) until the open phase, it is infeasible for another party to
determine v. We investigate stronger properties of commitment
schemes (like non-malleability and simulation-sound binding), and their
applications, in particular to zero-knowledge protocols.
Oblivious Transfer
Say Alice has two bits b(1) and b(2), and Bob has one bit e. An
oblivious transfer protocol between Alice and Bob will allow Bob to
retrieve the bit b(e). Also, Alice will not learn e (i.e., which bit
Bob receives), and Bob will not learn b(1-e) (i.e., the bit that he did
not receive). Oblivious transfer is a fundamental cryptographic
primitive that has theoretical applications (e.g., 2-party secure
function evaluation) and practical applications (e.g., flipping a bit
over the telephone, contract signing, and even password
authentication!). The earlier paper below investigates how to make
oblivious transfer protocol that works in an "Internet setting," where
concurrent oblivious transfer protocols may be running in an
asynchronous fashion. The more recent paper focuses on the case
where each party has committed to its bits, and how in this case each
party's actions may be verified.
Distributed Contract Signing
The problem of fair exchange of signatures and other types of
electronic documents over a network can be quite challenging. We have
been looking at
fair exchange of signatures, and in particular, how two parties can
sign a contract over a network in a way that is "fair" for both of
them. Exactly what does fair mean? In some sense, party A should not be
able to obtain a signature on a contract from party B without party B
also having the signature from party A, and vice-versa. In our view,
this definition should be extended so that party A should not even be
able to convince anyone that it has the power to obtain party B's
signature, unless B also has the power to obtain A's signature, no
matter what A does. We call this property "abuse-freeness". The papers
below deal with efficient contract signing protocols that have this
property.
Distributed cryptosystems
A major focus of research in the past couple years has been on the
development of tools to enable distributed cryptosystems. These
distributed cryptosystems can be used, for instance, as the basis of a
highly secure and reliable certification
authority. The tools include (1) key generation protocols, in which
keys
are generated in a distributed fashion, so that no small quorum of
corrupted
participants can disrupt the protocol or learn the key; (2) signature
(decryption)
protocols, in which messages are signed (decrypted) in a distributed
fashion
by participants who each know a share of the secret key, so that no
small
quorum of corrupted participants can disrupt the protocol or learn the
key;
and (3) proactive update protocols, in which the secret shares are
renewed/refreshed
so that any knowledge of old keys is rendered useless, thus
facilitating
organizational changes, recovery of corrupted participants, and
prevention
of long-term adversarial attacks.
- An
Efficient
Two-Party Cryptosystem Secure Against Adaptive Chosen-Ciphertext Attack
(pdf),
in PKC 2003, pp. 47-61. Full
version (pdf).
- with M. K. Reiter
,
Two-Party Generation of DSA Signatures . (Extended Abstract) in
Crypto, 2001, pp.137-154.
- with Y. Frankel and M.
Yung ,
"Pseudorandom Intermixing": A Tool for Shared Cryptography
(pdf) in PKC2000, pp. 306-325.
- with Y. Frankel and M.
Yung , Adaptively-Secure
Optimal-Resilience Proactive RSA (pdf)
in Asiacrypt'99.
- with Y. Frankel and M.
Yung , Adaptively-Secure
Distributed Public Key Systems (pdf)
in ESA'99.
- with Y. Frankel and M.
Yung , Robust
Efficient Distributed RSA Key Generation (pdf)
in
STOC'98, pp. 663-672.
- with Y. Frankel, P.
Gemmell , and M. Yung
, Optimal
Resilience Proactive Public-Key Cryptosystems (pdf)
in FOCS'97, pp. 384-393.
- with Y. Frankel, P.
Gemmell , and M. Yung
, Proactive
RSA (pdf)
in Crypto'97, pp. 440-454.
Zero-Knowledge
With a zero-knowledge proof, one party can prove to another party that
a certain statement is true (like "These two graphs are isomorphic" or
"I know the discrete log of this value") without revealing any other
information. In fact, an outside observer of the protocol does not
obtain any information at all! Zero-knowledge proofs are very useful in
designing cryptographic protocols, and we have shown some techniques
for designing very efficient zero-knowledge proofs of knowledge.
Certification
Electronic Cash
I have been very interested in all forms of electronic commerce
including e-cash. The following paper shows some flaws in e-cash
schemes that allow users to obtain coins which do not contain their
correct identity, and thus can be double-spent (in an off-line system)
without any consequence.
Anonymity
An area that is very hot these days is privacy and anonymity. The
following paper shows a scheme for investing anonymously. It is based
on e-shares , and uses anonymous e-cash schemes as a basis. It
handles the issues of obtaining dividends anonymously and paying taxes
on those dividends anonymously, but using a protocol in which a tax
agency can verify that all taxes have been properly paid.
Parallel Algorithms/Networks/Contention
Resolution
- with L.
Goldberg , Analysis
of Practical Backoff Protocols for Contention Resolution with Multiple
Servers (pdf)
Journal of Computer and System Sciences, vol. 58, no. 1, pp. 232-258,
1999. (Preliminary version in SODA'96, pp. 554-563)
- with X. Deng
and E. Koutsoupias , Competitive
Implementation of Parallel Programs (pdf)
Algorithmica, vol. 23, no. 1, pp. 14-30, 1999.
- with L.
Goldberg and M. Jerrum
,
An Omega(sqrt(loglog n)) Lower Bound for Routing in Optical Networks
(pdf) SIAM Journal on Computing, vol. 27, no. 4, pp. 1083-1098,
1998. (Preliminary version in SPAA'94, pp. 147-156.)
- with V.
Ramachandran , ERCW
PRAMs and Optical Communication (pdf)
Theoretical Computer Science, vol. 196, pp. 153-180, 1998. (Preliminary
version in EuroPar'96.)
- with V.
Ramachandran , Computational Bounds for Fundamental Problems on
General-Purpose Parallel Models, in SPAA'98.
- with Q. Stout, Ultra-Fast
Expected Time Parallel Algorithms (pdf)
Journal
of Algorithms, vol. 26, pp. 1-33, 1998. (Preliminary version in
SODA'91,
pp. 414-423.)
- The
Random Adversary: A Lower-Bound Technique for Parallel Algorithms (pdf)
SIAM Journal on Computing, vol. 26, no. 6, pp. 1559-1580, 1997.
(Preliminary version in SODA'92, pp. 94-99)
- Lower
Bounds for Randomized Exclusive-Write PRAMs (pdf)
Theory of Computing Systems, vol. 30, pp. 599-626, 1997. (Preliminary
version in SPAA'95, pp.254-263. )
- with L.
Goldberg , Contention
Resolution with Guaranteed Constant Expected Delay - full paper (pdf)
in FOCS'97, pp. 213-222.
- A
Lower Bound for the QRQW PRAM (pdf)
in SPDP'95, pp. 231-237. And then, An
Improved Lower Bound for the QRQW PRAM (pdf)
in WORPC'96 (in conjunction with IPPS'96)
- A
Separation Between Reconfigurable Mesh Models (pdf)
Parallel Processing Letters, vol. 5, no. 1, pp. 15-22, 1995.
(preliminary version (which contained an error) appeared in IPPS '93,
pp. 84-88)
- with G. Plaxton
and R. Rajaraman , On
Contention
Resolution and Associated Probabilistic Phenomena - full paper (pdf)
in STOC'94, pp. 153-162. (to appear in Journal of the ACM)
- A
Lower Bound for Order Preserving Broadcast in the Postal Model (pdf)
Parallel Processing Letters, vol 3, num 4, 1993, pp. 313-320.
- with E. Hao and Q. Stout, Selection
on the Reconfigurable Mesh - full paper (pdf)
Frontiers of Massively Parallel Computing '92, pp. 38-45.
Back to Phil's
home page
Last modified March 2, 2002.
Copyright
©
2002 Lucent Technologies. All rights reserved.