Abstract
Motivated by the desire to develop more realistic models of, and protocols for, interactions between mutually distrusting parties, there has recently been significant interest in combining the approaches and techniques of game theory with those of cryptographic protocol design. Broadly speaking, two directions are currently being pursued:
Applying cryptography to game theory: Certain game-theoretic equilibria are achievable if a trusted mediator is available. The question here is: to what extent can this mediator be replaced by a distributed cryptographic protocol run by the parties themselves?
Applying game-theory to cryptography: Traditional cryptographic models assume some honest parties who faithfully follow the protocol, and some arbitrarily malicious players against whom the honest players must be protected. Game-theoretic models propose instead that all players are simply self-interested (i.e., rational), and the question then is: how can we model and design meaningful protocols for such a setting?
In addition to surveying known results in each of the above areas, I suggest some new definitions along with avenues for future research.
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
Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In: Proc. 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 53–62. ACM Press, New York (2006)
Abraham, I., Dolev, D., Halpern, J.: Lower bounds on implementing robust and resilient mediators. In: 5th Theory of Cryptography Conference (TCC) (2008), http://arxiv.org/abs/0704.3646
Aumann, R.: Subjectivity and correlation in randomized strategies. J. Mathematical Economics 1, 67–96 (1974)
Aumann, R., Hart, S.: Long cheap talk. Econometrica 71(6), 1619–1660 (2003)
Aumann, Y., Lindell, Y.: Security against covert adversaries: Efficient protocols for realistic adversaries. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, Springer, Heidelberg (2007)
Barany, I.: Fair distribution protocols or how the players replace fortune. Mathematics of Operations Research 17(2), 327–340 (1992)
Beaver, D.: Multiparty protocols tolerating half faulty processors. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 560–572. Springer, Heidelberg (1990)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: 20th ACM Symposium on Theory of Computing (STOC), pp. 1–10 (1988)
Ben-Porath, E.: Cheap talk in games with incomplete information. J. Economic Theory 108(1), 45–71 (2003)
Buttyán, L., Hubaux, J.-P.: Security and Cooperation in Wireless Networks. Cambridge University Press, Cambridge (2007)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: 20th ACM Symposium on Theory of Computing, pp. 11–19 (1988)
Cleve, R.: Controlled gradual disclosure schemes for random bits and their applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, Springer, Heidelberg (1990)
Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: 18th ACM Symposium on Theory of Computing (STOC), pp. 364–369 (1986)
Crawford, V., Sobel, J.: Strategic information transmission. Econometrica 50(6), 1431–1451 (1982)
Dodis, Y., Halevi, S., Rabin, T.: A cryptographic solution to a game theoretic problem. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, Springer, Heidelberg (2006)
Dodis, Y., Rabin, T.: Cryptography and game theory. In: Nisan, et al. [38]
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Comm. ACM 28(6), 637–647 (1985)
Forges, F.: Universal mechanisms. Econometrica 58(6), 1341–1364 (1990)
Fudenberg, D., Tirole, J.: Game Theory. MIT Press, Cambridge (1991)
Goldreich, O.: Foundations of Cryptography, Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Goldwasser, S., Levin, L.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. Manuscript (2007)
Gordon, S.D., Katz, J.: Byzantine agreement with a rational adversary. In: Rump session presentation, Crypto (2006)
Gordon, S.D., Katz, J.: Rational secret sharing, revisited. In: Security and Cryptography for Networks (SCN), pp. 229–241 (2006)
Halpern, J.: Computer science and game theory: A brief survey. In: The New Palgrave Dictionary of Economics, 2nd edn. (2008), (Anticipated publication date: 2008) http://www.cs.cornell.edu/home/halpern/
Halpern, J., Teague, V.: Rational secret sharing and multiparty computation. In: 36th Annual ACM Symp. on Theory of Computing (STOC), pp. 623–632 (2004)
Izmalkov, S., Lepinski, M., Micali, S.: Rational secure computation and ideal mechanism design. In: IEEE Symposium on Foundations of Computer Science (FOCS), See also technical report MIT-CSAIL-TR-2007-040 (2005), http://hdl.handle.net/1721.1/38208
Izmalkov, S., Lepinski, M., Micali, S.: Verifiably secure devices. In: 5th Theory of Cryptography Conference (TCC) (2008)
Kol, G., Naor, M.: Cryptography and game theory: Designing protocols for exchanging information. In: 5th Theory of Cryptography Conference (TCC) (2008)
Lepinski, M., Micali, S., Peikert, C., Shelat, A.: Completely fair SFE and coalition-safe cheap talk. In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 1–10 (2004)
Lepinski, M., Micali, S., Shelat, A.: Collusion-free protocols. In: ACM Symposium on Theory of Computing (STOC) (2005)
Lindell, A.Y.: Legally-enforceable fairness in secure multiparty computation. In: CT-RSA (to appear 2008)
Linial, N.: Game-theoretic aspects of computer science. In: Aumann, R., Hart, S. (eds.) Handbook of Game Theory with Economic Applications, vol. 2, pp. 1340–1395. North-Holland, Amsterdam (1994)
Luby, M., Micali, S., Rackoff, C.: How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In: 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 11–21 (1983)
Lysyanskaya, A., Triandopoulos, N.: Rationality and adversarial behavior in multi-party computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, Springer, Heidelberg (2006)
Moulin, H., Vial, J.-P.: Strategically zero sum games. Intl. J. Game Theory 7(3/4), 201–221 (1978)
Nash, J.: Non-cooperative games. Annals of Mathematics 54(2), 286–295 (1951)
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Osborne, M., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (2004)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: 21st ACM Symp. on Theory of Computing, pp. 73–85 (1989)
Shoham, Y., Tennenholtz, M.: Non-cooperative computation: Boolean functions with correctness and exclusivity. Theoretical Comp. Sci. 343(1–2), 97–113 (2005)
Urbano, A., Villa, J.: Computational complexity and communication: Coordination in two-player games. Econometrica 70(5), 1893–1927 (2002)
Urbano, A., Villa, J.: Computationally restricted unmediated talk under incomplete information. Economic Theory 23(2), 283–320 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Katz, J. (2008). Bridging Game Theory and Cryptography: Recent Results and Future Directions. In: Canetti, R. (eds) Theory of Cryptography. TCC 2008. Lecture Notes in Computer Science, vol 4948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-78524-8_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78523-1
Online ISBN: 978-3-540-78524-8
eBook Packages: Computer ScienceComputer Science (R0)