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.

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


Back to Phil's home page
Last modified March 2, 2002.

Copyright © 2002 Lucent Technologies. All rights reserved.