LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems
Binyi Chen (Stanford)
Monday, May 20th 2024, 2-3pm
Abstract:
SNARKs stands for succinct proofs for NP statements, and it has wide applications in theory/practice. Folding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed. However, all of them rely on an additively homomorphic commitment scheme based on discrete log, and are therefore not post-quantum secure. In this work we present LatticeFold, the first lattice-based folding protocol based on the Module SIS problem. This folding protocol naturally leads to an efficient recursive lattice-based SNARK and an efficient PCD scheme. The key challenge is to construct a secure folding protocol that works with the Ajtai commitment scheme. The difficulty is ensuring that extracted witnesses are low norm through many rounds of folding. We present a novel technique using the sumcheck protocol to ensure that extracted witnesses are always low norm no matter how many rounds of folding are used. Our evaluation of the final proof system suggests that it is highly performant compared to existing folding schemes while providing plausible post-quantum security.
This is a joint work with Dan Boneh.
Speaker information:
Binyi Chen is a postdoc researcher at Stanford University. Previously, he was the Chief Cryptographer at Espresso Systems. He received his PhD from UC Santa Barbara in 2019. From 2018-2019, he was a visiting PhD student at University of Washington.
He is broadly interested in post-quantum cryptography and blockchain technology. His recent research has focused on building concretely efficient succinct proof systems for large NP statements. He is the recipient of the Best Paper Award at Eurocrypt 2017 and the co-inventor of a few succinct proof systems with broad industry impact, including HyperPlonk and Protostar.