Paper 2004/070

Easy decision-Diffie-Hellman groups

Steven D Galbraith and Victor Rotger

Abstract

It is already known that the Weil and Tate pairings can be used to solve many decision-Diffie-Hellman (DDH) problems on elliptic curves. A natural question is whether all DDH problems are easy on supersingular curves. To answer this question it is necessary to have suitable distortion maps. Verheul states that such maps exist, and this paper gives methods to construct them. The paper therefore shows that all DDH problems on supersingular elliptic curves are easy. We also discuss the issue of which DDH problems on ordinary curves are easy. A related contribution is a discussion of distortion maps which are not isomorphisms. We give explicit distortion maps for elliptic curves with complex multiplication of discriminants $D=-7$ and $D=-8$.

Note: This paper has now appeared in LMS J. Comput. Math. 7 (2004) 201--218 See http://www.lms.ac.uk/jcm/7/lms2004-010

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
pairingselliptic curvesdecision-Diffie-Hellman problem
Contact author(s)
Steven Galbraith @ rhul ac uk
History
2004-08-31: last of 3 revisions
2004-03-02: received
See all versions
Short URL
https://ia.cr/2004/070
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/070,
      author = {Steven D Galbraith and Victor Rotger},
      title = {Easy decision-Diffie-Hellman groups},
      howpublished = {Cryptology ePrint Archive, Paper 2004/070},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/070}},
      url = {https://eprint.iacr.org/2004/070}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.