Paper 2021/422
Stacking Sigmas: A Framework to Compose $\Sigma$Protocols for Disjunctions
Abstract
ZeroKnowledge (ZK) Proofs for disjunctive statements have been a focus of a long line of research. Classical results such as Cramer {\em et al.} [CRYPTO'94] and Abe {\em et al.} [AC'02] design generic compilers that transform certain classes of ZK proofs into ZK proofs for disjunctive statements. However, communication complexity of the resulting protocols in these results ends up being proportional to the complexity of proving all clauses in the disjunction. More recently, Heath {\em et al.} [EC'20] exploited special properties of garbled circuits to construct efficient ZK proofs for disjunctions, where the proof size is only proportional to the length of the largest clause in the disjunction. However, these techniques do not appear to generalize beyond garbled circuits. In this work, we focus on achieving the best of both worlds. We design a \textit{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 wellknown $\Sigma$protocols, including classical protocols (\emph{e.g.} Schnorr [JC'91] and GuillouQuisquater [CRYPTO'88]) and modern MPCinthehead protocols such as the recent work of Katz, Kolesnikov and Wang [CCS'18] and the Ligero protocol of Ames {\em et al.} [CCS'17]. Finally, since all of the protocols in our class can be made noninteractive in the random oracle model using the FiatShamir transform, our result yields the first generic noninteractive zeroknowledge protocol for disjunctions where the communication only depends on the size of the largest clause.
Note: This revised version contains the following updates: (1) an updated definition of partially binding commitments which was revised based on the issues observed by Avitabile et al. [ESORICS 22], (2) a sketch of an optimized construction for koutofl proofs of partial knowledge, which was inspired from the construction proposed by Avitabile et al. [ESORICS 22] and (3) an optimized construction of 1outof2^q partially binding vector commitments that further simplifies the presentation of our compiler. We have also updated the definition of hiding for the partially binding vector commitments such that they formally meet their intuitive properties.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in EUROCRYPT 2022
 Keywords
 ZeroknowledgeSigma protocolsDisjunctionsinteractive proofs
 Contact author(s)

aarushig @ cs jhu edu
mgreen @ cs jhu edu
ma @ cs au dk
kaptchuk @ bu edu  History
 20230109: last of 6 revisions
 20210331: received
 See all versions
 Short URL
 https://ia.cr/2021/422
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/422, author = {Aarushi Goel and Matthew Green and Mathias HallAndersen and Gabriel Kaptchuk}, title = {Stacking Sigmas: A Framework to Compose $\Sigma$Protocols for Disjunctions}, howpublished = {Cryptology ePrint Archive, Paper 2021/422}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/422}}, url = {https://eprint.iacr.org/2021/422} }