International Association for Cryptologic Research

International Association
for Cryptologic Research


CDS Composition of Multi-Round Protocols

Masayuki Abe , NTT Social Informatics Laboratories
Andrej Bogdanov , University of Ottawa
Miyako Ohkubo , NICT
Alon Rosen , Bocconi University and Reichman University
Zehua Shang , Kyoto University
Mehdi Tibouchi , NTT Social Informatics Laboratories
Search ePrint
Search Google
Conference: CRYPTO 2024
Abstract: We revisit the Cramer, Damg{\aa}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 $\mathsf{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.
  title={CDS Composition of Multi-Round Protocols},
  author={Masayuki Abe and Andrej Bogdanov and Miyako Ohkubo and Alon Rosen and Zehua Shang and Mehdi Tibouchi},