Diffie-Hellman Oracles

Ueli Maurer and Stefan Wolf

Advances in Cryptology — CRYPTO '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1109, pp. 268–282, Aug 1996.

This paper consists of three parts. First, various types of Diffie-Hellman oracles for a cyclic group $G$ and subgroups of $G$ are defined and their equivalence is proved. In particular, the security of using a subgroup of $G$ instead of $G$ in the Diffie-Hellman protocol is investigated. Second, we derive several new conditions for the polynomial-time equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms in $G$ which extend former results by den Boer and Maurer. Finally, efficient constructions of Diffie-Hellman groups with provable equivalence are described.

BibTeX Citation

@inproceedings{MauWol96c,
    author       = {Ueli Maurer and Stefan Wolf},
    title        = {{D}iffie-{H}ellman Oracles},
    editor       = {Neal Koblitz},
    booktitle    = {Advances in Cryptology --- CRYPTO~'96},
    pages        = {268--282},
    series       = {Lecture Notes in Computer Science},
    volume       = {1109},
    year         = {1996},
    month        = {8},
    publisher    = {Springer-Verlag},
}