CDS Composition of Multi-round Protocols

We revisit the Cramer, Damgård, Schoenmakers (CDS) approach for composing sigma protocols, and adapt it to a setting in which the underlying protocols have multiple rounds of interaction. The goal of CDS composition is to prove compound NP-relations by combining multiple “atomic” proof systems. Its key feature is that it interacts with the atomic proofs in a generic fashion, enabling simpler and more efficient implementation. Recent developments in multi-round protocols call for the adaptation of CDS composition beyond its original scope, which not only was restricted to three-move protocols but in fact fails in the multi-round case, as well as in the composition of so-called k-special sound proofs. We propose a new method for multi-round composition in the plain model, in a soundness preserving way and with an “offline” zero-knowledge simulation property. The need for handling arbitrary monotone access structures in \(\textsf{mNC}^1\) , which is all Boolean function families represented by polynomial-size formulas over some fixed complete basis, leads us to identify a complexity theoretic problem of independent interest. Prior to our work, multi-round composition was either restricted to the random oracle model, or worked only for argument systems, and moreover required heavy “online” zero-knowledge simulation.