|
Coin flipping protocol
|
tarix | 08.08.2018 | ölçüsü | 156,5 Kb. | | #61635 |
|
Coin flipping protocol Completely secure vs. normally secure one-way 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 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 - 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 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(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.
Dostları ilə paylaş: |
|
|