Paper 2015/810

Improved OR Composition of Sigma-Protocols

Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti


In [CDS94] Cramer, Damgård and Schoenmakers (CDS) devise an OR-composition technique for Sigma-protocols that allows to construct highly-efficient proofs for compound statements. Since then, such technique has found countless applications as building block for designing efficient protocols. Unfortunately, the CDS OR-composition technique works only if both statements are fixed before the proof starts. This limitation restricts its usability in those protocols where the theorems to be proved are defined at different stages of the protocol, but, in order to save rounds of communication, the proof must start even if not all theorems are available. Many round-optimal protocols ([KO04,DPV04,YZ07,SV12]) crucially need such property to achieve round-optimality, and, due to the inapplicability of CDS's technique, are currently implemented using proof systems that requires expensive NP reductions, but that allow the proof to start even if no statement is defined a.k.a., LS proofs from Lapidot-Shamir [LS90]). In this paper we show an improved OR-composition technique for Sigma-protocols, that requires only one statement to be fixed when the proof starts, while the other statement can be defined in the last round. This seemingly weaker property is sufficient for the applications, where typically one of the theorems is fixed before the proof starts. Concretely, we show how our new OR-composition technique can directly improve the round complexity of the efficient perfect quasi-polynomial time simulatable argument system of Pass [Pass03] (from four to three rounds) and of efficient resettable WI arguments (from five to four rounds).

Note: Part of the results of this paper will appear in TCC 2016-A.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2016
Sigma protocolsround efficiency
Contact author(s)
ivan visconti @ gmail com
2015-12-17: last of 5 revisions
2015-08-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Ciampi and Giuseppe Persiano and Alessandra Scafuro and Luisa Siniscalchi and Ivan Visconti},
      title = {Improved OR Composition of Sigma-Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2015/810},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.