## Cryptology ePrint Archive: Report 2021/090

A New Twofold Cornacchia-Type Algorithm for 4-GLV Decompositions and Its Applications

Bei Wang; Yi Ouyang; Honggang Hu ; Songsong Li

Abstract: Until now, there are two different methods to compute 4-GLV decompositions on the elliptic curves over $\mathbb{F}_{p^2}$ which are quadratic twists and possess a “restricted” endomorphism $\psi$ satisfying $\psi^{2}+1=0$. They are Longa and Sica's twofold Cornacchia-type algorithm (ASIACRYPT 2012) and Benjamin Smith's method--ready-made short bases (AMS 2015). In this paper, we first extend Smith's method from the case of quadratic twists to the case of quartic or sextic twists and give ready-made short bases for 4-GLV decompositions on these high degree twisted curves. After our supplements, Smith's method can be used to compute 4-GLV decompositions on more elliptic curves. Secondly, we focus on exploring more potential of Longa and Sica's algorithm, 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 $\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 curve. 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}$. We exploit the fact that this family of curves must have an endomorphism $\phi$ satisfying $\phi^{2}+\phi+1=0$ (and hence $\mathbb{Z}[\phi]=\mathbb{Z}[\omega]$). Of the two previous methods on this class of elliptic curves, the first one was proposed by Hu, Longa and Xu in 2012 (Designs, Codes and Cryptography) but is applicable only to curves which are twists of degree $6$ and possess a “restricted” endomorphism $\psi$ satisfying $\psi^{4}-\psi^{2}+1=0$, the second one follows from the the work of Longa and Sica (ASIACRYPT 2012) and is applicable only to curves with a “restricted” endomorphism $\psi$ satisfying $\psi^{2}+1=0$. 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 $\Z[\phi]=\Z[\omega]$).

Category / Keywords: public-key cryptography / Elliptic curves ; 4-GLV decompositions ; Twofold Cornacchia-type algorithm