Folding/Accumulation schemes are a powerful tool for building scalable proof systems. However, standard approaches for leveraging folding schemes, such as IVCs or PCDs, require embedding hash functions (modeled as random oracles) into recursive circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding schemes, and introduce Symphony, the first proving paradigm that leverages folding schemes as a black box without embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, and plausibly post-quantum secure, with polylogarithmic proof size and verification. The (low-memory) prover requires O(log log n) passes of the input data and its computation is dominated by committing to the input witnesses. A core component of our construction is a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot. 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 fit for large-scale applications such as zkVM and verifiable machine learning.
Note: Major revision of Section 1 and Section 3.4
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}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。