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