# Zero Knowledge Proof

In the following protocol $(P,V)$, prover $P$ and verifier $V$have common input $(N,X) \epsilon QR$ while the prover also has private input $x \epsilon SR(N,X)$. Let $SR(N,X) = \{x \epsilon$ $Z_{n}^{*} : X = x^{2} mod N\}$ and $QR(N) = \{X \epsilon Z_{n}^{*} : SR(N,X) \neq \phi (empty set)\}$. Also let $QR = \{(N,X) : N \geq 1 and X \epsilon QR(N)\}$.

Prover(P)                               Verifer(V)
<-CH----  Ch ← {0,1} (Picked at random)