Rational secret sharing and multiparty computation: extended abstract

ABSTRACT

We consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as possible of the other agents get it. We show that, under these assumptions, neither secret sharing nor multiparty function computation is possible using a mechanism that has a fixed running time. However, we show that both are possible using randomized mechanisms with constant expected running time.

REFERENCES

• 1: 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]
• 2: Manuel Blum, How to exchange (secret) keys, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.175-193, May 1983 [doi>10.1145/357360.357368]
• 3: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 4: A. Brandenburger and J. Keisler. Epistemic conditions for iterated admissibility. Unpublished manuscript; first version 6/16/00, latest draft 6/9/03., 2000.
• 5: R. Canetti. Studies in Secure Multiparty Computation and Applications. PhD thesis, Technion, 1996.
• 6: 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]
• 7: Richard Cleve, Controlled gradual disclosure schemes for random bits and their applications, Proceedings on Advances in cryptology, p.573-588, July 1989, Santa Barbara, California, United States
• 8: I. Damgard. Practical and provably secure release of a secret and exchange of signatures. Journal of Cryptology, 8(4):201--222, 1995.
• 9: 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]
• 10: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 11: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 12: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 13: 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]
• 14: M. Luby, S. Micali, and C. Rackoff. How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin. In Proc. 24th IEEE Symp. on Foundations of Computer Science, pages 11--21, 1983.
• 15: R. McGrew, R. Porter, and Y. Shoham. Towards infomational mechanism design: A new perspective on secure function evaluation. Unpublished manuscript.
• 16: Robert McGrew , Ryan Porter , Yoav Shoham, Towards a general theory of non-cooperative computation, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846249]
• 17: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, Cambridge, Mass., 1994.
• 18: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 19: Y. Shoham and M. Tennenholtz. Non-cooperative computing: Boolean functions with correctness and exclusivity. Theoretical Computer Science, 2004. To appear. Also available at iew3.technion.ac.il/~moshet/NCC-TCS.pdf.
• 20: A. Yao. Protocols for secure computation (extended abstract). In Proc. 23rd IEEE Symp. on Foundations of Computer Science, pages 160--164, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Economics, Theory

Keywords:
game theory, iterated deletion of weakly dominated strategies, multiparty computation, non-cooperative computing, secret sharing