Improved Zero Knowledge ZK-PCP from MPC

“MPC in the head” is a well-known cryptographic technique for constructing a probabilistically-checkable zero-knowledge proof (PCP) out of an MPC protocol. Basically, a prover P wants to prove to a verifier V that C(x)=1 where C is public but x is known only to P. Locally, or “in his own head,” P runs an MPC protocol where the virtual players together compute C(x). Then, P uses a commitment protocol to commit to the views of all virtual players via a Merkle tree. V asks to see the views of a small random set of players, and once P decommits to these, V accepts if all players views are consistent with each other (in terms of incoming and outgoing messages) and consistent with the output being C(x)=1. This “MPC in the head” technique is the basis of many existing zero-knowledge proof systems. We plan to apply a new MPC protocol based on fast multiplication verification to this framework in the hopes of constructing a new, more efficient PCP.