CryptoDB
CDS Composition of Multi-Round Protocols
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| 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. |
BibTeX
@inproceedings{crypto-2024-34237,
title={CDS Composition of Multi-Round Protocols},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68400-5_12},
author={Masayuki Abe and Andrej Bogdanov and Miyako Ohkubo and Alon Rosen and Zehua Shang and Mehdi Tibouchi},
year=2024
}