Sequential rationality in cryptographic protocols

Ronen Gradwohl*, Noam Livne, Alon Rosen

*Corresponding author for this work

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

14 Scopus citations

Abstract

Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers. We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat-free Nash equilibrium that is more permissive but still eliminates the undesirable "empty threats" of non-sequential solution concepts. To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria (Dodis-Halevi-Rabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a non-trivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages623-632
Number of pages10
DOIs
StatePublished - Dec 1 2010
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

Keywords

  • Cryptography
  • Game theory

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Sequential rationality in cryptographic protocols'. Together they form a unique fingerprint.

Cite this