Abstract
We consider the problem of fairness in two-party computation, where this means (informally) that both parties should learn the correct output. A seminal result of Cleve (STOC 1986) shows that fairness is, in general, impossible to achieve for malicious parties. Here, we treat the parties as rational and seek to understand what can be done.
Asharov et al. (Eurocrypt 2011) recently considered this problem and showed impossibility of rational fair computation for a particular function and a particular set of utilities. We observe, however, that in their setting the parties have no incentive to compute the function even in an ideal world where fairness is guaranteed. Revisiting the problem, we show that rational fair computation is possible, for arbitrary functions and utilities, as long as at least one of the parties has a strict incentive to compute the function in the ideal world. This gives a novel setting in which game-theoretic considerations can be used to circumvent an impossibility result in cryptography.
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: 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 53–62. ACM Press (2006)
Asharov, G., Canetti, R., Hazay, C.: Towards a Game Theoretic View of Secure Computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 426–445. Springer, Heidelberg (2011), Full version available at, http://eprint.iacr.org/2011/137
Asharov, G., Lindell, Y.: Utility dependence in correct and fair rational secret sharing. Journal of Cryptology 24(1), 157–202 (2011)
Barany, I.: Fair distribution protocols, or how the players replace fortune. Mathematics of Operations Research 17, 327–340 (1992)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Cleve, R.: Limits on the security of coin flips when half the processors are faulty. In: 18th Annual ACM Symposium on Theory of Computing (STOC), pp. 364–369. ACM Press (1986)
Crawford, V., Sobel, J.: Strategic information transmission. Econometrica 50, 1431–1451 (1982)
Dodis, Y., Halevi, S., Rabin, T.: A Cryptographic Solution to a Game Theoretic Problem. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 112–130. Springer, Heidelberg (2000)
Dodis, Y., Rabin, T.: Cryptography and game theory. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, pp. 181–207. Cambridge University Press (2007)
Forges, F.: Universal mechanisms. Econometrica 58, 1342–1364 (1990)
Fuchsbauer, G., Katz, J., Naccache, D.: Efficient Rational Secret Sharing in Standard Communication Networks. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 419–436. Springer, Heidelberg (2010)
Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM 58(6) (2011)
Gordon, S.D., Katz, J.: Rational Secret Sharing, Revisited. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 229–241. Springer, Heidelberg (2006)
Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation. Journal of Cryptology 25(1), 14–40 (2012)
Gradwohl, R.: Rationality in the Full-Information Model. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 401–418. Springer, Heidelberg (2010)
Gradwohl, R., Livne, N., Rosen, A.: Sequential rationality in cryptographic protocols. In: 51st FOCS Annual Symposium on Foundations of Computer Science (FOCS), pp. 623–632. IEEE (2010)
Halpern, J., Teague, V.: Rational secret sharing and multiparty computation. In: 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 623–632. ACM Press (2004)
Izmalkov, S., Lepinski, M., Micali, S.: Verifiably Secure Devices. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 273–301. Springer, Heidelberg (2008)
Izmalkov, S., Lepinski, M., Micali, S.: Perfect implementation. Games and Economic Behavior 71(1), 121–140 (2011), http://hdl.handle.net/1721.1/50634
Izmalkov, S., Micali, S., Lepinski, M.: Rational secure computation and ideal mechanism design. In: 46th FOCSAnnual Symposium on Foundations of Computer Science (FOCS), pp. 585–595. IEEE (2005), Full version available at, http://dspace.mit.edu/handle/1721.1/38208
Katz, J.: Bridging Game Theory and Cryptography: Recent Results and Future Directions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 251–272. Springer, Heidelberg (2008)
Kol, G., Naor, M.: Cryptography and Game Theory: Designing Protocols for Exchanging Information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320–339. Springer, Heidelberg (2008)
Kol, G., Naor, M.: Games for exchanging information. In: 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 423–432. ACM Press (2008)
Lepinski, M., Micali, S., Peikert, C., Shelat, A.: Completely fair SFE and coalition-safe cheap talk. In: 23rd ACM PODCAnnual ACM Symposium on Principles of Distributed Computing (PODC), pp. 1–10. ACM Press (2004)
Lepinski, M., Micali, S., Shelat, A.: Collusion-free protocols. In: 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 543–552. ACM Press (2005)
Lysyanskaya, A., Triandopoulos, N.: Rationality and Adversarial Behavior in Multi-party Computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 180–197. Springer, Heidelberg (2006)
Micali, S., Shelat, A.: Purely Rational Secret Sharing (Extended Abstract). In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 54–71. Springer, Heidelberg (2009)
Moran, T., Naor, M., Segev, G.: An Optimally Fair Coin Toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 1–18. Springer, Heidelberg (2009)
Ong, S.J., Parkes, D.C., Rosen, A., Vadhan, S.: Fairness with an Honest Minority and a Rational Majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 36–53. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Groce, A., Katz, J. (2012). Fair Computation with Rational Players. In: Pointcheval, D., Johansson, T. (eds) Advances in Cryptology – EUROCRYPT 2012. EUROCRYPT 2012. Lecture Notes in Computer Science, vol 7237. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29011-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-29011-4_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29010-7
Online ISBN: 978-3-642-29011-4
eBook Packages: Computer ScienceComputer Science (R0)