We deal with protocols that encourage participants to exchange information about their inputs for their mutual benefit. Our assumption is that the participants are rational and try to maximize their utility. Our goal is to design games and strategies where rational players do not have any incentive to deviate from the strategy.

We investigate the problem of rational secret sharing, where a dealer pre-distributed shares of a secret which can in turn be reconstructed by the participants at a later stage. In addition, we consider the more general problem of rational function evaluation, where the participants wish to evaluate a given function of their values. We call the above problems 'information exchanging'.

These tasks are two of the classical problems in foundations of cryptography, and have been intensively studied over the last three decades. However, their rational versions introduce new obstacles. One such obstacle is the behavior in the last round: if a participant knows that the current round is the last one, what is his incentive to send useful information?

We show that schemes for the above tasks where player values
come from a bounded (finite) domain *cannot* satisfy some of the
most desirable properties of such protocols. For instance, for
two parties no non-trivial exchange can have a Nash-equilibrium.
In contrast, we suggest protocols for rational secret sharing
where the values come from an unbounded domain, but with a finite
(and polynomial sized) expectation. The protocol is a strict Nash
equilibrium and it avoids the above mentioned problem of the last
round.

Postscript, gzipped Postscript, PDF. Slides: ppt.

- Gillat Kol and Moni Naor
, Abstract, Postscript, gzipped Postscript, PDF.*, Cryptography and Game Theory: Designing Protocols for Exchanging Information*

Back to: On-Line Publications, Recent Papers