TY - GEN
T1 - Cryptography and game theory
T2 - 5th Theory of Cryptography Conference, TCC 2008
AU - Kol, Gillat
AU - Naor, Moni
N1 - Funding Information:
Research supported by a grant from the Israel Science Foundation.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=40249088241&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=40249088241&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-78524-8_18
DO - 10.1007/978-3-540-78524-8_18
M3 - Conference contribution
AN - SCOPUS:40249088241
SN - 354078523X
SN - 9783540785231
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 320
EP - 339
BT - Theory of Cryptography - Fifth Theory of Cryptography Conference, TCC 2008, Proceedings
Y2 - 19 March 2008 through 21 March 2008
ER -