UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin

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. Green open access

[thumbnail of Groth_764.pdf]
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
Downloads since deposit
577Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item