Cryptography and Game Theory: Designing Protocols for Exchanging Information

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.