Cryptography - coin flipping protocol

[docnet]

Homework Statement

coin flipping protocol

Relevant Equations

n = pq
b^2 = y(modp)
b^2 = -y(modq)

Conditions of the problem:
y =/= a^2 (mod pq)
-y =/= a^2 (mod pq)
p = 3 (mod 4)
q = 3 (mod 4)

(a) We assume y is both square (mod p) and (mod q). Then,
b^2 = y (mod p)
b^2 = y (mod q)
b^2 = y + pk
b^2 = y + qr
pk = qr ?

(should we assume b is the same between the two equations?)

(b)
-y = d^2 (modq)
q-y = d^2 (modq)
y + d^2 = q (modq)
d^2 = -y (modq)

(c)
y = a^2 (mod p)
-y = a^2 (mod q)

(again, should we assume b is the same between two equations?)

(d)
If bob has b and y, he can compute a relationship between p and q.
b^2 = y + pk
b^2 = -y + qr
2 b^2 + pk + qr ?

______________________________________________________________________________________________________________
(description of the coin flipping protocol)

Alice knows primes p = 3(mod) and q = 3(mod4). She computes pq = n, she sends n to Bob.

Bob chooses u so y = u^2 (modn), sends y to Alice

Alice finds 4 square roots of y using p and q.
square roots = u, -u, v, -v,

Alice picks one square root at random and sends it to Bob. If Alice picks u or -u she wins. If she picks v or -v, she loses.

Bob cannot lie and falsify Alice's loss because he only knows u, -u. therefore he will not be able to provide v if Alice asks for it.

 

[docnet]

Edit: At the end of the protocol, Alice asks Bob for the factorization of n. If Bob can produce p and q, it means he has all four square roots and Alice lost. If Bob can't produce p and q, it means Alice won.

 

[docnet]

update on (a)

if y is square mod p and q, we have the system of equations

x^2 = y (mod p)
x^2 = y (mod q)

which is only true if

x^2 = y + p*q
x^2 = y + q*p

however,

x^2 =/= y (mod n)

and

x^2 =/= y + pq*r for some constant r. in this case, we have r = 1

so y can't be a square both mod p and mod q, We use the same procedure to show for -y.

 

[docnet]

(b)

x^2 = -y (mod q)
x^2 = q-y (mod q)
x^2 + y = 0 (mod q)
x^2 = -y (mod q)
This seems like I'm going around in circles, it feels like i haven't used the relevant information. Does anyone see what i should be doing?

(c)
I'm not sure how to incorporate the right information to prove what the problem is aking. this sounds extremely general to me. any pointers?

(d). could he use b^2 as one of the square roots (mod n) and find gcd(x-b, n) to factor n?