Title: Agents' privacy in distributed algorithmic mechanisms

In traditional theoretical computer science (TCS), computational agents are typically assumed either to be obedient (i.e., to follow the prescribed algorithm) or to be adversaries who "play against" each other. On the other hand, the strategic agents in economic theory are neither obedient nor adversarial. Although one cannot assume that they will follow the prescribed algorithm, one can assume that they will respond to incentives. Thus, the economics literature traditionally stressed incentives and downplayed computational complexity, and the TCS literature traditionally did the opposite. The emergence of the Internet as a standard platform for distributed computation has radically changed this state of affairs: Ownership, operation, and use by many self-interested, independent parties give the Internet the characteristics of an economy as well as those of a computer.

To date, the TCS community's work on "algorithmic mechanism design" has focused on "truthful" mechanisms. The overall approach, which is consistent with the approach in the economics literature, is to design mechanisms that are "incentive-compatible" in the technical sense that strategic agents cannot improve their welfare by lying about their private inputs. The well known Revelation Principle ensures that, if there is a mechanism that achieves a given economic design goal, then there is a truthful mechanism that achieves the same goal. The premise of this overall approach is that agents will voluntarily reveal their private information if it can be proven that lying does them no good in the situation addressed by this particular mechanism-design exercise.

We question this premise. In this talk, we will first explain why direct-revelation mechanisms may be unacceptable. Next, we will examine in detail the extent to which the theory of secure, multiparty function evaluation, as it has evolved in the cryptographic research community, can be applied in the domain of algorithmic mechanism design.

Title: Reusable Time-Lines

While probably the most important pillar of cryptography is the believed existence of hard problems, the notion of {\em moderately hard} problems also bears promise. A moderately hard problem is one which is not computationally infeasible to solve, but also not easy, meaning that a solution can be obtained after a certain - verifiable - amount of work. One such candidate problem is modular exponentiation. Indeed, modular exponentiation has been the basis for recent work in timed-release cryptography, including ``time-lock'' puzzles by Rivest, Shamir and Wagner, and timed commitments by Boneh and Naor.

In this work we build on the Boneh-Naor structure for timed commitments, which we call a ``time-line.'' In a nutshell, a time-line is a vector of elements, where each element is obtained by iterated squaring of the previous element. We first introduce the notion of {\em derived} time-lines, which are time-lines that are obtained by ``shifting'' of a master time-line. While expensive proofs are needed to verify the correctness of a master time-line, a much simpler and less expensive verification of correct shifting can be used. As a result, existing applications using time-lines (including timed commitments, electronic contract signing, and concurrent zero-knowledge proofs) benefit from the efficiency gain.

Additionally, our derived time-line construction allows us to solve a problem not addressed previously: the timed release of {\em standard} digital signatures (RSA, DSS, Schnorr). Such signatures, once released, cannot be distinguished from signatures of the same type obtained without a timed release, making it transparent to an observer of the end result. We demonstrate how to achieve a transparent timed release of RSA signatures.

This is joint work with Markus Jakobsson.

Title: Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications

We describe efficient protocols for non-malleable (interactive) proofs of plaintext knowledge for the RSA, Rabin, Paillier, and El-Gamal encryption schemes whose security can be proven in the standard model. We also discuss applications of these protocols to: (1) chosen-ciphertext secure, interactive encryption; (2) password-based authentication and key exchange in the public-key model; and (3) deniable authentication. In each case, we show very practical solutions (where we ensure that our constructions are secure even when run in an asynchronous, concurrent environment) based on, e.g., the RSA or factoring assumptions.

Our techniques provide a general methodology for constructing efficient non-malleable proofs of knowledge when shared parameters are available (for our intended applications, these parameters are simply included as part of the already-required public keys). Thus, non-malleable proofs of knowledge are easy to achieve ``in practice''.

Title: Key Management for IPsec: Background and Challenges

IPsec is a protocol suite for providing security at the network layer. Because of the different scenarios in which it may be employed, considerable requirements in terms of flexibility and security are placed on the key negotiation and management protocol/component.

IKE (RFC 2409), the current standard, has a number of deficiencies. The three most important are the high number of protocol rounds, its vulnerability to denial-of-service attacks, and the complexity of its specification. While it may be possible to ``patch'' the protocol to fix some of these problems, we would prefer to replace IKE with something better. With that in mind, we set out to engineer a new key exchange protocol specifically for Internet security applications. With a view toward its possible role as a successor to IKE, we call our new protocol ``JFK,'' which stands for ``Just Fast Keying.''

In this talk, I will provide a quick survey of the IPsec protocols, with particular emphasis on the proposed and used key management protocols. I will then discuss problems with the current standard, and the proposed JFK and LBJ protocols.

Joint work with Bill Aiello, Steve Bellovin, Matt Blaze, Ran Canetti, John Ioannidis, and Omer Reingold.

Title: Securing Internet Sealed-Bid Auctions

The talk will give a survey of existing technologies for running Internet auctions. In addition to the survey we will describe the [NPS] architecture for executing protocols for sealed bid auctions and, more generally, mechanism design. This system enables to preserve the privacy of the inputs of the participants (so that no nonessential information about them is divulged, even a posteriori) while maintaining communication and computational efficiency. This goal is achieved by adding another party - the auction issuer - that generates the programs for computing the auctions but does not take an active part in the protocol. The auction issuer is not a trusted party, but is assumed not to collude with the auctioneer. In the case of auctions, barring collusion between the auctioneer and the auction issuer, neither party gains any information about the bids, even after the auction is over. Moreover, bidders can verify that the auction was performed correctly. The bidders in the protocol are only required to send their bid to the auctioneer, and the overall communication and computational efficiency are very reasonable.

Title: Exploring the Worlds Between Minicrypt and Cryptomania

We study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i.e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement, trapdoor functions, and trapdoor permutations. In spite of the importance of these primitives, only little was known about the relationships among them. We resolve all the missing relationships, with respect to black-box reductions. In particular, we show that public-key encryption and oblivious transfer are incomparable under black-box reductions. Furthermore, relative to black-box reductions, neither oblivious transfer nor 1:1 trapdoor functions imply trapdoor permutations. Finally, we show that there is no black-box reduction from trapdoor functions to public-key encryption. Our negative results follow the oracle separation paradigm introduced by Impagliazzo and Rudich, as well as a new related model of separation.

One way to interpret our results is as an indication that obtaining a simple and clean view of cryptography is even further beyond our reach than might have been previously suspected, as the picture of cryptography is not likely to simplify in some of its most central concepts. Borrowing from the terminology of Impagliazzo, our results demonstrate that there are many possible worlds that lie between Minicrypt (the world that has only one-way functions and primitives implied by them) and Cryptomania (the world that contains trapdoor permutations and the rich cryptographic possibilities that they offer).

This talk is mostly based on joint work with Y. Gertner, S. Kannan, T. Malkin, and M. Viswanathan (FOCS 2000), and with Y. Gertner and T. Malkin, (FOCS 2001).

Title: Tight Bounds for Shared Memory Systems Accessed by Byzantine Processes

We provide efficient constructions and strong lower bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine faults, in a model previously explored by Malkhi et al. (DISC 2000). We show that sticky bits are universal in the Byzantine failure model provided n is at least 3t+1, an improvement over the previous result requiring n to be at least (2t+1)(t+1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n > 3t. (This is the best possible bound on n for strong consensus.) We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects. Authors: Michael Merritt, Omer Reingold, Gadi Taubenfeld, and Rebecca Wright.