
Coin flipping protocol

tarix  08.08.2018  ölçüsü  156,5 Kb.   #61635 

Coin flipping protocol Completely secure vs. normally secure oneway functions Some protocols that do not work Blum Protocol
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. The collection of E()’s are made publicly available but the D()’s remain secret. Called a oneway trapdoor 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 OneWay Function  Efficiently computable function whose inverse can not be computed efficiently
Completely Secure OneWay Function  Normally secure plus knowledge of f(x) does not give more than 5050 chance of efficiently guessing some nontrivial property such as parity
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
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(x1x2,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 oneway trapdoor function (hard to invert, but easy if you have the secret information)
GoldwasserMicali (Quadratic Redisuosity) GoldwasserMicali (Quadratic Redisuosity)  N = pq, x a nonresidue 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):270299, April 1984.
Dostları ilə paylaş: 

