Research and Selected Publications
Cryptography
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.
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.
Other interests
Other interests in the crypto field include certification authorities,
key exchange, VPNs (virtual private networks), zero-knowledge protocols,
and anonymity issues - papers to be coming soon!
Parallel Algorithms/Networks/Contention Resolution
- with L. Goldberg
and
M. Jerrum
An Omega(sqrt(loglog n)) Lower Bound for Routing in Optical Networks
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
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
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
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
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)
in FOCS'97, pp. 213-222.
- with L. Goldberg
Analysis of Practical Backoff Protocols for Contention Resolution with
Multiple Servers in SODA'96, pp. 554-563. (to appear in JCSS)
(
Full version)
-
A Lower Bound for the QRQW PRAM
in SPDP'95, pp. 231-237. And then,
An Improved Lower Bound for the QRQW PRAM
in WORPC'96 (in conjunction with IPPS'96)
-
A Separation Between Reconfigurable Mesh Models
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)
in STOC'94, pp. 153-162. (to appear in Journal of the ACM)
-
A Lower Bound for Order Preserving Broadcast in the Postal Model
Parallel Processing Letters, vol 3, num 4, 1993, pp. 313-320.
- with E. Hao and Q. Stout
Selection on the Reconfigurable Mesh (full paper)
Frontiers of Massively Parallel Computing '92, pp. 38-45.
- with X. Deng and E. Koutsoupias
Competitive Implementation of Parallel Programs
to appear in Algorithmica.
Back to Phil's home page
Last modified November 10, 1998.
Copyright ©
1998 Lucent Technologies. All rights reserved.