Paper 2025/1905
Symphony: Scalable SNARKs in the Random Oracle Model from Lattice-Based High-Arity Folding
, Stanford UniversityAbstract
Folding schemes are a powerful tool for building scalable proof systems. However, existing folding-based SNARKs require embedding hash functions (modeled as random oracles) into SNARK circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding, and introduce Symphony, the first folding-based SNARK that avoids embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, streaming-friendly, plausibly post-quantum secure, with polylogarithmic proof size and verification, and a prover dominated by committing to the input witnesses. As part of our construction, we introduce a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot, which may be of independent interest. Furthermore, we design a generic compiler that converts a folding scheme into a SNARK without embedding the Fiat-Shamir circuit into proven statements. Our evaluation shows its concrete efficiency, making Symphony a promising candidate for applications such as zkVM, proof of learning, and post-quantum aggregate signatures.
Note: A self-contained description of the monomial check protocol + more related work
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Succinct Proof SystemsFoldingLattice-based Cryptography
- Contact author(s)
- binyi @ cs stanford edu
- History
- 2026-02-11: last of 2 revisions
- 2025-10-12: received
- See all versions
- Short URL
- https://ia.cr/2025/1905
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1905,
author = {Binyi Chen},
title = {Symphony: Scalable {SNARKs} in the Random Oracle Model from Lattice-Based High-Arity Folding},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1905},
year = {2025},
url = {https://eprint.iacr.org/2025/1905}
}
