Lecture 8: Coin Flipping by Telephone Wayne Patterson SYCS 654 Spring 2010 Coin Flipping by Telephone • Originally presented by Manuel Blum, then at UC Berkeley (now at Carnegie-Mellon): • M. Blum. Coin flipping by telephone. In Proceedings of IEEE Spring Computer Conference, pages 133--137. IEEE, 1982. • Blum was Rene Peralta’s thesis advisor • Rene is a colleague who is now responsible for security in electronic voting at NIST As Rene Posed the Problem • Alice and Bob have decided to divorce. They are in different cities, want to decide who gets the (house, car, dog, …) • They decide to flip a coin • Naturally they don’t trust each other … Alice and Bob Agree on a Secure One-Way Function • For example, the function could be ax (mod p), for an agreedupon large prime number p and an agreed-upon primitive root a. Alice Will Flip the Coin • The act of flipping is the choice of a secret x, 1 < x < p-1. • x is either odd or even (i.e. heads or tails) • Alice chooses x (the flip) and announces to Bob the computation y = ax mod p. What Does Bob Do? • Bob receives y, and guesses that x is odd or even (heads or tails). • Bob sends his guess to Alice. • Alice verifies the result, whether Bob guessed right or wrong, and proves her decision by sending x to Bob. • Bob can verify that Alice did not lie by performing the same computation y = ax mod p. • If Alice lied about the value of x, Bob can prove the lie by the fact that the y he computes will not be the same y he had received.