Fall 2019

Ligero: Sublinear Arguments from MPC-in-the-head

Friday, Sep. 27, 2019 11:00 am12:00 pm PDT

Add to Calendar


Muthu Venkitasubramaniam (University of Rochester)

Ligero is a simple sub-linear argument protocol for NP based on the MPC-in-the-head paradigm whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient (somewhat) STARKs that do not require a trusted setup or public-key cryptography.

We will give a general transformation from MPC protocols to interactive PCPs and then provide a instantiation that yields the concretely efficient result.