## 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.

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. Rational Secure Computation and Ideal Mechanism Design I

Tuesday....October 18, 2005.....3:00pmKey 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:30pmWe 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)

Previous Rademacher Lecturers

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.