**The Vector Decomposition Problem for Elliptic and Hyperelliptic Curves**

*Iwan Duursma and Negar Kiyavash*

**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.

**Category / Keywords: **public-key cryptography / Elliptic curve cryptography, Curves of genus two

**Date: **received 7 Feb 2005

**Contact author: **duursma at math uiuc edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20050210:031414 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]