Cryptology ePrint Archive: Report 2018/1220

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

Taiga Mizuide and 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.

Category / Keywords: algebraic group model

Original Publication (with major differences): CT-RSA 2019

Date: received 20 Dec 2018, last revised 29 Jun 2019

Contact author: takayasu at mist i u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20190629:090504 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]