# Show that there is an efficient zero knowledge proof for any language $L \in NP$

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

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)$$.

• 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$? – Gabi G Jan 2 at 13:33
• $V_2=V \circ R$, i.e., $V_2(x)$ just runs $V$ on $R(x)$. $P_2$ is defined similarly. – Chris Peikert Jan 2 at 13:36
• Okay, thanks! Your answer was very helpful! – Gabi G Jan 2 at 18:25