Coin flipping by telephone a protocol for solving impossible problems
- 1 January 1983
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 15 (1), 23-27
- https://doi.org/10.1145/1008908.1008911
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.Keywords
This publication has 5 references indexed in Scilit:
- Probabilistic algorithm for testing primalityJournal of Number Theory, 1980
- Privacy and authentication: An introduction to cryptographyProceedings of the IEEE, 1979
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978
- A Fast Monte-Carlo Test for PrimalitySIAM Journal on Computing, 1977
- Riemann's hypothesis and tests for primalityJournal of Computer and System Sciences, 1976