This property has been instrumental in constructing round-efficient protocols for various tasks [KO04,DPV04,YZ07,SV12]. In all such constructions, the WI proofs are used to prove the OR composition of statements that are specified at different stages of the main protocol. The special property of LS is used precisely to allow a player of the main protocol to start a proof, even if only one of the statements of the OR relation is available, thus saving rounds of communication.
If, on the one hand, the usage of LS saves rounds, on the other hand it necessarily requires NP reductions to Graph Hamiltonicity. As such, even if each of the statements to be proved in the main protocol admits an efficient Sigma-protocol (e.g., if the statement consists in proving knowledge of a committed value or of a secret key), the reduced round complexity is paid for with a loss of efficiency. Hence, round-efficient constructions that rely on LS are typically computationally inefficient. A natural question is why one would go through the NP reduction to use LS, instead of composing the Sigma-protocols using the OR-composition technique introduced by Cramer, Damgard and Schoenmakers (CDS) in [CDS94]. The answer is that the CDS technique requires both statements to be available at the beginning of the protocol. Due to this limitation, constructions that use the CDS technique have in some cases a worse round complexity than the ones based on LS.
In this paper we introduce a new OR-composition technique for Sigma-protocols that needs only one statement to be fixed when the proof begins. This seemingly weaker property is sufficient to replace the use of LS in many applications that do not need both theorems to be undefined when the proof starts.
In fact, we show how the new OR composition technique can directly improve the round complexity of the efficient perfect quasi-polynomial time simulatable argument system of Pass [Pas03] (from four to three rounds) and of efficient resettable WI arguments (from five to four rounds).
Our OR-composition technique can not compose any arbitrary pair of Sigma-protocols. Nevertheless, we provide a precise classification of the Sigma-protocols that can be composed and show that all the widely used Sigma-protocols can be composed with our technique.
Category / Keywords: cryptographic protocols / Sigma protocols, round efficiency Original Publication (with minor differences): IACR-TCC-2016 Date: received 14 Aug 2015, last revised 18 Oct 2015 Contact author: ivan visconti at gmail com Available format(s): PDF | BibTeX Citation Note: Part of the results of this paper will appear in TCC 2016-A. Version: 20151018:233932 (All versions of this report) Short URL: ia.cr/2015/810 Discussion forum: Show discussion | Start new discussion