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

##### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1419

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.