Groth, J;
Kohlweiss, M;
(2015)
One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin.
In: Oswald, E and Fischlin, M, (eds.)
Advances in Cryptology - EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II.
(pp. pp. 253-280).
Springer Berlin Heidelberg: Berlin, Germany.
Preview |
Text
Groth_764.pdf Download (430kB) | Preview |
Abstract
We construct a 3-move public coin special honest verifier zero-knowledge proof, a so-called Sigma-protocol, for a list of commitments having at least one commitment that opens to 0. It is not required for the prover to know openings of the other commitments. The proof system is efficient, in particular in terms of communication requiring only the transmission of a logarithmic number of commitments. We use our proof system to instantiate both ring signatures and zerocoin, a novel mechanism for bitcoin privacy. We use our Sigma-protocol as a (linkable) ad-hoc group identification scheme where the users have public keys that are commitments and demonstrate knowledge of an opening for one of the commitments to unlinkably identify themselves (once) as belonging to the group. Applying the Fiat-Shamir transform on the group identification scheme gives rise to ring signatures, applying it to the linkable group identification scheme gives rise to zerocoin. Our ring signatures are very small compared to other ring signature schemes and we only assume the users’ secret keys to be the discrete logarithms of single group elements so the setup is quite realistic. Similarly, compared with the original zerocoin protocol we only rely on a weak cryptographic assumption and do not require a trusted setup. A third application of our Sigma protocol is an efficient proof of membership of a secret committed value belonging to a public list of values.
| Type: | Proceedings paper |
|---|---|
| Title: | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin |
| Event: | 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques |
| ISBN-13: | 9783662468029 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-662-46803-6_9 |
| Publisher version: | http://dx.doi.org/10.1007/978-3-662-46803-6 |
| Language: | English |
| Additional information: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-46803-6_9. |
| Keywords: | Sigma-protocol, Zero-knowledge, Disjunctive proof, Ring signature, Zerocoin, Membership proof |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1502142 |
Archive Staff Only
 |
View Item |
