International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Vector Decomposition Problem for Elliptic and Hyperelliptic Curves

Authors:
Iwan Duursma
Negar Kiyavash
Download:
URL: http://eprint.iacr.org/2005/031
Search ePrint
Search Google
Abstract: The group of m-torsion points on an elliptic curve, for a prime number m, forms a two-dimensional vector space. It was suggested and proven by Yoshida that under certain conditions the vector decomposition problem (VDP) on a two-dimensional vector space is at least as hard as the computational Diffie-Hellman problem (CDHP) on a one-dimensional subspace. In this work we show that even though this assessment is true, it applies to the VDP for m-torsion points on an elliptic curve only if the curve is supersingular. But in that case the CDHP on the one-dimensional subspace has a known sub-exponential solution. Furthermore, we present a family of hyperelliptic curves of genus two that are suitable for the VDP.
BibTeX
@misc{eprint-2005-12370,
  title={The Vector Decomposition Problem for Elliptic and Hyperelliptic Curves},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Elliptic curve cryptography, Curves of genus two},
  url={http://eprint.iacr.org/2005/031},
  note={ duursma@math.uiuc.edu 12821 received 7 Feb 2005},
  author={Iwan Duursma and Negar Kiyavash},
  year=2005
}