Non-Interactive Zero-Knowledge Proofs of Non-Membership

Olivier Blazy, Céline Chevalier, and Damien Vergnaud

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 this party 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 the 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 language L (with a witness w) in such a way that the verifier accepts the interaction only if w does not belong to a set determined by a public relation Q and some private input w' 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 (w,w') in 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.CT-RSA 2015
Keywords
Zero KnowledgeWitness EliminationSmooth Projective Hash FunctionGroth-Sahai Proof System
Contact author(s)
olivier blazy @ unilim fr
History
Short URL
https://ia.cr/2015/072

CC BY

BibTeX

@misc{cryptoeprint:2015/072,
author = {Olivier Blazy and Céline Chevalier and Damien Vergnaud},
title = {Non-Interactive Zero-Knowledge Proofs of Non-Membership},
howpublished = {Cryptology ePrint Archive, Paper 2015/072},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/072}},
url = {https://eprint.iacr.org/2015/072}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.