Manuel Blum
Abstract
Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes . . . I'm flipping the coin. . . . You lost!"Coin-flipping in the SPECIAL way done here has a serious purpose. Indeed, it should prove an INDISPENSABLE TOOL of the protocol designer. Whenever a protocol requires one of two adversaries, say Alice, to pick a sequence of bits at random, and whenever it serves Alice's interests best NOT to pick her sequence of bits at random, then coin-flipping (Bob flipping coins to Alice) as defined here achieves the desired goal:1. It GUARANTEES to Bob that Alice will pick her sequence of bits at random. Her bit is 1 if Bob flips heads to her, O otherwise.2. It GUARANTEES to Alice that Bob will not know WHAT sequence of bits he flipped to her.Coin-flipping has already proved useful in solving a number of problems once thought impossible: mental poker, certified mail, and exchange of secrets. It will certainly prove a useful tool in solving other problems as well.
- {A'78} D. Angluin, "The Complexity of Some Problems in Number Theory," Lecture Notes available from author, Dept. of Comp. Science, Yale U. (1978).Google Scholar
- {B'81} M. Blum, "How to Exchange (Secret) Keys," to appear.Google Scholar
- {BM'81} M. Blum and S. Micali, "Coin-Flipping into a Well," to appear.Google Scholar
- {BR'81} M. Blum and M. O. Rabin, "Mail Certification by Randomization," to appear.Google Scholar
- {DH'79} W. Diffie and M. E. Hellman, "Privacy and Authentication: An Introduction to Cryptography," Proc. IEEE, vol. 67 no. 3 (March 1979), 397--427.Google ScholarCross Ref
- {L'77} W. J. LeVeque, "Fundamentals of Number Theory," Addison-Wesley Pub., 1977.Google Scholar
- {M'76} G. L. Miller, "Riemann's Hypothesis and a Test for Primality," J. Comput. and System Sci. vol. 13 (1976), 300--317.Google ScholarDigital Library
- {MG'81} S. Micali and S. Goldwasser, "Mental Poker Without Commutative Locks," to appear.Google Scholar
- {R'79} M. O. Rabin, "Digital Signatures and Public Key Systems as Intractable as Factorization," MIT LCS TM 1979. Google ScholarDigital Library
- {R'80} M. O. Rabin, "Probabilistic Algorithm for Testing Primality," J. Number Theory, vol. 12 (1980), 128--138.Google ScholarCross Ref
- {RSA'78} R. L. Rivest, A. Shamir, and L. L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Commun. ACM, vol. 21 (1978), 120--126. Google ScholarDigital Library
- {SRA'78} A. Shamir, R. L. Rivest, and L. M. Adleman, "Mental Poker," in The Mathematical Gardner, ed. D. A. Klarner, pub. by Wadsworth Intrntl (1981), 37--43.Google Scholar
- {SS'77} R. Solovay and V. Strassen, "A Fast Monte-Carlo Test for Primality," SIAM J. Comput. vol. 6 (1977), 84--85.Google ScholarDigital Library
Index Terms
- Coin flipping by telephone a protocol for solving impossible problems
Recommendations
An almost-optimally fair three-party coin-flipping protocol
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computingIn a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [STOC 1986] has shown that in the case of dishonest majority (i.e., at least half of the ...
Fair coin flipping: tighter analysis and the many-party case
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsIn a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be ...
An Almost-Optimally Fair Three-Party Coin-Flipping Protocol
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, ...
Comments