0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ How does this differ from the classical protocol? See, e.g., cs.jhu.edu/~abhishek/classes/CS600-442-Fall2016/S10.pdf. $\endgroup$
    – D.W.
    Commented May 16 at 20:32
  • $\begingroup$ @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. $\endgroup$
    – GeoArt
    Commented May 17 at 3:58
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented May 17 at 4:49

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.