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.
Citation: Bei Wang, Songsong Li, Yi Ouyang, Honggang Hu. Ready-made short basis for GLV+GLS on high degree twisted curves[J]. AIMS Mathematics, 2022, 7(1): 306-314. doi: 10.3934/math.2022021
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.
| [1] | R. P. Gallant, R. J. Lambert, S. A. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, In: J. Kilian, Advances in cryptology–CRYPTO 2001, Lecture Notes in Computer Science, Berlin: Springer, 2139 (2001), 190–200. doi: 10.1007/3-540-44647-8_11. |
| [2] |
S. D. Galbraith, X. B. Lin, M. Scott, Endomorphisms for faster elliptic curve cryptography on a Large class of curves, J. Cryptology, 24 (2011), 446–469. doi: 10.1007/s00145-010-9065-y. doi: 10.1007/s00145-010-9065-y
|
| [3] | P. Longa, F. Sica, Four-dimensional Gallant-Lambert-Vanstone scalar multiplication, In: X. Wang, K. Sako, Advances in cryptology–ASIACRYPT 2012, Lecture Notes in Computer Science, Berlin: Springer, 27 (2014), 248–283. doi: 10.1007/978-3-642-34961-4_43. |
| [4] | A. Guillevic, S. Ionica, Four-dimensional GLV via the Weil restriction, In: K. Sako, P. Sarkar, Advances in cryptology–ASIACRYPT 2013, Lecture Notes in Computer Science, Berlin: Springer, Springer, 8269 (2013), 79–96. doi: 10.1007/978-3-642-42033-7_5. |
| [5] | B. Smith, Easy scalar decompositions for efficient scalar multiplication on elliptic curves and genus 2 Jacobians, In: S. Ballet, M. Perret, A. Zaytsev, Algorithmic arithmetic, geometry, and coding theory, American Mathematical Society, 637 (2015), 127–142. doi: 10.1090/conm/637/12753. |
| [6] | B. Smith, Families of fast elliptic curves from $\mathbb{Q}$-curves, In: K. Sako, P. Sarkar, Advances in cryptology–ASIACRYPT 2013, Lecture Notes in Computer Science, Berlin: Springer, Springer, 8269 (2013), 61–78. doi: 10.1007/978-3-642-42033-7_4. |
| [7] | D. R. Kohel, B. Smith, Efficiently computable endomorphisms for hyperelliptic curves, In: F. Hess, S. Pauli, M. Pohst, Algorithmic number theory. ANTS 2006, Lecture Notes in Computer Science, Berlin: Springer, Springer, 4076 (2006), 495–509. doi: 10.1007/11792086_35. |
| [8] |
K. Takashima, A new type of fast endomorphisms on Jacobians of hyperelliptic curves and their cryptographic application, IEICE Trans. Fund. Electr., E89-A (2006), 124–133. doi: 10.1093/ietfec/e89-a.1.124. doi: 10.1093/ietfec/e89-a.1.124
|
| [9] | K. Ireland K, M. Rosen, A classical introduction to modern number theory, Vol. 84, New York: Springer, 1990. doi: 10.1007/978-1-4757-2103-4. |
| [10] |
Z. Hu, P. Longa, M. Z. Xu, Implementing the 4-dimensional GLV method on GLS elliptic curves with $j$-invariant 0, Des. Codes Cryptogr., 63 (2012), 331–343. doi: 10.1007/s10623-011-9558-1. doi: 10.1007/s10623-011-9558-1
|
| [11] | H. Cohen, A course in computational algebraic number theory, New York: Springer, 1993. doi: 10.1007/978-3-662-02945-9. |
| [12] | F. Hess, N. P. Smart, F. Vercauteren, The Eta pairing revisited, IEEE Trans. Inf. Theory, 52 (2006), 4595–4602. doi: 10.1109/TIT.2006.881709. |
Bei Wang, Songsong Li, Yi Ouyang, Honggang Hu. Ready-made short basis for GLV+GLS on high degree twisted curves[J]. AIMS Mathematics, 2022, 7(1): 306-314. doi: 10.3934/math.2022021
DownLoad: