Paper 2024/257

LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems

Dan Boneh, Stanford University
Binyi Chen, Stanford University

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.

Available format(s)
Cryptographic protocols
Publication info
Succinct Proof SystemsIVC/PCDFoldingLattice-based Cryptography
Contact author(s)
dabo @ cs stanford edu
binyi @ cs stanford edu
2024-03-06: revised
2024-02-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dan Boneh and Binyi Chen},
      title = {{LatticeFold}: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2024/257},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.