Week 12 (rev. 3) 
Professor M. J. Fischer  April 12 & 14, 2005 
Alice  Bob  
1.  Choose random bit b_{A} ∈ {0,1}  → ^{bA}.  
2.  ← ^{bB}  Choose random bit b_{B} ∈ {0,1}.  
3.  Coin outcome is b = b_{A} ⊕b_{B}.  Coin outcome is b = b_{A} ⊕b_{B}. 
Alice  Bob  
1.  Choose random bit b_{A} ∈ {0,1}.  Choose random bit b_{B} ∈ {0,1}.  
2.  commit(b_{A}).  ↔  commit(b_{B}). 
3.  open(c_{A}).  ↔  open(c_{B}). 
4.  Coin outcome is b = b_{A} ⊕b_{B}.  Coin outcome is b = b_{A} ⊕b_{B}. 
Alice  Bob  
1.  Choose RSA key pair A with modulus n=pq.  Choose RSA key pair B with modulus n=pq.  
2.  Choose random r ∈ Z_{(n−1)/2}.  
Let m_{i} = 2r+i, for i ∈ {0,1}.  
Let c_{i} = E_{A}(m_{i}) for i ∈ {0,1}.  
Let C = {c_{0}, c_{1}}.  → ^{C}  Choose c_{a} ∈ C.  
3.  ← ^{cab}  Let c_{ab} = E_{B}(c_{a}).  
4.  Let c_{b} = D_{A}(c_{ab}).  → ^{cb}  
5.  Let m = D_{B}(c_{b}).  
Let i = m mod 2.  
Let r = (m−i)/2.  
If i=0 outcome is "tails".  
If i=1 outcome is "heads".  
← ^{B}  
6.  Let m = D_{B}(c_{b}).  
Check m ∈ {m_{0}, m_{1}}.  
If m=m_{0} outcome is "tails".  
If m=m_{1} outcome is "heads".  
→ ^{A}  
7.  Let c′_{a} = C − { c_{a} }.  
Let m′ = D_{A}( c′_{a} ).  
Let i′ = m′ mod 2.  
Let r′ = (m′−i′)/2.  
Check that i′ ≠ i and r′ = r. 
Alice  Bob  
1.  Secret s.  
Choose primes p, q, and let n = pq.  
Generate RSA public key (e, n).  
Compute c = E_{(e,n)}(s).  
→ ^{(e, n, c)}  
2.  Choose random x ∈ Z^{∗}_{n}.  
← ^{a}  Compute a = x^{2} mod n.  
3.  Check a ∈ QR_{n}.  
Choose y at random from among the 4 square roots of a mod n.  
→ ^{y}  
4.  Check y^{2} ≡ a mod n.  
If y \not ≡ ±x mod n, use x, y to factor n and decrypt c to obtain s. 
Alice  Bob  
1.  Choose two PKS key pairs (e_{0}, d_{0}) and (e_{1}, d_{1}).  
→ ^{e0, e1}  
2.  Generate random key k for a symmetric cryptosystem ([^(E)], [^(D)]).  
Choose e ∈ {e_{0},e_{1}}.  
← ^{c}  Compute c = E_{e}(k).  
3.  Compute k_{i} = D_{di}(c) for i=0, 1.  
Compute c_{i} = [^(E)]_{ki}(s_{i}) for i=0, 1.  → ^{c0, c1}  
4.  Compute s_{i} = [^(D)]_{k}(c_{i}) for i=0, 1.  
One of the s_{i} is correct and the other is garbage. 









To Q(x):  
1.  Let s_{2} = x^{2} mod n. 
2.  Let s_{i} = s_{i−1}^{2} mod n, for i=3, …, k. 
3.  Let b_{1} = lsb(x). 
4.  Let b_{i} = lsb(s_{i}), for i=2, …, k. 
5.  Let c = A(b_{2}, …, b_{k}). 
6.  If c = b_{1} then output 1; else output 0. 


