International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions

Authors:
Aarushi Goel , NTT Research
Mathias Hall-Andersen , Aarhus University
Gabriel Kaptchuk , Boston University
Nicholas Spooner , University of Warwick
Download:
DOI: 10.1007/978-3-031-30617-4_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
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.
BibTeX
@inproceedings{eurocrypt-2023-32950,
  title={Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30617-4_12},
  author={Aarushi Goel and Mathias Hall-Andersen and Gabriel Kaptchuk and Nicholas Spooner},
  year=2023
}