Zero-Knowledge Proofs with Witness Elimination

Aggelos Kiayias, Hong-Sheng Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Zero-knowledge proofs with witness elimination are protocols that enable a prover to demonstrate knowledge of a witness to the verifier that accepts the interaction provided that the witness is valid for a given statement and additionally the witness does not belong to a set of eliminated witnesses. This set is determined by a public relation Q (that parameterizes the primitive) and the private input of the verifier. Zero-knowledge proofs with witness elimination thus call for a relaxation of the zero-knowledge property and are relevant in settings where a statement has a multitude of witnesses that may attest to its validity. A number of interesting issues arise in the design of such protocols that include whether a protocol transcript enables the verifier to test for witness after termination (something akin to an “offline dictionary attack”) and whether the prover should be capable of understanding whether her witness is eliminated. The primitive is motivated by the setting of identification schemes where a user wishes to authenticate herself to an access point while preserving her anonymity and the access point needs to certify that the user is eligible while at the same time making sure she does not match the identity of a suspect user that is tracked by the authorities. We call such primitives anonymous identification schemes with suspect tracking. In this work we formalize zero-knowledge proofs with witness elimination in the universal composability setting and we provide a general construction based on smooth projective hashing that is suitable for designing efficient schemes. As an illustration of our general construction we then present an explicit efficient scheme for proving knowledge of a Boneh-Boyen signature with witness elimination. Our scheme requires the design of a smooth projective hash function for the language of linear ElGamal ciphertexts. Along the way we demonstrate how zero-knowledge proofs with witness elimination naturally relate to the primitives of password-based key exchange and private equality testing.
Original languageEnglish
Title of host publicationPublic Key Cryptography -- PKC 2009
Subtitle of host publication12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings
EditorsStanislaw Jarecki, Gene Tsudik
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-642-00468-1
ISBN (Print)978-3-642-00467-4
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Zero-Knowledge Proofs with Witness Elimination'. Together they form a unique fingerprint.

Cite this