Non-Interactive Zero-Knowledge Proofs of Non-Membership

Olivier Blazy 1 Céline Chevalier 2 Damien Vergnaud 3
1 XLIM-DMI - DMI
XLIM - XLIM
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Often, in privacy-sensitive cryptographic protocols, a party commits to a secret message m and later needs to prove that m belongs to a language L or that m does not belong to L (but does not want to reveal any further information). We present a method to prove in a non-interactive way that a committed value does not belong to a given language L. Our construction is generic and relies on the corresponding proof of membership to L. We present an efficient realization of our proof system by combining smooth projective hash functions and Groth-Sahai proof system. In 2009, Kiayias and Zhou introduced zero-knowledge proofs with witness elimination which enable to prove that a committed message m belongs to a set L in such a way that the verifier accepts the interaction only if m does not belong to a set determined by a public relation Q and some private input m′ of the verifier. We show that the protocol they proposed is flawed and that a dishonest prover can actually make a verifier accept a proof for any message m in L even if (m,m′) belongs to Q. Using our non-interactive proof of non-membership of committed values, we are able to fix their protocol and improve its efficiency. Our approach finds also efficient applications in other settings, e.g. in anonymous credential systems and privacy-preserving authenticated identification and key exchange protocols.
Type de document :
Communication dans un congrès
Kaisa Nyberg. Topics in Cryptology - CT-RSA 2015, The Cryptographer's Track at the RSA Conference 2015, Apr 2015, San Francisco, United States. Springer, Topics in Cryptology - CT-RSA 2015, Lecture Notes in Computer Science 2014 (9048), pp.145-164, 〈http://link.springer.com/book/10.1007/978-3-319-16715-2〉. 〈10.1007/978-3-319-16715-2_8〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01214711
Contributeur : Damien Vergnaud <>
Soumis le : lundi 12 octobre 2015 - 20:18:43
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Olivier Blazy, Céline Chevalier, Damien Vergnaud. Non-Interactive Zero-Knowledge Proofs of Non-Membership. Kaisa Nyberg. Topics in Cryptology - CT-RSA 2015, The Cryptographer's Track at the RSA Conference 2015, Apr 2015, San Francisco, United States. Springer, Topics in Cryptology - CT-RSA 2015, Lecture Notes in Computer Science 2014 (9048), pp.145-164, 〈http://link.springer.com/book/10.1007/978-3-319-16715-2〉. 〈10.1007/978-3-319-16715-2_8〉. 〈hal-01214711〉

Partager

Métriques

Consultations de la notice

308