Zero-Knowledge Proofs with Witness Elimination

Abstract. Zero-knowledge proofs with witness elimination are proto-cols 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 relax-ation 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 wit-ness 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 identi-fication schemes where a user wishes to authenticate herself to an access point while preserving her anonymity and the access point needs to cer-tify 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 construc-tion 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.? Research partly supported by NSF CAREER Award CNS-0447808.