Completely fair SFE and coalition-safe cheap talk

ABSTRACT

Secure function evaluation (SFE) enables a group of players, by themselves, to evaluate a function on private inputs as securely as if a trusted third party had done it for them. A completely fair SFE is a protocol in which, conceptually, the function values are learned atomically.We provide a completely fair SFE protocol which is secure for any number of malicious players, using a novel combination of computational and physical channel assumptions.We also show how completely fair SFE has striking applications togame theory. In particular, it enables "cheap-talk" protocol that

1. (a) achieve correlated-equilibrium payoffs in any game,
2. (b) are the first protocols which provably give no additional power to any coalition of players, and
3. (c) are exponentially more efficient than prior counterparts.

REFERENCES

• 1: R. Aumann. Subjectivity and correlation in randomized strategies. J. Math. Econ., 1:67--96, 1974.
• 2: Imre Bárány, Fair distribution protocols or how the players replace fortune, Mathematics of Operations Research, v.17 n.2, p.327-340, May 1992 [doi>10.1287/moor.17.2.327]
• 3: Michael Ben-Or , Oded Goldreich , Shafi Goldwasser , Johan Håstad , Joe Kilian , Silvio Micali , Phillip Rogaway, Everything Provable is Provable in Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.37-56, August 21-25, 1988
• 4: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 5: E. Ben-Porath. Correlation without mediation: Expanding the set of equilibria outcomes by "cheap" pre-play procedures. Journal of Economic Theory, 80:108--122, 1998.
• 6: M. Blum. Three Applications of the Oblivious Transfer: Part I: Coin Flipping by the telephone; Part II: How to Exchange Secrets; Part III: How to Send Certified Electronic Mail. University of California, Berkeley, 1981.
• 7: Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
• 8: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 9: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 10: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 11: R Cleve, Limits on the security of coin flips when half the processors are faulty, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.364-369, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12168]
• 12: Yevgeniy Dodis , Shai Halevi , Tal Rabin, A Cryptographic Solution to a Game Theoretic Problem, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.112-130, August 20-24, 2000
• 13: Yevgeniy Dodis , Silvio Micali, Parallel Reducibility for Information-Theoretically Secure Computation, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.74-92, August 20-24, 2000
• 14: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 15: P. Feldman and S. Micali. Byzantine agreement in constant expected time (and trusting no one). In Proc. 26th FOCS, pages 267--276. IEEE Computer Society, 1985.
• 16: J. A. Garay, P. MacKenzie, and K. Yang. Efficient and secure multi-party computation with faulty majority and complete fairness. Technical Report 9, Eprint, January 2004. http://eprint.iacr.org/2004/009.
• 17: D. Gerardi. Unmediated communication in games with complete and incomplete information. Journal of Economic Theory, to appear.
• 18: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 19: Shafi Goldwasser , Leonid A. Levin, Fair Computation of General Functions in Presence of Immoral Majority, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.77-93, August 11-15, 1990
• 20: M. Luby, S. Micali, and C. Rackoff. How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In FOCS, pages 11--21, 1983.
• 21: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 22: D. Moreno and J. Wooders. Coalition-proof equilibrium. Games and Economic Behavior, 17:80--112, 1996.
• 23: H. Moulin and J. P. Vial. Strategically zero sum games. Internat. J. Game Theory, 7:201--221, 1978.
• 24: J. Nash. Non-cooperative games. Annals of Mathematics, 54:286--295, 1951.
• 25: 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, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 26: I. Ray. Coalition-proof correlated equilibrium: A definition. Games and Economic Behavior, 17:56--79, 1996.
• 27: V. Teague. Selecting correlated random actions. In Proc. Financial Cryptography, 2004.
• 28: A. Urbano and J. E. Vila. Computational complexity and communication: Coordination in two-player games. Econometrica, 70(5):1893--1927, 2002.
• 29: A. C.-C. Yao. How to generate and exchange secrets. In Proc. 27th FOCS, pages 162--167. IEEE Computer Society, 1986.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Economics, Security, Theory

Keywords:
correlated equilibrium, game theory, mechanism design, secure function evaluation