# Can interactive zero-knowledge proof systems be implemented using secure two-party computation?

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real world, there exists a simulator that carries out this attack successfully in the ideal world. It follows that security in the real world must be equivalent to security in the ideal world.

I am defining interactive zero-knowledge proof systems for a language $$L$$ using the original definition from The Knowledge Complexity of Interactive Proof Systems. That is, a pair $$(A, B)$$ of interactive Turing machines must fulfill

1. Completeness: given $$x \in L$$, $$B$$ accepts with very high probability;
2. Soundness: given any prover $$A'$$ and $$x \not\in L$$ passed into $$(A', B)$$, $$B$$ accepts with very low probability;
3. Zero-Knowledge: there exists a probabilistic polynomial-time simulator that can simulate the entire exchange of messages between $$A$$ and $$B$$ for any input $$x \in L$$.

Now, the paper Zero-Knowledge from Secure Multiparty Computation mentions the following:

Zero-knowledge protocols can be viewed as a special case of secure two-party computation, where the function verifies the validity of a witness held by the prover.

That is, given $$L \in \mathcal{NP}$$, there exists an algorithm $$A$$ such that $$x \in L \iff \exists w\colon A(x, w) = 1$$ (definition of $$\mathcal{NP}$$). One party $$P_1$$ acts as the prover, another $$P_2$$ as the verifier. $$P_1$$ knows $$x$$ and $$w$$, $$P_2$$ knows only $$x$$. They execute $$A(x, w)$$ together to determine whether $$x \in L$$ or not.

Clearly, $$w$$ is not revealed to the verifier $$P_2$$ due to the MPC protocol. However, is the definition of zero-knowledge not more general? If the prover $$P_1$$ sent, for some reason, the solution to some instance of an $$\mathcal{NP}$$-complete problem1, no polynomial-time simulator could simulate this assuming $$\mathcal{P} \neq \mathcal{NP}$$. The created proof system would not be zero-knowledge.

So, given that an MPC protocol could exchange non-simulatable messages, an MPC protocol cannot actually be used to implement a zero-knowledge proof system for some language $$L \in \mathcal{NP}$$, can it?

1 The solution can be made dependent on $$x$$ such that it is not constant and thus easily simulatable.

• Yes, but this scheme is what I described right below the citation with parties $P_1$ and $P_2$, isn't it? My question specifically addresses that zero-knowledge means not only not leaking $w$, but also not leaking anything else, while secure MPC might leak other knowledge than $w$. Therefore, it appears unreasonable to me that MPC could be used to construct a zero-knowledge proof. Aug 25 at 15:39