Title: Shorter Zero-Knowledge Proofs from MPC
| Speaker: | Greg Zaverucha |
| Affiliation: | Microsoft Research |
| Zoom: | Please email Emma Watson |
Abstract:
In this talk I will review the MPC-in-the-head approach to constructing zero-knowledge proofs, then talk about some recent research results to make the proofs shorter.
In a zero-knowledge proof system, a prover wants to convince a verifier that they know a secret value, without revealing it. A common case involves a one-way function, where the prover wants to convince a verifier that they know a secret input corresponding to a public output. A secure multi-party computation (MPC) protocol allows a group to compute a function on secret-shared input data. MPC-in-the-head proof systems work by first having the prover simulate the execution of an MPC protocol, and commit to the views of each party, i.e., the inputs, outputs and the messages sent between parties. Then the verifier selects a subset of the parties, and the prover reveals their views. The verifier checks that the views are consistent with one another, building confidence that the function was evaluated correctly and that the secret-shared input is indeed related to the public output. The main application of MPC-in-the-head proof systems has been to construct signature schemes with post-quantum security, since the proof systems are very flexible and do not require structured hardness assumptions. Here the size of the proof is important, and I will present some recent results (joint work with Daniel Kales), on a new approach to shorter proofs. When applied to the Picnic signature scheme, our improvements reduce signature size by 1.6x.