International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 14 August 2015

Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, Ivan Visconti
ePrint Report ePrint Report
In [LS90] Lapidot and Shamir provide a 3-round witness-indistinguishable (WI) proof of knowledge for Graph Hamiltonicity (the LS proof) with a special property: the prover uses the statement to be proved only in the last round.

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 proofs 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 proofs 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 proofs are typically inefficient.

A natural question is why one would go through the NP-reduction to use LS proof, instead of composing the Sigma-protocols using the OR composition technique introduced 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 proofs.

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 proofs 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 perfectly simulatable argument of [Pass03] (from four to three rounds) and of efficient resettable WI arguments (from five to four rounds).

Our OR 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.

Expand

Additional news items may be found on the IACR news page.