patternMinor
ZK proof that I possess a ZK proof for membership in $L$?
Viewed 0 times
membershipthatforpossessproof
Problem
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$?
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$?
Solution
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.
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.
Context
StackExchange Computer Science Q#47473, answer score: 3
Revisions (0)
No revisions yet.