Cryptology ePrint Archive: Report 2005/031

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)

Short URL: ia.cr/2005/031

Discussion forum: Show discussion | Start new discussion