Paper 2021/130

Ready-Made Short Basis for GLV+GLS on High Degree Twisted Curves

Bei Wang, Songsong Li, Yi Ouyang, and Honggang Hu


The crucial step in elliptic curve scalar multiplication based on scalar decompositions using efficient endomorphisms—such as GLV, GLS or GLV+GLS—is to produce a short basis of a lattice involving the eigenvalues of the endomorphisms, which usually is obtained by lattice basis reduction algorithms or even more specialized algorithms. Recently, lattice basis reduction is found to be unnecessary. Benjamin Smith (AMS 2015) was able to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS of quadratic twists using elementary facts about quadratic rings. Certainly it is always more convenient to use a ready-made short basis than to compute a new one by some algorithm. In this paper, we extend Smith's method on GLV+GLS for quadratic twists to quartic and sextic twists, and give ready-made short bases for $4$-dimensional decompositions on these high degree twisted curves. In particular, our method gives a unified short basis compared with Hu et. al's method (DCC 2012) for $4$-dimensional decompositions on sextic twisted curves.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
EndomorphismReady-made short basisTwistGLV+GLS
Contact author(s)
wangbei @ mail ustc edu cn
2021-03-04: last of 3 revisions
2021-02-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bei Wang and Songsong Li and Yi Ouyang and Honggang Hu},
      title = {Ready-Made Short Basis for GLV+GLS on High Degree Twisted Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2021/130},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.