You are looking at a specific version 20210331:183502 of this paper. See the latest version.

Paper 2021/422

Stacking Sigmas: A Framework to Compose $\Sigma$-Protocols for Disjunctions

Aarushi Goel and Matthew Green and Mathias Hall-Andersen and Gabriel Kaptchuk

Abstract

A sequence of recent works by Heath and Kolesnikov have explored modifying existing interactive protocols for privacy-preserving computation (secure multiparty computation, private function evaluation and zero-knowledge proofs) to be more communication efficient when applied to disjunctive statements, such that the cost only depends on the size of the largest clause in the disjunction. In this work, we focus on the specific case of zero-knowledge proofs for disjunctive statements. We design a general framework that compiles a large class of unmodified $\Sigma$-protocols, each for an individual statement, into a new $\Sigma$-protocol that proves a disjunction of these statements. Our framework can be used both when each clause is proved with the same $\Sigma$-protocol and when different $\Sigma$-protocols are used for different clauses. The resulting $\Sigma$-protocol is concretely efficient and has communication complexity proportional to the communication required by the largest clause, with additive terms that are only logarithmic in the number of clauses. We show that our compiler can be applied to many well-known $\Sigma$-protocols, including classical protocols (e.g. Schnorr and Guillou-Quisquater) and modern MPC-in-the-head protocols such as the recent work of Katz, Kolesnikov and Wang and the Ligero protocol of Ames et al. Finally, since all of the protocols in our class can be made non-interactive in the random oracle model using the Fiat-Shamir transform, our result yields the first non-interactive zero-knowledge protocol for disjunctions where the communication only depends on the size of the largest clause.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Zero-knowledgeSigma protocolsDisjunctionsinteractive proofs
Contact author(s)
aarushig @ cs jhu edu
mgreen @ cs jhu edu
ma @ cs au dk
kaptchuk @ bu edu
History
2023-01-09: last of 6 revisions
2021-03-31: received
See all versions
Short URL
https://ia.cr/2021/422
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.