CS 789 THEORY SEMINAR [home]

Speaker:    Joe Halpern
Affiliation: Cornell University
Date:         April 5, 2004
Title:         Rational Secret Sharing and Multiparty Computation

Abstract:

Secret sharing is one of the main building blocks of modern-day cryptography.  Roughly speaking, m out of n secret sharing allows someone to give "shares" of a secret to n other players so that any m of them can reconstruct the secret. Implicitly, we are assuming that there are m "good" agents, who will cooperate, and n-m "bad" agents who may not. But what if instead we assume that all agents are rational:  they prefer getting the secret to not getting the secret but, secondarily, prefer that as few as possible of the other agents get it. In this case we show (1) there is no fixed-length secret-sharing protocol for rational agents that survives iterated deletion of weakly dominated strategies, and (2) there is a randomized protocol for secret sharing that survives iterated deletion, and runs in expected constant number of rounds. We then prove analogous results for multiparty computation:  the problem of computing some function of individual agents' inputs without revealing any information about the inputs.  This is joint work with Vanessa Teague. No prior knowledge of secret sharing, multiparty computation, or game theory will be assumed.