Cryptography and game theory: Designing protocols for exchanging information

Gillat Kol, Moni Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

142 Scopus citations


The goal of this paper is finding fair protocols for the secret sharing and secure multiparty computation (SMPC) problems, when players are assumed to be rational. It was observed by Halpern and Teague (STOC 2004) that protocols with bounded number of iterations are susceptible to backward induction and cannot be considered rational. Previously suggested cryptographic solutions all share the property of having an essential exponential upper bound on their running time, and hence they are also susceptible to backward induction. Although it seems that this bound is an inherent property of every cryptography based solution, we show that this is not the case. We suggest coalition-resilient secret sharing and SMPC protocols with the property that after any sequence of iterations it is still a computational best response to follow them. Therefore, the protocols can be run any number of iterations, and are immune to backward induction. The mean of communication assumed is a broadcast channel, and we consider both the simultaneous and non-simultaneous cases.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - Fifth Theory of Cryptography Conference, TCC 2008, Proceedings
Number of pages20
StatePublished - 2008
Externally publishedYes
Event5th Theory of Cryptography Conference, TCC 2008 - New York, United States
Duration: Mar 19 2008Mar 21 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4948 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Theory of Cryptography Conference, TCC 2008
Country/TerritoryUnited States
CityNew York

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Cryptography and game theory: Designing protocols for exchanging information'. Together they form a unique fingerprint.

Cite this