Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation
作者： Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern
关键词: Game theory 、 Computer science 、 Nash equilibrium 、 Theoretical computer science 、 Computation 、 Best response 、 Secret sharing 、 Distributed computing 、 Secure multi-party computation 、 Rational agent
摘要: We study k-resilient Nash equilibria, joint strategies where no member of a coalition C size up to k can do better, even if the whole defects. show that such equilibria exist for secret sharing and multiparty computation, provided players prefer get information than not it. Our results hold there are only 2 players, so we computation with two rational agents. extend our they in presence t "unexpected" utilities. Finally, techniques be used simulate games mediators by without mediators.
acm.org
tu-berlin.de 参考文章(26)
Noam Nisan, Benny Pinkas, Yaron Sella, Dahlia Malkhi, Fairplay—a secure two-party computation system usenix security symposium. pp. 20- 20 ,(2004)
Anna Lysyanskaya, Nikos Triandopoulos, Rationality and Adversarial Behavior in Multi-party Computation Lecture Notes in Computer Science. pp. 180- 197 ,(2006) , 10.1007/11818175_11
Oded Goldreich, Foundations of Cryptography Cambridge University Press. ,(2001) , 10.1017/CBO9780511546891
T. Rabin, M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 73- 85 ,(1989) , 10.1145/73007.73014
J. Justesen, On the complexity of decoding Reed-Solomon codes (Corresp.) IEEE Transactions on Information Theory. ,vol. 22, pp. 237- 238 ,(1976) , 10.1109/TIT.1976.1055516
Gil Neiger, Sam Toueg, Automatically increasing the fault-tolerance of distributed algorithms Journal of Algorithms. ,vol. 11, pp. 374- 419 ,(1990) , 10.1016/0196-6774(90)90019-B
Elchanan Ben-Porath, Cheap talk in games with incomplete information Journal of Economic Theory. ,vol. 108, pp. 45- 71 ,(2003) , 10.1016/S0022-0531(02)00011-X
B.Douglas Bernheim, Bezalel Peleg, Michael D Whinston, Coalition-Proof Nash Equilibria I. Concepts Journal of Economic Theory. ,vol. 42, pp. 1- 12 ,(1987) , 10.1016/0022-0531(87)90099-8
Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation symposium on the theory of computing. pp. 1- 10 ,(1988) , 10.1145/62212.62213
Goldreich Oded, Foundations of Cryptography: Volume 2, Basic Applications ,(2004)