bit commitment with hash functions Commitment Alice: generates random ry r2 Alice-Bob: r1 and x= h ry r2 m [x is called a blob] Revelation Aice→Bob: ri r2y m Bob hashes(r1 r2,m and compares it to x Discussion Bob does not have to send any messages Alice sends a message to commit and a message to reveal Alice cannot find r3 such that h(ry r3r m)== h(ty r2, m) The value r2 is kept secret so Bob can't brute force the message space
11 bit commitment with hash functions Commitment: • Alice: generates random r1 , r2 • Alice → Bob: r1 and x = h(r1 , r2 , m) [x is called a blob] Revelation: • Alice → Bob: r1 , r2 , m • Bob hashes (r1 , r2 , m) and compares it to x Discussion: • Bob does not have to send any messages – Alice sends a message to commit and a message to reveal • Alice cannot find r3 such that h(r1 , r3 , m) == h(r1 , r2 , m) • The value r2 is kept secret so Bob can’t brute force the message space
fair coin flipping Problem Alice and Bob are arguing on the internet over who will be white in a game of online chess They agree to flip a coin to resolve the situation. Alice doesn t trust Bob to flip the coin. Bob doesnt trust Alice to flip the coin. How can we flip a coin fairly? 12
12 fair coin flipping Problem: • Alice and Bob are arguing on the Internet over who will be white in a game of online chess . • They agree to flip a coin to resolve the situation. • Alice doesn’t trust Bob to flip the coin. • Bob doesn’t trust Alice to flip the coin. • How can we flip a coin fairly?