UNIVERSITY OF PENNSYLVANIA

Department of Mathematics

Fall 2005 - Hans Rademacher Lectures in Mathematics

Silvio Micali
Department of Electrical Engineering & Computer Science and
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology




will deliver four lectures on

FROM TRUST TO REASON

Trusted parties are routinely relied upon to guarantee the privacy and correctness of many real-world transactions among mutually suspicious agents. In this cycle of lectures we shall explore the extent to which trusted parties can be replaced by further interaction among the agents alone. Our exploration will move from very practical examples (where trusted parties have a minimal role) to a new theory of Rationality, Privacy, and Correctness (where trusted parties no longer appear).

Fair Electronic Exchange
Monday....October 17, 2005....4:30pm
Assume each of two parties has something the other wants. Then, a fair exchange is an electronic protocol guaranteeing that either both parties get what they want, or none of them does. Fair exchange can be trivially accomplished by protocols relying on traditional trusted parties, but such protocols are INEFFICIENT (because a trusted party must be part of every execution) and EXPENSIVE (because trusted parties want to be paid for each execution).

We shall demonstrate how recent advances in cryptographic primitives yield protocols for certified e-mail and contract signing of surprising simplicity, efficiency and security. Our protocols are OPTIMISTIC, that is, they rely on a trusted party that (1) does not participate at all in an honest execution, and yet (2) guarantees the fairness of all executions.

Rational Secure Computation and Ideal Mechanism Design I
Tuesday....October 18, 2005.....3:00pm
We put forward and implement Rational Secure Computation, a stronger notion of secure computation that does not depend on players' honesty, but solely on their rationality. Our new notion has broad implications for Mechanism Design. In particular, it enables Modular Mechanism Design.

Key to our result is showing that the ballot box---the venerable device used throughout the world to privately and correctly compute the tally of secret votes---can actually be used to securely compute ANY function of secret inputs.

(Joint work with Sergei Izmalkov and Matt Lepinski)

Rational Secure Computation and Ideal Mechanism Design II
Tuesday....October 18, 2005....4:30pm

We put forward and implement Rational Secure Computation, a stronger notion of secure computation that does not depend on players' honesty, but solely on their rationality. Our new notion has broad implications for Mechanism Design. In particular, it enables Modular Mechanism Design.

Key to our result is showing that the ballot box---the venerable device used throughout the world to privately and correctly compute the tally of secret votes---can actually be used to securely compute ANY function of secret inputs.

(Joint work with Sergei Izmalkov and Matt Lepinski)

Collusion-Free Protocols
Wednesday....October 19, 2005....4:30pm

Secure protocols minimize the injuries to privacy and correctness inflicted by coalitions of malicious participants, but do NOT prevent them from coordinating their actions during run time!

We put forward the notion of a collusion-free protocol and show that, under standard computational and physical assumptions, such protocols exist for Poker, Bridge, and all games with (partial information but) public actions.

A key step of our solution is making steganography ---i.e., subliminal communication via "innocuous" public messages--- provably impossible.

(Joint work with Matt Lepinski and Abhi Shelat)



The lectures on Monday and Tuesday will be held in room A-8, and
the lectures on Wednesday will be held in A-6 of the David Rittenhouse Laboratory,
S.E. corner of 33rd and Walnut Streets, Philadelphia, PA.

Tea: 4E17 David Rittenhouse Laboratory at 4PM.

For further information, please call the Department of Mathematics at the University of Pennsylvania - 215-898-8627.

Previous Rademacher Lecturers