The Library
Speed-stacking : fast sublinear zero-knowledge proofs for disjunctions
Tools
Goel, Aarushi, Hall-Andersen, Mathias, Kaptchuk, Gabriel and Spooner, Nicholas (2023) Speed-stacking : fast sublinear zero-knowledge proofs for disjunctions. In: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23–27 Apr 2023. Published in: Advances in Cryptology – EUROCRYPT 2023, 14005 pp. 347-378. ISBN 9783031306167. doi:10.1007/978-3-031-30617-4_12 ISSN 0302-9743.
|
PDF
WRAP-Speed-Stacking-Spooner-2023.pdf - Accepted Version - Requires a PDF viewer. Download (1883Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-031-30617-4_12
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 Σ-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 ` clauses, each of size N, with only O((N + `)· polylog(N)) computation, versus O(`N · 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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computer science -- Mathematics , Computer algorithms , Computational complexity, Cryptography | ||||||
Series Name: | Lecture Notes in Computer Science | ||||||
Journal or Publication Title: | Advances in Cryptology – EUROCRYPT 2023 | ||||||
Publisher: | Springer | ||||||
ISBN: | 9783031306167 | ||||||
ISSN: | 0302-9743 | ||||||
Book Title: | Advances in Cryptology – EUROCRYPT 2023 | ||||||
Official Date: | 15 April 2023 | ||||||
Dates: |
|
||||||
Volume: | 14005 | ||||||
Page Range: | pp. 347-378 | ||||||
DOI: | 10.1007/978-3-031-30617-4_12 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 14 June 2023 | ||||||
Date of first compliant Open Access: | 15 April 2024 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Lyon, France | ||||||
Date(s) of Event: | 23–27 Apr 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year