Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$.

I want to show that for every language $L$ that is reducible to $A$ there is also such an efficient zero-knowledge interactive proof $(P_2, V_2)$ which is also $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$.

Well, I am not sure how exactly to start to describe such $(P_2, V_2)$, but maybe I don't understand this completely since it seems there is only one straightforward way.

Since $L$ is reducible to $A$, then there is a Levin reduction from $L$ to $A$. Namely, there is a polynomial algorithm $R$ such that $R(x) \in A \leftrightarrow x \in A$, and there is a polynomial algorithm $W$ that maps a witness $w$ for $x \in L$ to the witness $W(x,w)$ for $R(x) \in A$.

My idea was to take the proof system $(P,V)$ and for the input $x$ apply $R(x)$ to simulate the original zero-knowledge proof for $A$.

However, it seems too trivial to me. Moreover, in this way I only get $(T-|R|,\epsilon)-\text{sound}$ and $(T-|R|,\epsilon)-\text{ZK}$, since I need to run the algorithm $R$.

Help Would be appreciated.


1 Answer 1


Your idea is correct. Although the running times of the honest prover and verifier do increase by the running time of $R$, this (somewhat counterintuitively) does not affect the concrete bounds for soundness and ZK (at least how they are usually defined).

Note that $T$-soundness does not really make sense for a proof system, since it is sound against even unbounded cheating provers. However, it does make sense for an argument system, and here we don’t really “lose” the reduction $R$’s runtime: any $T$-time cheating prover $P_2^*$ for some instance $x \notin L$ is itself a $T$-time cheating prover for the instance $R(x) \notin A$, because it fools the verifier $V$ (for language $A$) without doing any additional computation. The latter does not exist by assumption, so neither does the former.

Similar reasoning holds for ZK: a $T$-time cheating verifier $V_2^*$ for some instance $x\in L$ is itself a $T$-time cheating verifier for $R(x) \in A$, because it plays the role of $V$ in talking to $P$. So, we don’t need any additional computation to “gain knowledge” from an interaction with $P$ about $R(x)$.

  • $\begingroup$ thanks! Could you clarify a little bit how to practically construct $(P_2, V_2)$? It is still a little bit in the air for me. Namely, when exactly in the proof $(P V)$ I apply $R$ and $W$? $\endgroup$
    – Gabi G
    Jan 2, 2021 at 13:33
  • $\begingroup$ $V_2=V \circ R$, i.e., $V_2(x)$ just runs $V$ on $R(x)$. $P_2$ is defined similarly. $\endgroup$ Jan 2, 2021 at 13:36
  • $\begingroup$ Okay, thanks! Your answer was very helpful! $\endgroup$
    – Gabi G
    Jan 2, 2021 at 18:25

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.