QR ZK protocol in Lecture 7

QR ZK protocol in Lecture 7

Keren Ganon 31 Jan 2020 14:43

In the first ZK example for The QR language, V samples a bit b and P answers different answers according to it.

Why is this necessary? If we were to remove this bit sampling and have P always send rx to V, wouldn't this still work?
Then the simulator would simply always return y^-1r² to V as the first message.

Re: QR ZK protocol in Lecture 7

nbitansky 31 Jan 2020 17:37

If I understand what you're saying, you seem to be suggesting a one-message protocol: $P$ sends $a = r^2, b= rx$, $V$ checks that $ya = b^2$.
This protocol is not sound. A malicious prover can pick $b$ arbitrarily and choose $a = b^2/y$ and convince you of accepting a non-residue. Recall that in general, there cannot be one-message zero knowledge, except for trivial languages.