TY - GEN
T1 - Zero-Knowledge Proofs for Set Membership
T2 - 25th International Conference on Financial Cryptography and Data Security, FC 2021
AU - Benarroch, Daniel
AU - Campanelli, Matteo
AU - Fiore, Dario
AU - Gurkan, Kobi
AU - Kolonelos, Dimitris
N1 - Funding Information:
Acknowledgements. Research leading to these results has been partially supported by the Spanish Government under projects SCUM (ref. RTI2018-102043-B-I00), CRYPTOEPIC (ref. EUR2019-103816), and SECURITAS (ref. RED2018-102321-T), by the Madrid Regional Government under project BLOQUES (ref. S2018/TCS-4339), and by research grants from Protocol Labs, and Nomadic Labs and the Tezos Foundation. Matteo Campanelli worked on this project as a post-doc at the IMDEA Software Institute.
Funding Information:
Research leading to these results has been partially supported by the Spanish Government under projects SCUM (ref. RTI2018-102043-B-I00), CRYPTOEPIC (ref. EUR2019-103816), and SECURITAS (ref. RED2018-102321-T), by the Madrid Regional Government under project BLOQUES (ref. S2018/TCS-4339), and by research grants from Protocol Labs, and Nomadic Labs and the Tezos Foundation. Matteo Campanelli worked on this project as a post-doc at the IMDEA Software Institute.
Publisher Copyright:
© 2021, International Financial Cryptography Association.
PY - 2021
Y1 - 2021
N2 - We consider the problem of proving in zero knowledge that an element of a public set satisfies a given property without disclosing the element, i.e., for some u, “ u∈ S and P(u) holds”. This problem arises in many applications (anonymous cryptocurrencies, credentials or whitelists) where, for privacy or anonymity reasons, it is crucial to hide certain data while ensuring properties of such data. We design new modular and efficient constructions for this problem through new commit-and-prove zero-knowledge systems for set membership, i.e. schemes proving u∈ S for a value u that is in a public commitment cu. We also extend our results to support non-membership proofs, i.e. proving u∉ S. Being commit-and-prove, our solutions can act as plug-and-play modules in statements of the form “ u∈ S and P(u) holds” by combining our set (non-)membership systems with any other commit-and-prove scheme for P(u). Also, they work with Pedersen commitments over prime order groups which makes them compatible with popular systems such as Bulletproofs or Groth16. We implemented our schemes as a software library, and tested experimentally their performance. Compared to previous work that achieves similar properties—the clever techniques combining zkSNARKs and Merkle Trees in Zcash—our solutions offer more flexibility, shorter public parameters and 3.7 × – 30 × faster proving time for a set of size 264.
AB - We consider the problem of proving in zero knowledge that an element of a public set satisfies a given property without disclosing the element, i.e., for some u, “ u∈ S and P(u) holds”. This problem arises in many applications (anonymous cryptocurrencies, credentials or whitelists) where, for privacy or anonymity reasons, it is crucial to hide certain data while ensuring properties of such data. We design new modular and efficient constructions for this problem through new commit-and-prove zero-knowledge systems for set membership, i.e. schemes proving u∈ S for a value u that is in a public commitment cu. We also extend our results to support non-membership proofs, i.e. proving u∉ S. Being commit-and-prove, our solutions can act as plug-and-play modules in statements of the form “ u∈ S and P(u) holds” by combining our set (non-)membership systems with any other commit-and-prove scheme for P(u). Also, they work with Pedersen commitments over prime order groups which makes them compatible with popular systems such as Bulletproofs or Groth16. We implemented our schemes as a software library, and tested experimentally their performance. Compared to previous work that achieves similar properties—the clever techniques combining zkSNARKs and Merkle Trees in Zcash—our solutions offer more flexibility, shorter public parameters and 3.7 × – 30 × faster proving time for a set of size 264.
UR - http://www.scopus.com/inward/record.url?scp=85118946982&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-64322-8_19
DO - 10.1007/978-3-662-64322-8_19
M3 - Article in proceedings
AN - SCOPUS:85118946982
SN - 9783662643211
T3 - Lecture Notes in Computer Science
SP - 393
EP - 414
BT - Financial Cryptography and Data Security
A2 - Borisov, Nikita
A2 - Diaz, Claudia
PB - Springer
Y2 - 1 March 2021 through 5 March 2021
ER -