Easy decision Diffie–Hellman groups
Steven D. Galbraith and Victor Rotger
Abstract: The decision Diffie–Hellman problem (DDH) is a central
computational problem in cryptography. It is known that the Weil
and Tate pairings can be used to solve many DDH problems on
elliptic curves. Distortion maps are an important tool for solving
DDH problems using pairings, and it is known that distortion maps
exist for all supersingular elliptic curves. An algorithm is
presented here to construct suitable distortion maps. The
algorithm is efficient on the curves that are usable in practice,
and hence all DDH problems on these curves are easy. The issue of
which DDH problems on ordinary curves are easy is also discussed.
|
