Abstract
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 (k, n)-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).
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 language | English |
|---|---|
| Title of host publication | Advances in Cryptology -- EUROCRYPT 2016 |
| Editors | Marc Fischlin, Jean-Sébastien Coron |
| Place of Publication | Berlin, Heidelberg |
| Publisher | Springer |
| Pages | 63-92 |
| Number of pages | 30 |
| ISBN (Electronic) | 978-3-662-49896-5 |
| ISBN (Print) | 978-3-662-49895-8 |
| DOIs | |
| Publication status | Published - 2016 |
| Event | 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Vienna, Austria Duration: 8 May 2016 → 12 May 2016 http://ist.ac.at/eurocrypt2016/index.html |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 9666 |
Conference
| Conference | 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques |
|---|---|
| Abbreviated title | Europcrypt 2016 |
| Country/Territory | Austria |
| City | Vienna |
| Period | 8/05/16 → 12/05/16 |
| Internet address |