Distributed Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty Computation

Joseph Halpern

Cornell University

Traditionally, work on secret sharing and multiparty function computation in the cryptography community, just like work in distributed computation, has divided the agents into "good guys" and "bad guys". The good guys follow the protocol; the bad guys do everything in their power to make sure it does not work. By way of contrast, game theory has focused on ``rational'' agents, who try to maximize their utilities. Here I try to combine these viewpoints, focusing on two key problems in cyrptography: secret sharing and multiparty computation. 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. Vanessa Teague and I showed that (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 proved analogous results for multiparty computation: the problem of computing some function of individual agents' inputs without revealing any information about the inputs. More recently, Ittai Abraham, Danny Dolev, and Rica Gonen, and I considered what happens if we allow not just one agent to defect (as is the case in Nash equilibrium) but we allow up to k agents to defect. We showed that such k-resilient Nash equilibria exist for secret sharing and multiparty computation. We further extended these results so that they hold even in the presence for up to t players with "unexpected" utilities, who might not act the way you expect. (These players can be viewed as "faulty".) Finally, we show that our techniques can be used to simulate games with mediators by games without mediators. The talk is self-contained. No background in game theory or distributed computing will be assumed.

Bio: Joseph Y. Halpern received a B.Sc. in mathematics from the
University of Toronto in 1975 and a Ph.D. in mathematics from Harvard
in 1981.  In between, he spent two years as the head of the
Mathematics Department at Bawku Secondary School, in Ghana.  After a
year as a visiting scientist at MIT, he joined the IBM Almaden
Research Center in 1982, where he remained until 1996. He served as
manager of the Mathematics and Related Computer Science Department at
IBM from 1988-1990 and was a consulting professor at Stanford from
1984-1996.  In 1996, he moved to Cornell University, where he is a
professor in Computer Science.

His major research interests are in reasoning about knowledge and
uncertainty, qualitative reasoning, causality, belief revision,
(fault-tolerant) distributed computation, game theory, decision
theory, and security.  Together with his former student, Yoram Moses,
he pioneered the approach of applying reasoning about knowledge to
analyzing distributed protocols and multi-agent systems.  He has
coauthored 5 patents, two books ("Reasoning About Knowledge" and
"Reasoning about Uncertainty"), and well over 100 journal publications
and 100 conference publications.  He was designated Highly Cited
Researcher by the Institute for Scientific Information.

Halpern was program chair and organizer of the first conference on
Theoretical Aspects of Reasoning about Knowledge, and program chair of
the 5th ACM Symposium on Principles of Distributed Computing, the 23rd
ACM Symposium on Theory of Computing, and the 16th IEEE Symposium on
Logic in Computer Science.  He received the Publishers' Prize for Best
Paper at at the International Joint Conference on Artificial
Intelligence in 1985 (joint with Ronald Fagin) and in 1989, the 1997
Godel Prize (joint with Yoram Moses), and two IBM Outstanding
Innovation Awards.  He is a Fellow of AAAI (American Association of
Artificial Intelligence), AAAS (American Association for the
Advancement of Science), and ACM (Association for Computing
Machinery), and in 2001-02 was the recipient of a Guggenheim and a
Fulbright Fellowship. He was editor-in-chief of Journal of the ACM,
and currently serves on the editorial board of Journal of Logic and
Computation, Games and Economic Behavior, and Artificial Intelligence.

Deepak Ramachandran

Last modified: Mon Mar 27 11:38:17 CST 2006