Using symmetries in the index calculus for elliptic curves discrete logarithm (Q484325)

This paper deals with the so-called Point Decomposition Problem (PDP) on elliptic curves \(E\) defined over a finite non-binary field \(\mathbb{F}_{q^n},\;n \geq 2\) (with \(n\) small), \(E\) given by a twisted Edwards or a twisted Jacobi intersection model. \textit{P. Gaudry} [J. Symb. Comput. 44, No. 12, 1690--1702 (2009; Zbl 1177.94148)] proposed an Index Calculus attack to the discrete logarithm problem. One of the steps of this algorithm, for elliptic curves \(E\) defined over \(\mathbb{F}_{q^n}\), is the PDP: given \(R\in E(\mathbb{F}_{q^n})\) and a fixed factor base \({\mathcal F}\) to find points \(P_1, P_2,\dots , P_n\) such that \(R=P_1\oplus \dots \oplus P_n\). The present paper takes advantages of the symmetries of twisted Edwards and twisted Jacobi intersection curves to decrease the complexity of the computation of PDP by a factor of \(2^{\omega(n-1)},\;2\leq \omega >3\). Section 2 summarizes a method, summation polynomials, due to \textit{I. Semaev} [``Summation polynomials and the discrete logarithm problem on elliptic curves'', Cryptology ePrint archive, \url{http://eprint.iacr.org/2004/031} (2004)]. Then, applying Weil restriction, to solve PDP is equivalent to solve a polynomial system. In order to solve that system one need to compute a Gröbner basis and Section 3 is devoted to this problem. The core Section 4 shows how the 2-torsion or 4-torsion points in twisted Edwards and twisted Jacobi intersection curves allows to speed up the PDP solving (Theorem 4.1). Finally Section 5 shows experimental results for \(n=4,5,6\), see Tables 1 to 6. For instance in the authors words ``for a twisted Edwards or twisted Jacobi intersections curve defined over \(\mathbb{F}_{q^5}\) where \(\log_2(q)=64\), solving the ECDLP with generic algorithms require approximately \(2^{160}\) operations in \(E(\mathbb{F}_{q^5})\) and only \(2^{130}\) basic arithmetic operations (multiplications of two 32-bits words) with our approach.''