Noam Livne (Weizmann Institute of Science)
Wednesday, 29.12.2010, 12:20
Much ofMuch 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.