User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs

Primary tabs

Libert, Benoît [UCL] Yung, M.

Introduced by Micali, Rabin and Kilian (MRK), the basic primitive of zero-knowledge sets (ZKS) allows a prover to commit to a secret set S so as to be able to prove statements such as x isin S or x notin S. Chase et al. showed that ZKS protocols are underlain by a cryptographic primitive termed mercurial commitment. A (trapdoor) mercurial commitment has two commitment procedures. At committing time, the committer can choose not to commit to a specific message and rather generate a dummy value which it will be able to softly open to any message without being able to completely open it. Hard commitments, on the other hand, can be hardly or softly opened to only one specific message. At Eurocrypt 2008, Catalano, Fiore and Messina (CFM) introduced an extension called trapdoor q-mercurial commitment (qTMC), which allows committing to a vector of q messages. These qTMC schemes are interesting since their openings w.r.t. specific vector positions can be short (ideally, the opening length should not depend on q), which provides zero-knowledge sets with much shorter proofs when such a commitment is combined with a Merkle tree of arity q. The CFM construction notably features short proofs of non-membership as it makes use of a qTMC scheme with short soft openings. A problem left open is that hard openings still have size 0(q), which prevents proofs of membership from being as compact as those of non-membership. In this paper, we solve this open problem and describe a new qTMC scheme where hard and short position-wise openings, both, have constant size. We then show how our scheme is amenable to constructing independent zero-knowledge sets (i.e., ZKS's that prevent adversaries from correlating their set to the sets of honest provers, as denned by Gennaro and Micali). Our solution retains the short proof property for this important primitive as well.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès restreint
Publication date 2010
Conference "Theory of Cryptography. 7th Theory of Cryptography Conference, TCC 2010", Zurich, Switzerland (9-11 February 2010)
Peer reviewed yes
Host document Micciancio, D.; ; "Theory of Cryptography. 7th Theory of Cryptography Conference, TCC 2010"- p. 499-517 (ISBN : 978-3-642-11798-5)
Publisher Springer-verlag
Affiliation UCL - SST/ICTM - Institute for Information and Communication. Technologies, Electronics and Applied Mathematics
Links
  1. Ateniese Giuseppe, de Medeiros Breno, Identity-Based Chameleon Hash and Applications, Financial Cryptography (2004) ISBN:9783540224204 p.164-180, 10.1007/978-3-540-27809-2_19
  2. Barreto Paulo S. L. M., Naehrig Michael, Pairing-Friendly Elliptic Curves of Prime Order, Selected Areas in Cryptography (2006) ISBN:9783540331087 p.319-331, 10.1007/11693383_22
  3. Boneh Dan, Boyen Xavier, Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles, Advances in Cryptology - EUROCRYPT 2004 (2004) ISBN:9783540219354 p.223-238, 10.1007/978-3-540-24676-3_14
  4. Boneh Dan, Boyen Xavier, Goh Eu-Jin, Hierarchical Identity Based Encryption with Constant Size Ciphertext, Lecture Notes in Computer Science (2005) ISBN:9783540259107 p.440-456, 10.1007/11426639_26
  5. Boneh Dan, Gentry Craig, Waters Brent, Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys, Advances in Cryptology – CRYPTO 2005 (2005) ISBN:9783540281146 p.258-275, 10.1007/11535218_16
  6. Camenisch Jan, Kohlweiss Markulf, Soriente Claudio, An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials, Public Key Cryptography – PKC 2009 (2009) ISBN:9783642004674 p.481-500, 10.1007/978-3-642-00468-1_27
  7. Canetti Ran, Dodis Yevgeniy, Pass Rafael, Walfish Shabsi, Universally Composable Security with Global Setup, Theory of Cryptography ISBN:9783540709350 p.61-85, 10.1007/978-3-540-70936-7_4
  8. Catalano Dario, Dodis Yevgeniy, Visconti Ivan, Mercurial Commitments: Minimal Assumptions and Efficient Constructions, Theory of Cryptography (2006) ISBN:9783540327318 p.120-144, 10.1007/11681878_7
  9. Catalano Dario, Fiore Dario, Messina Mariagrazia, Zero-Knowledge Sets with Short Proofs, Advances in Cryptology – EUROCRYPT 2008 ISBN:9783540789666 p.433-450, 10.1007/978-3-540-78967-3_25
  10. Chase Melissa, Healy Alexander, Lysyanskaya Anna, Malkin Tal, Reyzin Leonid, Mercurial Commitments with Applications to Zero-Knowledge Sets, Lecture Notes in Computer Science (2005) ISBN:9783540259107 p.422-439, 10.1007/11426639_25
  11. Chaum David, Evertse Jan-Hendrik, Graaf Jeroen, An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations, Advances in Cryptology — EUROCRYPT ’87 ISBN:9783540191025 p.127-141, 10.1007/3-540-39118-5_13
  12. Cheon Jung Hee, Security Analysis of the Strong Diffie-Hellman Problem, Advances in Cryptology - EUROCRYPT 2006 (2006) ISBN:9783540345466 p.1-11, 10.1007/11761679_1
  13. Di Raimondo Mario, Gennaro Rosario, New approaches for deniable authentication, 10.1145/1102120.1102137
  14. Gennaro Rosario, Multi-trapdoor Commitments and Their Applications to Proofs of Knowledge Secure Under Concurrent Man-in-the-Middle Attacks, Advances in Cryptology – CRYPTO 2004 (2004) ISBN:9783540226680 p.220-236, 10.1007/978-3-540-28628-8_14
  15. Gennaro Rosario, Micali Silvio, Independent Zero-Knowledge Sets, Automata, Languages and Programming (2006) ISBN:9783540359074 p.34-45, 10.1007/11787006_4
  16. Goldwasser Shafi, Micali Silvio, Rivest Ronald L., A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, 10.1137/0217017
  17. Hofheinz Dennis, Kiltz Eike, Programmable Hash Functions and Their Applications, Lecture Notes in Computer Science ISBN:9783540851738 p.21-38, 10.1007/978-3-540-85174-5_2
  18. Liskov Moses, Updatable Zero-Knowledge Databases, Lecture Notes in Computer Science (2005) ISBN:9783540306849 p.174-198, 10.1007/11593447_10
  19. MacKenzie Philip, Yang Ke, On Simulation-Sound Trapdoor Commitments, Advances in Cryptology - EUROCRYPT 2004 (2004) ISBN:9783540219354 p.382-400, 10.1007/978-3-540-24676-3_23
  20. Merkle Ralph C., A Digital Signature Based on a Conventional Encryption Function, Advances in Cryptology — CRYPTO ’87 (1988) ISBN:9783540187967 p.369-378, 10.1007/3-540-48184-2_32
  21. Micali S., Rabin M., Kilian J., Zero-knowledge sets, 10.1109/sfcs.2003.1238183
  22. Ostrovsky Rafail, Rackoff Charles, Smith Adam, Efficient Consistency Proofs for Generalized Queries on a Committed Database, Automata, Languages and Programming (2004) ISBN:9783540228493 p.1041-1053, 10.1007/978-3-540-27836-8_87
  23. Pedersen Torben Pryds, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Advances in Cryptology — CRYPTO ’91 ISBN:9783540551881 p.129-140, 10.1007/3-540-46766-1_9
  24. Prabhakaran Manoj, Xue Rui, Statistically Hiding Sets, Topics in Cryptology – CT-RSA 2009 (2009) ISBN:9783642008610 p.100-116, 10.1007/978-3-642-00862-7_7
  25. Waters Brent, Efficient Identity-Based Encryption Without Random Oracles, Lecture Notes in Computer Science (2005) ISBN:9783540259107 p.114-127, 10.1007/11426639_7
Bibliographic reference Libert, Benoît ; Yung, M.. Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs.Theory of Cryptography. 7th Theory of Cryptography Conference, TCC 2010 (Zurich, Switzerland, 9-11 February 2010). In: Micciancio, D.;, Theory of Cryptography. 7th Theory of Cryptography Conference, TCC 2010, Springer-verlag2010, p. 499-517
Permanent URL http://hdl.handle.net/2078.1/67437