Paper 2022/1419

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

Aarushi Goel, NTT Research
Mathias Hall-Andersen, Aarhus University
Gabriel Kaptchuk, Boston University
Nicholas Spooner, University of Warwick
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Zero-knowlege sublinear proofs disjunctions
Contact author(s)
aarushi goel @ ntt-research com
ma @ cs au dk
kaptchuk @ bu edu
Nicholas Spooner @ warwick ac uk
History
2022-10-24: approved
2022-10-19: received
See all versions
Short URL
https://ia.cr/2022/1419
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1419,
      author = {Aarushi Goel and Mathias Hall-Andersen and Gabriel Kaptchuk and Nicholas Spooner},
      title = {Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1419},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1419}},
      url = {https://eprint.iacr.org/2022/1419}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.