Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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.

REFERENCES

• 1: {A'78} D. Angluin, "The Complexity of Some Problems in Number Theory," Lecture Notes available from author, Dept. of Comp. Science, Yale U. (1978).
• 2: {B'81} M. Blum, "How to Exchange (Secret) Keys," to appear.
• 3: {BM'81} M. Blum and S. Micali, "Coin-Flipping into a Well," to appear.
• 4: {BR'81} M. Blum and M. O. Rabin, "Mail Certification by Randomization," to appear.
• 5: {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.
• 6: {L'77} W. J. LeVeque, "Fundamentals of Number Theory," Addison-Wesley Pub., 1977.
• 7: {M'76} G. L. Miller, "Riemann's Hypothesis and a Test for Primality," J. Comput. and System Sci. vol. 13 (1976), 300--317.
• 8: {MG'81} S. Micali and S. Goldwasser, "Mental Poker Without Commutative Locks," to appear.
• 9: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 10: {R'80} M. O. Rabin, "Probabilistic Algorithm for Testing Primality," J. Number Theory, vol. 12 (1980), 128--138.
• 11: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 12: {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.
• 13: {SS'77} R. Solovay and V. Strassen, "A Fast Monte-Carlo Test for Primality," SIAM J. Comput. vol. 6 (1977), 84--85.