LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems
Binyi Chen
Abstract:
Folding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed, such as Nova, Supernova, Hypernova, Protostar, and others. 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. LatticeFold supports folding low-degree relations, such as R1CS, as well as high-degree relations, such as CCS. 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 as performant as Hypernova, while providing post-quantum security. This is a joint work with Prof. Dan Boneh.
Bio:
Binyi Chen is a postdoc researcher at Stanford University. Previously, he was the Chief Cryptographer at Espresso Systems. He is broadly interested in post-quantum cryptography and blockchain technology. His recent research has focused on building concretely efficient proof systems for exceptionally large computation statements. He is the recipient of the Best Paper Award at Eurocrypt 2017. He received his PhD from UC Santa Barbara in 2019. From 2018-2019, he was a visiting PhD student at the University of Washington.