Abstract
In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payo.s can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payo.s o.ered by mediator-assisted strategies. We answer this question a.rmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game.
The main building block of our solution is an e.cient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a 1, b 1)... (a n , b n ) (possibly with repetitions), and they want to pick a random index i such that Alice learns only a i and Bob learns only b i . Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Abe. Universally Verifiable Mix-net with Verification Work Independent on the number of Mix-centers. In Proceedings of EUROCRYPT’ 98, pp. 437–447, 1998.
R. Aumann. Subjectivity and Correlation in Randomized Strategies. In Journal of Mathematical Economics, 1, pp. 67–95, 1974
I. Barany. Fair distribution protocols or how the players replace fortune. Mathematics of Operations Research, 17(2):327–340, May 1992.
M. Bellare, R. Impagliazzo, and M. Naor. Does parallel repetition lower the error in computationally sound protocols? In 38th Annual Symposium on Foundations of Computer Science, pages 374–383. IEEE, 1997.
J. Benaloh. Dense Probabilistic Encryption. In Proc. of the Workshop on Selected Areas in Cryptography, pp. 120–128, 1994.
M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 1–10, 1988.
M. Blum. Coin flipping by telephone: A protocol for solving impossible problems. In CRYPTO’ 81 ECE Report 82-04, ECE Dept., UCSB, 1982.
G. Brassard, D. Chaum, and C. Crépeau. Minimum disclosure proofs of knowledge. JCSS, 37(2):156–189, 1988.
R. Canetti, Security and Composition of Multi-parti Cryptographic Protocols. Journal of Cryptology, 13(1):143–202.
D. Chaum. Blind signatures for untraceable payment. In Advances in Cryptology-CRYPTO’ 82, pages 199–203. Plenum Press, 1982.
D. Chaum, C. Crépeau, and E. Damgård. Multiparty unconditionally secure protocols. In Advances in Cryptology-CRYPTO’ 87, volume 293 of 99 Lecture Notes in Computer Science, pages 462–462. Springer-Verlag, 1988.
R. Cramer, I. Damgard, and P. MacKenzie. Efficient zero-knowledge proofs of knowledge without intractability assumptions. Proceedings of PKC 2000 January 2000, Melbourne, Australia.
Y. Dodis and S. Halevi and T. Rabin. Cryptographic Solutions to a Game Theoretic Problem. http://www.research.ibm.com/security/DHR00.ps.
C. Dwork, M. Naor, and A. Sahai. Concurrent zero knowledge. In Proceedings of the 30th Annual ACM STOC, pages 409–418. ACM Press, 1998.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In CRYPTO’ 84, LNCS 196, pages 10–18. Springer-Verlag, 1985.
U. Feige and A. Shamir. Witness indistinguishable and witness hiding protocols. In Proceedings of the 22nd Annual ACM STOC, pages 416–426. ACM Press, 1990.
M. Fischer, R. Wright. An Application of Game-Theoretic Techniques to Cryptography. In Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 99–118, 1993.
F. Forges. Can sunspots repalce the mediator? In J. of Math. Economics, 17:347–368, 1988.
F. Forges. Universal Mechanisms, In Econometrica, 58:1341–1364, 1990.
D. Fudenberg, J. Tirole. Game Theory. MIT Press, 1992.
J. Garay, R. Gennaro, C. Jutla, and T. Rabin. Secure distributed storage and retrieval. In Proc. 11th International Workshop on Distributed Algorithms (WDAG’ 97), LNCS 1320, pages 275–289. Springer-Verlag, 1997.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 218–229, 1987.
S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, April 1984.
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, 1989.
M. Jakobsson. A Practical Mix. In Proceedings of EUROCRYPT’ 98, pp. 448–461, 1998.
J. Kilian. (More) Completeness Theorems for Secure Two-Party Computation In Proc. of STOC, 2000.
E. Lehrer and S. Sorin. One-shot public mediated talk. Discussion Paper 1108, Northwestern University, 1994.
P. MacKenzie. Efficient ZK Proofs of Knowledge. Unpublished manuscript, 1998.
G. Mailath, L. Samuelson and A. Shaked. Correlated Equilibria and Local Interaction In Economic Theory, 9, pp. 551–556, 1997.
R. Myerson. Communication, correlated equilibria and incentive compatibility. In Handbook of Game Theory, Vol. II, Elsevier, Amsterdam, pp. 827–847, 1994.
J.F. Nash. Non-Cooperative Games. Annals of Mathematics, 54 pages 286–295.
M. Osborne, A. Rubinstein. A Course in Game Theory. The MIT Press, 1994.
T. Sander, A. Young, and M. Yung. Non-interactive CryptoComputing for NC1. In 40th Annual Symposium on Foundations of Computer Science, pages 554–567. IEEE, 1999.
A. C. Yao. Protocols for secure computations (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 160–164. IEEE, Nov. 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dodis, Y., Halevi, S., Rabin, T. (2000). A Cryptographic Solution to a Game Theoretic Problem. In: Bellare, M. (eds) Advances in Cryptology — CRYPTO 2000. CRYPTO 2000. Lecture Notes in Computer Science, vol 1880. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44598-6_7
Download citation
DOI: https://doi.org/10.1007/3-540-44598-6_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67907-3
Online ISBN: 978-3-540-44598-2
eBook Packages: Springer Book Archive