A new twofold Cornacchia-type algorithm and its applications

Bei Wang; Yi Ouyang; Songsong Li; Honggang Hu

doi:10.3934/amc.2021026

Article Contents

2023, Volume 17, Issue 4: 873-887. Doi: 10.3934/amc.2021026

This issue Previous Article Four by four MDS matrices with the fewest XOR gates based on words Next Article Degenerate flag varieties in network coding

A new twofold Cornacchia-type algorithm and its applications

1.
Key Laboratory of Electromagnetic Space Information, CAS, School of Information Science and Technology, University of Science and Technology of China, Hefei, 230027, China
2.
CAS Wu Wen-Tsun Key Laboratory of Mathematics, School of Mathematical Sciences, University of Science and Technology of China, Hefei, 230026, China
3.
School of Cyber Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China

^* Corresponding author: Honggang Hu
^* Corresponding author: Honggang Hu

Received: April 2021

Early access: July 2021

Published: August 2023

The second author is supported by Anhui Initiative in Quantum Information Technologies grant AHY150200, NSFC grant 11571328. The fourth author is supported by NSFC (grant 61972370 and 61632013), Fundamental Research Funds for Central Universities in China grant WK3480000007

Abstract / Introduction Full Text(HTML) Figure(1) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 14H52; Secondary: 14G50.

Citation:

Full Text(HTML)

Figure 1. A lattice diamond in $ \mathbb{Z}[\omega] $

Download: Full-size image PowerPoint slide

Table 1. Total cost of scalar multiplication at a 128-bit security level

Curve	Method	Operation counts	Global estimation
$E_{1}(\mathbb{F}_{p_{1}^{2}})$	4-GLV(Algorithm in [12-18]) 4-GLV(Our algorithm)	$885M+580S$	$4395m$
$E_{2}(\mathbb{F}_{p_{2}^{2}})-(12)$	{4-GLV(Algorithm in [10]) 4-GLV(Our algorithm)	$834M+560S$	$4182m$
$E_{2}(\mathbb{F}_{p_{2}^{2}})-(13)$	4-GLV (Our algorithm)	$834M+556S$	$4170m$
$J_{\mathcal{C}}(\mathbb{F}_{p})$	4-GLV(Our algorithm)	$1623m+300s$	$1923m$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.