Publications: Abstract

Efficient Proofs of Knowledge of Discrete Logarithms and Representations in Groups with Hidden Order

Endre Bangerter and Jan Camenisch and Ueli Maurer

 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 $\psi(x_1) = h_1^{x_1}$ and multi-exponentiation homomorphisms $\psi(x_1, \ldots, x_l) \doteq h_1^{x_1} \cdots h_l^{x_l}$ with $h_1, \ldots,h_l \in H$ (i.e., proofs of knowledge of discrete logarithms and representations) where $H$ is a group of hidden order, e.g., an RSA group.