Coin flipping protocol

Coin flipping protocol

• Coin flipping protocol

• Completely secure vs. normally secure one-way functions

• Some protocols that do not work

• Blum Protocol

• Goldwasser-Micali Probabilistic Encryption

Want to flip a coin over the telephone

• Want to flip a coin over the telephone

• Fair and verifiable
• Not subject to cheating

Let M be a message and let C be the encrypted message (ciphertext). A public key cryptosystem has a separate method E() for encrypting and D() decrypting.

• Let M be a message and let C be the encrypted message (ciphertext). A public key cryptosystem has a separate method E() for encrypting and D() decrypting.

• D(E(M)) = M
• Both E() and D() are easy to compute
• Publicly revealing E() does not make it easy to determine D()
• E(D(M)) = M - needed for signatures

• The collection of E()’s are made publicly available but the D()’s remain secret. Called a one-way trap-door function (hard to invert, but easy if you have the secret information)

Generate Encryption/Decryption Keys

• Generate Encryption/Decryption Keys

• A: Randomly select flip = “heads” or “tails”
• A  B EA(flip)
• B  A guess heads or tails
• A  B DA() to check result

• What’s wrong

Normally Secure One-Way Function

• Normally Secure One-Way Function

• Efficiently computable function whose inverse can not be computed efficiently

• Completely Secure One-Way Function

• Normally secure plus knowledge of f(x) does not give more than 50-50 chance of efficiently guessing some non-trivial property such as parity

A: randomly select x

• A: randomly select x

• A  B f(x)

• B  A guess x even/odd

• A  B send x to verify result

Generate Keys: N = PQ, gcd(e,(N))=1, ed  1(mod (N)), E = (e,N), D = (d,N)

• Generate Keys: N = PQ, gcd(e,(N))=1, ed  1(mod (N)), E = (e,N), D = (d,N)

• A: Randomly select x (use parity)
• A  B E(x)
• B  A guess parity of x
• A  B D() to check parity of result

• What could be wrong

Zp = <>, p  1 (mod 4) prime

• Zp = <>, p  1 (mod 4) prime

• A: Randomly select x (use parity)
• A  B y = x
• B  A guess parity of x
• A  B send x to verify guess

• Probability is correct. What is wrong?

Bob generates n=pq where p and q are both primes equivalent to 3 mod 4 and sends n to Alice

• Bob generates n=pq where p and q are both primes equivalent to 3 mod 4 and sends n to Alice

• Alice generates a random x and computes y = x2 (mod n) and sends y to Bob [this is the coin flip]

• Bob guesses heads b = 1 or tails b = -1 and sends the guess to Alice

• Alice sends x to Bob and Bob computes J(x,n) and checks to see if J(x,n)=b If so he wins otherwise he loses.

Four solutions x2  a (mod N) [use CRT]

• Four solutions x2  a (mod N) [use CRT]

• (±b)2  a (mod P), (±c)2  a (mod Q)
• P  Q  3 (mod 4)  J(-1,P) =J(-1,Q) = -1
• Half with J(x,N) = 1, half with J(x,N)= -1

• Knowing solutions x1 and x2 gives P, Q

• x1  b (mod P), x1 = c (mod Q)
• x2 = b (mod P), x2 = c (mod Q)
•  gcd(x1-x2,N)=Q

Let M be a message and let C be the encrypted message (ciphertext). A public key cryptosystem has a separate method E() for encrypting and D() decrypting.

• Let M be a message and let C be the encrypted message (ciphertext). A public key cryptosystem has a separate method E() for encrypting and D() decrypting.

• D(E(M)) = M
• Both E() and D() are easy to compute
• Publicly revealing E() does not make it easy to determine D()
• E(D(M)) = M - needed for signatures

• The collection of E()’s are made publicly available but the D()’s remain secret. Called a one-way trap-door function (hard to invert, but easy if you have the secret information)

Goldwasser-Micali (Quadratic Redisuosity)

• Goldwasser-Micali (Quadratic Redisuosity)

• N = pq, x a non-residue such that
• m = m1   mt, mi  {0,1}
• c = c1   ct, ci = yixmi mod N, yi random quadratic residue
• Shafi Goldwasser and Silvio Micali. Probabilistic Encryption. Journal of Computer and System Sciences (JCSS), 28(2):270-299, April 1984.