Sequentially composing zero knowledge proofs

Cryptography 2019-02-18

The material in this post will be really simple, really.

I went to the 9th BIU Winter School this year. 這真是難得的經驗（突然中文）。 I will try to write some interesting stuffs during the program. However, due to time limit I will not be able to cover all the abundant materials in the school. Interested readers are referred to the official site of the school for videos, slides and other information.

An IP Protocol for non-QR

The problem of deciding if an arbitrary element $x$ is a quadratic residue modulo $N$ when $N$ is composite is conjectured to be hard Wikipeida : Quadratic Residuosity Problem.

The following is a protocol ([GMR’85]) for non-QR (in the reduced group $\mathbb{Z}^*_{N}$ . Is the protocol zero-knowledge?

Given $x$ as common input to $(P(x),V(x)):$

:
sample .
- If $b = 0$ send $z \gets y^2$ to $P$ ;
- If $b = 1$ send $z \gets xy^2$ to $P$ .
:
- If $z \in QR_{N}$ send $b' = 0$ to $V$ ;
- Otherwise send $b' = 1$ to $V$ .
$V$ accepts iff $b = b'$ .

Completeness

If $x \notin QR_{N}$ , then when $b = 0$ the honest prover receive a residue; but when $b = 1$ the honest prover receive a non-residue. This is due to the subgroup structure of $QR_{N}$ .

Therefore any honest prover is accepted with probability 1.

Soundness

If $x \in QR_{N}$ , then in either situation the sent item is a random element in $QR_{N}$ . Therefore any prover can succeed in guessing $b$ with probability exactly $\frac{1}{2}$ . To achieve exponential soundness, repeat the protocol and use concentration inequalities.

ZK?

To prove zero-knowledgeness, we need to build a simulator $S(x)$ which, upon receiving $x$ , generates a distribution view for the verifier, s.t. the view is indistinguishable from the distribution of the view of a verifier in a real execution of the protocol.

Note: the definition of indistinguishability is crucial in the definition and give rise to different complexity classes. Here we will consider perfect ZK, i.e. the simulated distribution is identical to the actual one.

One can come up with the following.

Given $x$ to $S(x)$ :

Sample $y_S \xleftarrow{R} \mathbb{Z}^*_{N}, b_S \xleftarrow{R} \{0,1\}$ .
Let $b'_S \gets b_S$ .

If $x \in QR_{N}$ , then the verifier will expect to receive $b'$ as equal to $b$ . Therefore we would see $(y_S, b_S, b_S')$ is identical to the distribution desired.

Or is it?

Reference:

Alon Rosen: Introduction to Zero Knowledge, talk & slides. (Day 1 of BIU school)

official site of BIU Winter School.