Fall 1998

December 3, 1998

Design of a dependable distributed system is a highly complex task that requires a structured approach. In this research, we adopt a layered design philosophy in which fundamental primitive services such as reliable multicast and fault detection are used to build more complex tasks such as consensus, distributed fault diagnosis, and checkpoint/rollback. One of the most fundamental services in a dependable distributed system is clock synchronization. A synchronization primitive simplifies the specification of many important aspects of distributed systems including, among others, process coordination, total event ordering, checkpointing, at-most-once message delivery, cache consistency, atomic broadcast, and deadline observance.

In this talk, we present a novel approach to clock synchronization in large distributed systems known as multistep interactive convergence has a communication cost that is orders of magnitude lower than traditional approaches and it achieves significantly tighter synchronization than approaches of comparable communication cost. We present an overview of m-ICV and its performance, compare it to alternative synchronization approaches, and discuss its implementation and validation on several platforms.

December 4, 1998

No cryptographic protocol is stronger than the mechanism protecting its secret keys. However, in many computing and communication systems, there is no “safe place” in which secret keys can be stored and cryptographic computations can be performed. This is especially true of modern networked computers: In some sense, every computer that communicates extensively with the world is bound at some point to be partly controlled by an unfriendly entity. Therefore, it is natural to consider adding an external, special-purpose device, such as a smart-card or a PCMCIA card, for storing cryptographic keys and computing cryptographic functions. Unfortunately, because such devices have limited bandwidth, memory, and processor speed, it is not feasible to rely on them to perform all of the cryptographic computation that a host computer may need for a high-bandwidth application (e.g., a private video conference).

This talk addresses “the remotely keyed encryption problem”: how to do bulk encryption and decryption for high-bandwidth applications in a way that takes advantage of both the superior power of the host and the superpior security of the smart-card? We review the network threats and the emerging services that motivate the development of secure smart-cards and remotely keyed encryption schemes. We then present a formal framework in which to study the security of these schemes, along with two specific schemes that satisfy our formal criteria. In addition to being “provably secure”, these schemes are efficient enough for use in high-speed, high-bandwidth services.

This is joint work with Matt Blaze (AT&T Labs – Research) and Moni Naor (Weizmann Institute of Science).