Journal of the Ramanujan Mathematical Society

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

The Vector Decomposition Problem for Elliptic and Hyperelliptic Curves


Affiliations
1 Coordinated Science Laboratory, Department of Mathematics, University of Illinois at Urbana-Champaign, United States
2 Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, United States
     

   Subscribe/Renew Journal


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.
User
Subscription Login to verify subscription
Notifications
Font Size

Abstract Views: 275

PDF Views: 0




  • The Vector Decomposition Problem for Elliptic and Hyperelliptic Curves

Abstract Views: 275  |  PDF Views: 0

Authors

Iwan Duursma
Coordinated Science Laboratory, Department of Mathematics, University of Illinois at Urbana-Champaign, United States
Negar Kiyavash
Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, United States

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.