International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Easy decision-Diffie-Hellman groups

Authors:
Steven D. Galbraith
Victor Rotger
Download:
URL: http://eprint.iacr.org/2004/070
Search ePrint
Search Google
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$.
BibTeX
@misc{eprint-2004-12044,
  title={Easy decision-Diffie-Hellman groups},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / pairings, elliptic curves, decision-Diffie-Hellman problem},
  url={http://eprint.iacr.org/2004/070},
  note={ Steven.Galbraith@rhul.ac.uk 12661 received 2 Mar 2004, last revised 31 Aug 2004},
  author={Steven D. Galbraith and Victor Rotger},
  year=2004
}