Efficient proofs of knowledge of discrete logarithms and representations in groups with hidden order

For many one-way homomorphisms used in cryptography, there exist efficient zero-knowledge proofs of knowledge of a preimage. Examples of such homomorphisms are the ones underlying the Schnorr or the Guillou-Quisquater identification protocols. In this paper we present, for the first time, efficient zero-knowledge proofs of knowledge for exponentiation ψ(x 1) ≒ h1x1 and multi-exponentiation homomorphisms ψ(x1, . . . , x1) ≒ h 1x1 · . . . · hlxl with h1, . . . , hl εH (i.e., proofs of knowledge of discrete logarithms and representations) where H is a group of hidden order, e.g., an RSA group. © International Association for Cryptologic Research 2005.