Lattices, Folding, & Symphony with Binyi Chen

Anna Rose introduces Bin Ye Chen, a postdoctoral researcher at Stanford University, to discuss his work on Lattice Fold, Lattice Fold Plus, and the Symphony project. Bin Ye explains that his folding research began in 2023, focusing on the potential of lattices as a replacement for Peterson hashes, highlighting both the benefits and limitations of lattice-based folding. The Symphony project explores new techniques, complementing the recently released ZK Whiteboard Sessions module on Lattice Fold.

Bin Ye reflects on advancements in post-quantum folding schemes, addressing open problems and emphasizing the promising direction of lattice-based approaches. He categorizes earlier folding schemes, such as Nova and Halo, as first-generation, noting their vulnerabilities to quantum attacks due to reliance on discrete log assumptions. The transition to lattice-based commitments is deemed necessary, as recent work has shown that folding can be achieved without homomorphic commitments.

The conversation touches on ITI commitments, introduced by A.J. Ta, based on the shortest integer solution assumption, leading to effective constructions for collision-resistant hash functions. Bin Ye compares hash-based schemes, which are mature and believed to be post-quantum secure, with lattice-based schemes, which offer more algebraic structure and efficient verification processes. While hash-based schemes currently dominate in terms of maturity for SNARKs, he concludes that lattice-based folding schemes show significant promise due to their competitive efficiency and smaller verification complexity.

Leslie Kendrick raises the question of whether integrating lattices with folding necessitates a complete rethinking of the approach. Bin Ye responds that the challenges are substantial, particularly in managing norm constraints during folding. Despite these challenges, he notes similarities between lattice and Peterson-based schemes, particularly in their use of homomorphic commitments. The discussion also includes the goals of designing folding systems, focusing on trade-offs in speed and cost for provers and verifiers.

Folding condenses multiple MP statements into a single statement, exemplified by simplifying the Fibonacci sequence into smaller chunks. It is distinct from parallelization, focusing on mathematically reducing large problems rather than dividing them. Folding is promising for scalable computation due to its simplicity, transformation potential into succinct proof systems, and streaming friendliness, allowing proofs to begin during computation rather than after completion.

The historical context of recursive SNARKs, proposed by Paul Valiant in 2008, highlights their evolution from theoretical constructs to practical applications, particularly after the Halo paper and subsequent works that simplified folding verification. Recent advancements include the Man-Groove paper, which enables the transformation of arbitrary computations into uniform computations suitable for folding. The introduction of lattices aims to improve prover efficiency, with initial lattice-based commitments optimized for polynomial ring settings, reducing complexity from quadratic to sub-linear.

Challenges remain, particularly with elliptic curve commitments complicating recursive verification and increasing circuit sizes. First-generation lattice folds require the original witness to be broken into multiple lower norm vectors, increasing the prover's workload, while ring-based commitments are more efficient but still lag behind elliptic curve schemes in overall speed. The connection between range proofs and lookup arguments has been clarified, with various techniques for range proofs in lattice settings, including decomposition and monomial encoding.

The Neo paper introduces a new lattice-based folding scheme that combines projection and monomial encoding, enhancing speed and simplicity while supporting small fields and more natural constraint encoding. Despite improvements, there are trade-offs regarding prover and verifiable overhead compared to elliptic curve-based folding schemes. The Fiers-Chamier circuit is essential for transforming interactive protocols into non-interactive ones by generating verifiable challenges through a hash function on the transcript. However, in the lattice setting, the transcript size is larger due to increased attack commitments, raising concerns about the high complexity of Fiers-Chamier hashing.

The Shortest Integer Solution (SIS) problem is a key challenge in lattice cryptography, where finding a small vector that satisfies a given matrix equation is computationally difficult. This difficulty underpins the security of lattice cryptography, with the assumption that quantum computers cannot easily solve the SIS problem. Ongoing research continues to test the robustness of these assumptions, particularly in the context of lattice folding, where a shift in approach has been noted. Decomposing before folding enhances control over norms, and the introduction of range proofs has further advanced lattice applications.

Range proofs, inspired by protocols like Labrador and Sump Check, offer sub-linear verification complexity, making them suitable for folding applications. While Labrador has linear verification complexity, Lattice Fold integrates various research threads to optimize these processes. Recent developments in folding schemes have highlighted issues with proving Fiers-Chamier circuits, which tend to be large due to their simplicity. A recent paper presents a significant attack on the GKR-based proof system, revealing vulnerabilities when hash functions are instantiated in real-world scenarios.

The new work titled "Symphony" proposes a novel folding framework that harmonizes previous research and allows for high-arity folding, enabling the combination of many statements into one. This approach effectively reduces verification complexity, making large-scale folding feasible by eliminating reliance on Fiers-Chamier circuits. The conversation centers on the development of a new proof system that enhances efficiency and security by utilizing a "commit and proof" snark, which reduces the attack surface for KRS-like attacks.

The discussion highlights the flexibility of commit and proof snarks, noting that various types can be employed. While current lattice-based snarks face challenges due to high verification complexity, advancements in lattice-based folding schemes are being explored. The conversation also touches on the scalability of these folding schemes for applications requiring proofs of extensive computations, such as billions of RISC-V instructions. The folding process is described as compressing a matrix into a single statement, with potential for higher dimensions beyond the current two-fold approach.

Additionally, the speakers reflect on their academic journeys, expressing admiration for colleagues and discussing their interests in obfuscation and its implications in cryptography. They emphasize a preference for research that balances mathematical depth with practical applications, particularly in areas like SNARKs and post-quantum cryptography. The guest raises questions about the potential for a fully succinct lattice-based SNARK that could outperform hash-based SNARKs, expressing optimism about future advancements in lattice-based SNARKs.