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)
- 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
-
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}, url = {https://eprint.iacr.org/2018/1220} }