Paper 2018/1220

Tight Reductions for Diffie-Hellman Variants in the Algebraic Group Model

Taiga Mizuide, Atsushi Takayasu, and Tsuyoshi Takagi


Fuchsbauer, Kiltz, and Loss~(Crypto'18) gave a simple and clean definition of an ¥emph{algebraic group model~(AGM)} that lies in between the standard model and the generic group model~(GGM). Specifically, an algebraic adversary is able to exploit group-specific structures as the standard model while the AGM successfully provides meaningful hardness results as the GGM. As an application of the AGM, they show a tight computational equivalence between the computing Diffie-Hellman~(CDH) assumption and the discrete logarithm~(DL) assumption. For the purpose, they used the square Diffie-Hellman assumption as a bridge, i.e., they first proved the equivalence between the DL assumption and the square Diffie-Hellman assumption, then used the known equivalence between the square Diffie-Hellman assumption and the CDH assumption. In this paper, we provide an alternative proof that directly shows the tight equivalence between the DL assumption and the CDH assumption. The crucial benefit of the direct reduction is that we can easily extend the approach to variants of the CDH assumption, e.g., the bilinear Diffie-Hellman assumption. Indeed, we show several tight computational equivalences and discuss applicabilities of our techniques.

Available format(s)
Publication info
Published elsewhere. Major revision. CT-RSA 2019
algebraic group model
Contact author(s)
takayasu @ mist i u-tokyo ac jp
2019-06-29: revised
2018-12-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Taiga Mizuide and Atsushi Takayasu and Tsuyoshi Takagi},
      title = {Tight Reductions for Diffie-Hellman Variants in the Algebraic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1220},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.