O. Goldreich
S. Micali
A. Wigderson
ABSTRACT
We present a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest.
Our algorithm automatically solves all the multi-party protocol problems addressed in complexity-based cryptography during the last 10 years. It actually is a completeness theorem for the class of distributed protocols with honest majority. Such completeness theorem is optimal in the sense that, if the majority of the players is not honest, some protocol problems have no efficient solution [C].
- Ba.D. Barrington , Bounded-Width Branehin9 Programs Recognize Exactly Those Languages in NC~, Proc. 18th STOC, 1986 pp 1-5 Google Scholar
Digital Library
- Bl.M. Blum, Coin Flipping by Telephone, IEEE COMPCON 1982, pp. 133-137.Google Scholar
- BH.R. Boppana and R. Hirschfeld, Pseudo-Random Generatoro and Complexity Clauses, To appear in Randomness and Computation, 5th volume of Advances in Computing Research, ed. S. MicaliGoogle Scholar
- BM.M. Blum and S. Micali, How To Generate Sequences Of C~ptographically Strong Pseudo- Random Bits, SiAM J. on Computing, Vol. 13, Nov 1984, pp. 850-864 Google ScholarDigital Library
- CG.B. Chor and O. Goldreich, RSA/Rabi, Bits Are 1/2 4- 1/poly(log N) Seeure, To appear SIAM J. on Computing. Earlier version in Proc. FOCS 1984, pp. 449- 463Google Scholar
- CGMA.B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch, Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults', Proc. 26th FOCS, 1985, pp. 383-395Google ScholarDigital Library
- EGL.S. Even, O. Goldreich, and A. Lempel, A Randomized Protoeol for Signing Contraets, CACM, vol. 28, No. 6, 1985, pp. 637-647 Google ScholarDigital Library
- FMRW.M.Fiseher, S. Mieali, C. Raekoff and D. Witenberg, A Secure Protocol for the Oblivious Transfer, In preperation 1986.Google Scholar
- GM.S. Goldwa~ser, and S. Micali, Probabilisti~ Eneryption, JCSS Vol. 28, No. 2, April 1984. An earlier version (containing other results) was tiffed Probabilistic Encryption and How to Play Mental Poker Hideing All Partial Information,Google Scholar
- GMR.g. Goldwasser, S. Micali and C. Rackoff, 7he Knowledge Complexity of Interaetive Proof- Systems, To appear SIAM J. on Computing (manuscript available from authors). Earlier version in Proc. 17th Annual ACM Symp. on Theory of Computing, pp 291-304. Google ScholarDigital Library
- GoMiRi.S. Goldwasser, S. Micali, and R. Rivest, A Digital Signature Scheme Secure Against Adaptive, Chosen Gyphertext Attack To appear in SIAM J. on Computing (available from authors) Earlier version, titled 'A Paradoxical Solution to The Signature Problem, in Proc. 25th FOCS, 1984, pp. 441-448Google Scholar
- GMW.O. Goldreich, S. Micali and A. Wigderson, Proofs that Yield Nothing but their Validity and a Methodology of U~ptographie Design, Proe. of FOCS 1986.Google Scholar
- HR.J. Halpern and M.O. Rabin, A Logic to reaaon about likehood, Proc. of 15th STOC, 1983. Google ScholarDigital Library
- L.L. Leonid, One-Wa3t Functions and PseudO- Random Generators, Proc. 17th STOC, 1985, pp. 363-365 Google ScholarDigital Library
- Y.A.Yao, Theory and Application of Trapdoor Functions, Proc. of 23rd FOCS, IEEE, Nov., ~982, pp 80-9t. Google ScholarCross Ref
- Y2.A.Yao, How to Generate and Exchang~ Secrets, Proc. 27th STOC, 1986, pp. 162-167Google Scholar
Index Terms
- How to play ANY mental game
Recommendations
The (s, t)-Wythoff's Game under Misère Play Convention
CSO '12: Proceedings of the 2012 Fifth International Joint Conference on Computational Sciences and OptimizationA.S. Fraenkel introduces a new (s, t)-Wythoff's game which is the generalization of both a-Wythoff's game and Wythoff's game. Fraenkel determines all P-positions of (s, t)-Wythoff's game under normal play convention. In this paper, the (s, t)-Wythoff's ...
Sensing game play. Exploring computer game play in a game café and a mass LAN party
CGAMES '11: Proceedings of the 2011 16th International Conference on Computer GamesIn this article we discuss the sensory experiences of playing computer games by exploring the sight, the sound, the taste, smell, and touch of games. We reflect on how senses and the social atmosphere gives meaning to players' experiences of playing ...
Robust game play against unknown opponents
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systemsA standard assumption of search in two-player games is that the opponent has the same evaluation function or utility for possible game outcomes. While some work has been done to try to better exploit weak opponents, it has only been a minor component of ...
Comments