3
$\begingroup$

A zero-knowledge proof system for a language $L$ is an interactive proof system where a prover $P$ (a Turing machine) tries to convince a verifier $V$ (a polynomially bounded Turing machine) in a sequence of message exchanges that $x \in L$ so that $V$ learns nothing from the interaction except whether $x \in L$ or not.

Question. Is it known how iterate this, i.e.: how to produce a ZK proof that I possess a ZK proof for membership in $L$?

$\endgroup$
7
  • $\begingroup$ What would it mean to "possess" such a proof? ​ (possessing the transcript of such a proof?) ​ ​ ​ ​ $\endgroup$ – user12859 Sep 23 '15 at 13:42
  • $\begingroup$ @RickyDemer I'm not sure how to define this properly. It's part of the question. A ZK proof system consists of a couple of TMs with certain properties. Can I demonstrate the possession of said TMs without leaking any other information? $\endgroup$ – Martin Berger Sep 23 '15 at 13:54
  • $\begingroup$ Do you want it to be for the proof system or just for a particular x? ​ $\endgroup$ – user12859 Sep 23 '15 at 13:59
  • $\begingroup$ @RickyDemer For the proof system. But I assume that the two problems are related. $\endgroup$ – Martin Berger Sep 23 '15 at 14:02
  • $\begingroup$ In that case, something like MIP* would be needed, since the property of L having a zero-knowledge proof system is undecidable by reduction from the halting problem. ​ $\endgroup$ – user12859 Sep 23 '15 at 14:13
3
$\begingroup$

Yes, it's possible. There is a ZK proof for every language in NP. Roughly speaking, this means that if there's a way for someone to prove it (by giving a polynomial-size witness/proof), there's a way to prove it with a zero knowledge proof.

For instance, if you have a transcript of a ZK interaction, there's a polynomial-time algorithm to verify whether the ZK interaction should be accepted by the verifier, so it's possible to prove in ZK (i.e., it's possible to give a ZK proof) that you know a transcript of a ZK interaction that would be accepted by the verifier. However, this might not be quite what you want, because this doesn't prove that the randomness was chosen randomly by the verifier.

Here's a better instance of what you're looking for. Look up non-interactive zero knowledge proofs. Suppose I know a string $p$ that is a valid non-interactive zero knowledge (NIZK) proof of some statement $s$. Moreover, there is a polynomial-time algorithm that allows verifying whether $p$ is a valid NIZK proof of $s$. Therefore, there's a way I can use a ZK proof to prove to Alice in zero-knowledge that I know a string $p$ that is a valid NIZK proof of $s$, without revealing $p$ to Alice (because this is proving a NP statement).

That said, this probably isn't useful. What would be the point? I don't think this lets Alice conclude anything more than if I just proved in ZK to her that $s$ is true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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