Information Security and Cryptography Research Group

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

Endre Bangerter, 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.

BibTeX Citation

@inproceedings{BaCaMa05,
    author       = {Endre Bangerter and Jan Camenisch and Ueli Maurer},
    title        = {Efficient Proofs of Knowledge of Discrete Logarithms and Representations in Groups with Hidden Order},
    editor       = {S. Vaudenay},
    booktitle    = {Public Key Cryptography --- PKC 2005},
    pages        = 154--171,
    series       = {Lecture Notes in Computer Science},
    volume       = 3386,
    year         = 2005,
    month        = 1,
    publisher    = {Springer-Verlag},
}

Files and Links

• PDF
• PS