Setup: n = p q where p and q are distinct odd primes. Pat claims: x ? _n . Repeat m-many times: Vanna chooses v ? Z^?_n, randomly, & i ? { 0, 1 }, randomly, computes z = xⁱv² mod n, and sends Pat z. Pat, upon receiving z, sends j to Vanna where: if z ? QR_n , then j = 0 else j = 1. Vanna tests whether i = j and, if not, she rejects. If Vanna has not rejected after m-many rounds, she accepts

(a) Prove that the above is complete.

(b) Prove that the above is sound.

(c) The above is NOT prefect zero knowledge. Explain why.

Reference

|A| = the number of elements in set A.

?(n) = |{ a ? Z⁺_n : gcd(a, n) = 1 }|.

Eulers Theorem: For each n > 1 and a ? Z^?_n : a^?(n) 1 (mod n).

g is a primitive element of Z^?_n iff { g¹ , g² , . . . , g^?(n) } = Z^?_n .

Suppose g is a primitive element of Z^?_n . For a ? Z^?_n, the discrete log of a to the base g mod p (written: dlog_g (a)) is the solution for x of: g^x a (mod n), i.e., g ^dlog_g(a) a (mod n).

Definition. Suppose a, n ? Z with n > 1 and a 0. (a) a is a quadratic residue mod n when x² ? a (mod n) has a solution, otherwise a is a nonresidue. (b) QR_n = the quadratic residues mod n. (c) Suppose n is the product of two distinct odd primes p and q. n = { a : ( ) = ?1 = ( ) } = the pseudo-residues mod n. ( Solve it without doing integration iif possible)

QR