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.
Category / Keywords: public-key cryptography / Zero Knowledge, Witness Elimination, Smooth Projective Hash Function, Groth-Sahai Proof System Original Publication (with major differences): CT-RSA 2015 Date: received 1 Feb 2015 Contact author: olivier blazy at unilim fr Available format(s): PDF | BibTeX Citation Version: 20150210:050642 (All versions of this report) Short URL: ia.cr/2015/072 Discussion forum: Show discussion | Start new discussion