Curve | Method | Operation counts | Global estimation |
4-GLV(Algorithm in [12-18]) 4-GLV(Our algorithm) |
|||
{4-GLV(Algorithm in [10]) 4-GLV(Our algorithm) |
|||
4-GLV (Our algorithm) | |||
4-GLV(Our algorithm) |
We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $ \mathbb{Z} $ and the second one in the Gaussian integer ring $ \mathbb{Z}[i] $. We observe that $ \mathbb{Z}[i] $ in the second sub-algorithm can be replaced by another Euclidean domain $ \mathbb{Z}[\omega] $ $ (\omega = \frac{-1+\sqrt{-3}}{2}) $. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $ C\cdot n^{1/4} $, where $ C = \frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|} $ with small values $ r, s $ given by the curves.
The new twofold algorithm can be used to compute $ 4 $-GLV decompositions on two classes of curves. First it gives a new and unified method to compute all $ 4 $-GLV decompositions on $ j $-invariant $ 0 $ elliptic curves over $ \mathbb{F}_{p^2} $. Second it can be used to compute the $ 4 $-GLV decomposition on the Jacobian of the hyperelliptic curve defined as $ \mathcal{C}/\mathbb{F}_{p}:y^{2} = x^{6}+ax^{3}+b $, which has an endomorphism $ \phi $ with the characteristic equation $ \phi^2+\phi+1 = 0 $ (hence $ \mathbb{Z}[\phi] = \mathbb{Z}[\omega] $). As far as we know, none of the previous algorithms can be used to compute the $ 4 $-GLV decomposition on the latter class of curves.
Citation: |
Table 1. Total cost of scalar multiplication at a 128-bit security level
Curve | Method | Operation counts | Global estimation |
4-GLV(Algorithm in [12-18]) 4-GLV(Our algorithm) |
|||
{4-GLV(Algorithm in [10]) 4-GLV(Our algorithm) |
|||
4-GLV (Our algorithm) | |||
4-GLV(Our algorithm) |
[1] |
J. W. Bos, C. Costello, H. Hisil and K. Lauter, High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition, International Workshop on Cryptographic Hardware and Embedded Systems, 2013 (2013), 331-348.
doi: 10.1007/978-3-642-40349-1_19.![]() ![]() |
[2] |
H. Cohen, A Course in Computational Algebraic Number Theory, GTM 138, Springer, Heidelberg, 1993.
doi: 10.1007/978-3-662-02945-9.![]() ![]() ![]() |
[3] |
C. Costello and K. Lauter, Group law computations on jacobians of hyperelliptic curves, Selected Areas in Cryptography, 7118 (2012), 92-117.
doi: 10.1007/978-3-642-28496-0_6.![]() ![]() ![]() |
[4] |
D. M. Freeman and T. Satoh, Constructing pairing-friendly hyperelliptic curves using Weil restriction, Journal of Number Theory, 131 (2011), 959-983.
doi: 10.1016/j.jnt.2010.06.003.![]() ![]() ![]() |
[5] |
S. D. Galbraith, X. Lin and M. Scott, Endomorphisms for faster elliptic curve cryptography on a Large class of curves, Journal of Cryptology, 24 (2011), 446-469.
doi: 10.1007/s00145-010-9065-y.![]() ![]() ![]() |
[6] |
R. P. Gallant, R. J. Lambert and S. A. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, Advances in Cryptology –- CRYPTO 2001, 2139 (2001), 190-200.
doi: 10.1007/3-540-44647-8_11.![]() ![]() ![]() |
[7] |
A. Guillevic and S. Ionica, Four-dimensional GLV via the weil restriction, International Conference on the Theory and Application of Cryptology and Information Security, 2013 (2013), 79-96.
doi: 10.1007/978-3-642-42033-7_5.![]() ![]() ![]() |
[8] |
A. Guillevic and D. Vergnaud, Genus 2 hyperelliptic curve families with explicit jacobian order evaluation and pairing-friendly constructions, Pairing-Based Cryptography-Pairing 2012, 7708 (2013), 234-253.
doi: 10.1007/978-3-642-36334-4_16.![]() ![]() ![]() |
[9] |
D. Hankerson, A. J. Menezes and S. Vanstone, Guide to elliptic curve cryptography, Springer, Heidelberg, 281 (2004), 311-314.
doi: 10.1016/s0012-365x(04)00102-5.![]() ![]() ![]() |
[10] |
Z. Hu, P. Longa and M. Xu, Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0., Designs, Codes and Cryptography, 63 (2012), 331-343.
doi: 10.1007/s10623-011-9558-1.![]() ![]() ![]() |
[11] |
T. Iijima, K. Matsuo, J. Chao and S. Tsujii, Construction of frobenius maps of twists elliptic curves and its application to elliptic scalar multiplication, The 2002 Symposium on Cryptography and Information Security Shirahama, Japan, Jan.29-Feb.1, 2002–-SCIS, 2002,699–702.
![]() |
[12] |
P. Longa and F. Sica, Four-dimensional gallant-lambert-vanstone scalar multiplication, Journal of Cryptology, 27 (2014), 248-283.
doi: 10.1007/s00145-012-9144-3.![]() ![]() ![]() |
[13] |
P. Longa, High-Speed Elliptic Curve and Pairing-Based Cryptography, Ph.D Thesis, University of Waterloo, 2011. Available from: http://hdl.handle.net/10012/5857.
![]() |
[14] |
J. M. Miret, R. Moreno Chiral and A. Rio, Generalization of Vélu's formulae for isogenies between elliptic curves, Publicacions Matemàtiques, 2007 (2007), 147-163.
doi: 10.5565/PUBLMAT_PJTN05_07.![]() ![]() ![]() |
[15] |
F. Sica, M. Ciet and J. J. Quisquater, Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms, elliptic and hyperelliptic curves, International Workshop on Selected Areas in Cryptography, 2595 (2002), 21-36.
doi: 10.1007/3-540-36492-7_3.![]() ![]() ![]() |
[16] |
J. H. Silverman, The Arithmetic of Elliptic Curves, GTM 106. Springer, New York, 2009.
doi: 10.1007/978-0-387-09494-6.![]() ![]() ![]() |
[17] |
J. Vélu, Isogenies entre courbes elliptiques, Compte Rendu Académie Sciences Paris Série, 273 (1971), 238-241.
![]() ![]() |
[18] |
H. Yi, Y. Zhu and D. Lin, Refinement of the four-Dimensional GLV method on elliptic curves, International Conference on Selected Areas in Cryptography, 2017 (2017), 23-42.
doi: 10.1007/978-3-319-72565-9_2.![]() ![]() ![]() |
[19] |
Z. Zhou, Z. Hu, M. Xu and W. Song, Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves, Information Processing Letters, 110) (2010), 1003-1006.
doi: 10.1016/j.ipl.2010.08.014.![]() ![]() ![]() |
A lattice diamond in