# Is the protocol perfect zero knowledge?

Consider such protocol for $$GI$$ (Graph-isomorphism problem).

$$P$$ randomly chooses permutations $$\sigma_1, \sigma_2, ..., \sigma_k$$ and sends $$H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k > 1)$$;

$$V$$ randomly chooses $$b_1, ..., b_n \in \{0,1\}$$ and sends it;

$$P$$ finds $$\tau_i = \begin{cases}\sigma_i &\text{if } b_i = 0\\\sigma_i\pi&\text{if } b_i = 1 \end{cases}$$ where $$\pi(G_1) = G_0$$ and sends $$\tau_1,...,\tau_n$$.

It is rather similar to classical one, showing $$GI \in PZK$$. The probability to accept non-isomorphic graphs seems to be not greater than $$\displaystyle\frac{1}{2^n}$$ in this case. But would such protocol be zero-knowledge?

• How does this differ from the classical protocol? See, e.g., cs.jhu.edu/~abhishek/classes/CS600-442-Fall2016/S10.pdf.
– D.W.
Commented May 16 at 20:32
• @D.W. The difference is that P randomly chooses k permutations (I forgot to mention that k > 1). Whouldn't it give more information about isomorphism for verifier? I didn't manage to prove that protocol is zero-knowledge in the way it is done for classical one. Commented May 17 at 3:58
• I think it would be helpful to edit your post to highlight that you are asking about whether you can run $n$ copies in parallel (concurrent self-composition), to make it clear what your focus is.
– D.W.
Commented May 17 at 4:49

Zero-knowledge proofs do not in general compose in parallel. See this paper by Feige and Shamir for a (contrived) counterexample. Beyond this counterexample, there are several constraints to actually showing that a proof system composes in parallel. For example, Goldreich and Krawczyk prove that no 3-message proof system for a language $$L$$ can be black-box zero-knowledge, i.e. where the simulator only uses the malicious verifier as a black-box, unless $$L\in BPP$$. So the simulator would have to use the verifier in a non-black-box way. Non-black-box simulation has been used successfully to circumvent impossibility results, but the construction is rather more involved than the parallel repetition of a simple proof system.