Score:1

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

sa flag

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.

Score:2
cn flag

Zero-knowledge was initially defined with respect to arbitrary (possibly unbounded) provers. However, when we use or discuss zero-knowledge in cryptography, we almost always implicitly assume ZK for NP where the prover runs in polynomial time given a witness for the statement. This is the type of zero-knowledge proof the paper was referring to, and this is indeed a special case of maliciously-secure two-party computation.

cadaniluk avatar
sa flag
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.
Geoffroy Couteau avatar
cn flag
How would the polynomial-time prover (who is only given the witness for the statement) leak this "other knowledge"? Either this is hardcoded in its description - then it can be harcoded in the simulator, or it is easy to compute (then the simulator can compute it). Otherwise, there is no way anything hard-to-simulate is leaked by the MPC protocol. If you inspect the definition, it holds directly that malicious 2-party MPC is a strict generalization of zero-knowledge.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.