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)                
c ← Z_{n}^$; Cmt ← c² mod N --Cmt-->
RSP ← c . x^{Ch} mod N      --RSP-->  d ← Rsp² = Cmt . X^{Ch} mod N; return d

Question: Show that the protocol $(P,V)$ fails to satisfy soundness for the language $QR$ by presenting a strategy for a cheating prover to convince the verifier to accept (this means return $d = true$) with probability one when the parties have common input $(N,X)$ not element of $QR$.

My Solution:

Let $Ch = 0$. Then $Rsp \leftarrow c.x^0 \pmod N = c$. Then $d \leftarrow c^2 \equiv c^2 \pmod N$.

I am not sure what I need to show next such that $d$ always returns $true$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.