Welcome to the resource topic for 2022/1419
Title:
Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions
Authors: Aarushi Goel, Mathias Hall-Andersen, Gabriel Kaptchuk, Nicholas Spooner
Abstract:Building on recent disjunctive compilers for zero-knowledge (e.g. Goel et al. [EUROCRYPT’22]) we propose a new compiler that, when applied to sublinear-sized proofs, can result in sublinear-size disjunctive zero-knowledge with sublinear proving times (without meaningfully increasing proof sizes). Our key observation is that simulation in sublinear-size zero-knowledge proof systems can be much faster (both concretely and asymptotically) than the honest prover. We study applying our compiler to two classes of O(\log n)-round protocols: interactive oracle proofs, specifically Aurora [EUROCRYPT’19] and Fractal [EUROCRYPT’20], and folding arguments, specifically Compressed \Sigma-protocols [CRYPTO’20, CRYPTO’21] and Bulletproofs [S&P’18]. This study validates that the compiler can lead to significant savings. For example, applying our compiler to Fractal enables us to prove a disjunction of \ell clauses, each of size N, with only O((N+\ell) \cdot \text{polylog}(N)) computation, versus O(\ell N \cdot \text{polylog}(N)) when proving the disjunction directly. We also find that our compiler offers a new lens through which to understand zero-knowledge proofs, evidenced by multiple examples of protocols with the same “standalone” complexity that each behave very differently when stacked.
ePrint: https://eprint.iacr.org/2022/1419
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .