Paper 2018/1220

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

Taiga Mizuide, Atsushi Takayasu, and Tsuyoshi Takagi

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MAJOR revision.CT-RSA 2019
Keywords
algebraic group model
Contact author(s)
takayasu @ mist i u-tokyo ac jp
History
2019-06-29: revised
2018-12-30: received
See all versions
Short URL
https://ia.cr/2018/1220
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1220,
      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{https://eprint.iacr.org/2018/1220}},
      url = {https://eprint.iacr.org/2018/1220}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.