<p>Zero-knowledge proofs do not in general compose in parallel. See <a href="https://dl.acm.org/doi/10.1145/100216.100272" rel="nofollow noreferrer">this paper</a> 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, <a href="https://epubs.siam.org/doi/abs/10.1137/S0097539791220688" rel="nofollow noreferrer">Goldreich and Krawczyk</a> prove that no 3-message proof system for a language <span class="math-container">$L$</span> can be <em>black-box</em> zero-knowledge, i.e. where the simulator only uses the malicious verifier as a black-box, unless <span class="math-container">$L\in BPP$</span>. So the simulator would have to use the verifier in a non-black-box way. Non-black-box simulation <a href="https://ieeexplore.ieee.org/abstract/document/959885" rel="nofollow noreferrer">has been used</a> successfully to circumvent impossibility results, but the construction is rather more involved than the parallel repetition of a simple proof system.</p>

CC BY-SA 4.0
2024-05-30T19:51:47.340Z
2024-05-30T19:51:47.340Z
lamontap
<p>Consider such protocol for <span class="math-container">$GI$</span> (Graph-isomorphism problem).</p>
<p><span class="math-container">$P$</span> randomly chooses permutations <span class="math-container">$\sigma_1, \sigma_2, ..., \sigma_k$</span> and sends <span class="math-container">$H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k &gt; 1)$</span>;</p>
<p><span class="math-container">$V$</span> randomly chooses <span class="math-container">$b_1, ..., b_n \in \{0,1\}$</span> and sends it;</p>
<p><span class="math-container">$P$</span> finds <span class="math-container">$\tau_i = \begin{cases}\sigma_i &amp;\text{if } b_i = 0\\\sigma_i\pi&amp;\text{if } b_i = 1 \end{cases}$</span> where <span class="math-container">$\pi(G_1) = G_0$</span> and sends <span class="math-container">$\tau_1,...,\tau_n$</span>.</p>
<p>It is rather similar to classical one, showing <span class="math-container">$GI \in PZK$</span>. The probability to accept non-isomorphic graphs seems to be not greater than <span class="math-container">$\displaystyle\frac{1}{2^n}$</span> in this case. But would such protocol be zero-knowledge?</p>

CC BY-SA 4.0
2024-05-16T20:32:13.147Z
How does this differ from the classical protocol?  See, e.g., https://www.cs.jhu.edu/~abhishek/classes/CS600-442-Fall2016/S10.pdf.
D.W.
CC BY-SA 4.0
2024-05-17T03:58:40.067Z
@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.
GeoArt
CC BY-SA 4.0
2024-05-17T04:49:24.583Z
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.
<graph-theory><complexity-classes><graph-isomorphism><interactive-proofs><zero-knowledge>
Is the protocol perfect zero knowledge?
GeoArt
# Is the protocol perfect zero knowledge?

(Asked by: username_0 on 2024-05-16)

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?

**Tags:** graph-theory, complexity-classes, graph-isomorphism, interactive-proofs, zero-knowledge
> **Comments:**
> **username_1**: How does this differ from the classical protocol?  See, e.g., https://www.cs.jhu.edu/~abhishek/classes/CS600-442-Fall2016/S10.pdf.  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2024-05-30. Score: 2

Zero-knowledge proofs do not in general compose in parallel. See [this paper](https://dl.acm.org/doi/10.1145/100216.100272) 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](https://epubs.siam.org/doi/abs/10.1137/S0097539791220688) 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](https://ieeexplore.ieee.org/abstract/document/959885) successfully to circumvent impossibility results, but the construction is rather more involved than the parallel repetition of a simple proof system.


---

