# Coin flipping protocol

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

• ## Want to flip a coin over the telephone

• Fair and verifiable
• Not subject to cheating

• ## 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

• ## 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

• ## 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

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

• ## 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.

• 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)

• 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.

Yüklə 156,5 Kb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

Ana səhifə