Online/Offline OR Composition of Sigma Protocols

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Proofs of partial knowledge allow a prover to prove knowledge of witnesses for k out of n instances of NP languages. Cramer, Schoenmakers and Damgård [10] provided an efficient construction of a 3-round public-coin witness-indistinguishable (kn)-proof of partial knowledge for any NP language, by cleverly combining n executions of Σ-protocols for that language. This transform assumes that all n instances are fully specified before the proof starts, and thus directly rules out the possibility of choosing some of the instances after the first round.

Very recently, Ciampi et al. [6] provided an improved transform where one of the instances can be specified in the last round. They focus on (1, 2)-proofs of partial knowledge with the additional feature that one instance is defined in the last round, and could be adaptively chosen by the verifier. They left as an open question the existence of an efficient (1, 2)-proof of partial knowledge where no instance is known in the first round. More in general, they left open the question of constructing an efficient (k, n)-proof of partial knowledge where knowledge of all n instances can be postponed. Indeed, this property is achieved only by inefficient constructions requiring NP reductions [19].

In this paper we focus on the question of achieving adaptive-input proofs of partial knowledge. We provide through a transform the first efficient construction of a 3-round public-coin witness-indistinguishable (k, n)-proof of partial knowledge where all instances can be decided in the third round. Our construction enjoys adaptive-input witness indistinguishability. Additionally, the proof of knowledge property remains also if the adversarial prover selects instances adaptively at last round as long as our transform is applied to a proof of knowledge belonging to the widely used class of proofs of knowledge described in [9, 21]. Since knowledge of instances and witnesses is not needed before the last round, we have that the first round can be precomputed and in the online/offline setting our performance is similar to the one of [10].

Our new transform relies on the DDH assumption (in contrast to the transforms of [6, 10] that are unconditional).
Original languageEnglish
Title of host publicationAdvances in Cryptology -- EUROCRYPT 2016
EditorsMarc Fischlin, Jean-Sébastien Coron
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages30
ISBN (Electronic)978-3-662-49896-5
ISBN (Print)978-3-662-49895-8
Publication statusPublished - 2016
Event35th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Vienna, Austria
Duration: 8 May 201612 May 2016

Publication series

NameLecture Notes in Computer Science


Conference35th Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated titleEuropcrypt 2016
Internet address


Dive into the research topics of 'Online/Offline OR Composition of Sigma Protocols'. Together they form a unique fingerprint.

Cite this