Interactive Proofs

y ∉ QNRn

Choose b'

Pr[b'=b]=1/2