Zero-Knowledge from Secure Multiparty Computation

Zero-Knowledge from Secure Multiparty Computation

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai
STOC 2007 [pdf] [bibtex]

“MPC in the head” exploits MPC techniques and protocols to achieve efficient Zero Knowledge protocols. The idea that was presented in the (IKOS07) constructs zero knowledge proofs from multiparty computation protocols. These MPC protocols must be secure in the presence of an honest majority. Their idea is to have the prover imagines in its head ⚠ {$n$} players running an MPC protocol ∏⚠ {$_f$} that verifies the security of the ⚠ {$n$} parties’ functionality. The prover’s view of the ⚠ {$n$} parties functionality consists of the ⚠ {$n$} players using an NP statement, sharing secret witness as private inputs and all players are communicating with each other. The prover commits to the views of all players. Then, the verifier selects a random subset of the parties’ views. The prover must open the committed views of these random pair and the verifier respond according to the consistency of these views. The probability that the prover cheats undetected or the verifier accepts inconsistence views is very small.

Zero-knowledge protocol ∏⚠ {$_R$}:

  1. Prover imagines ⚠ {$n$} parties running an MPC protocol ∏⚠ {$_f$} for ⚠ {$f(x,w_1…,w_n )=R(x,w_1 \oplus ...\oplus w_n )$}. The prover needs to prove knowledge of ⚠ {$w$} such that ⚠ {$R(x,w)=1$}. The prover prepares the views ⚠ {$V_1,…,V_n$} of the ⚠ {$n$} players and she commits to each of these n views. A view consists of the inputs ⚠ {$w_1…,w_n$} and random coins of the player, and all exchanging messages.
  2. Verifier selects a random subset of views ⚠ {$i,j$} ∈ [⚠ {$n$}] and asks the prover to open these views.
  3. Prover opens the committed views of these random pair ⚠ {$V_i,V_j$}.
  4. Verifier responds according to:
  • The consistency of the messages inside the two opened views.
  • The output of ⚠ {$P_i$} and ⚠ {$P_j$}.

The protocol ∏⚠ {$_R$} is a ZK protocol if it satisfies three properties:

  • Completeness: if ⚠ {$R(x,w) = 1$}, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
  • Soundness: if ⚠ {$R(x,w) = 0$} for all ⚠ {$w$}, no cheating prover can convince the honest verifier that it is true, except with some small probability ⚠ {$(2^{-k})$}.
  • Zero-knowledge: if ⚠ {$R(x,w) = 1$}, no cheating verifier learns anything other than this fact.

Categories:

MPC in the head?, Zero Knowledge?