Index calculus algorithm for non-planar curves. (English) Zbl 1540.11079
Summary: In this paper, we develop a variation of the index calculus algorithm using non-planar models of non-hyperelliptic curves of genus \(g\). Using canonical model of degree \(2g-2\) in the projective space of dimension \(g-1\), intersections with hyperplanes and following similar ideas to those of Diem (who used intersections with lines on planar models), we obtain an upper bound of \(O(q^{2-\frac{2}{g-1}+\varepsilon})\) for the computation of discrete logarithms for all non-hyperelliptic curves of genus \(g\) defined over the finite field \(\mathbb{F}_q\). This asymptotic cost is essentially the same as Diem’s, but our algorithm offers several advantages over Diem’s, including a constant speed-up.
MSC:
| 11G20 | Curves over finite and local fields |
| 14H45 | Special algebraic curves and curves of low genus |
| 14Q05 | Computational aspects of algebraic curves |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
| 14K30 | Picard schemes, higher Jacobians |
References:
| [1] | Adleman, L. M.; DeMarrais, J.; Huang, M.-D., A subexponential algorithm for discrete logarithms in the rational subgroup of the Jacobian of a hyperelliptic curve over a finite field, (ANTS 1994. ANTS 1994, Lecture Notes in Comput. Sci., vol. 877 (1994), Springer), 28-40 · Zbl 0829.11068 |
| [2] | Arbarello, E.; Cornalba, M.; Griffiths, P. A.; Harris, J., Geometry of Algebraic Curves, vol. I, Grundlehren Math. Wiss., vol. 267 (1985), Springer · Zbl 0559.14017 |
| [3] | Diem, C., An index calculus algorithm for plane curves of small degree, (ANTS 2006. ANTS 2006, Lecture Notes in Comput. Sci., vol. 4076 (2006), Springer), 543-557 · Zbl 1143.11361 |
| [4] | Enge, A., Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comput., 71, 238, 729-742 (2002) · Zbl 0988.68069 |
| [5] | Galbraith, S. D.; Paulus, S. M.; Smart, N. P., Arithmetic on superelliptic curves, Math. Comput., 71, 237, 393-405 (2002) · Zbl 1013.11026 |
| [6] | Enge, A.; Gaudry, P.; Thomé, E., An \(L(1 / 3)\) discrete logarithm algorithm for low degree curves, J. Cryptol., 24, 1, 24-41 (2011) · Zbl 1208.94042 |
| [7] | Frey, G.; Shaska, T., Curves, Jacobians, and cryptography. Algebraic curves and their applications, Contemp. Math., 724, 279-344 (2019) · Zbl 1428.14044 |
| [8] | Gaudry, P., An algorithm for solving the discrete log problem on hyperelliptic curves, (Advances in Cryptology—EUROCRYPT 2000 (Bruges). Advances in Cryptology—EUROCRYPT 2000 (Bruges), Lecture Notes in Comput. Sci., vol. 1807 (2000), Springer: Springer Berlin), 19-34 · Zbl 1082.94517 |
| [9] | Gaudry, P.; Thomé, E.; Thériault, N.; Diem, C., A double large prime variation for small genus hyperelliptic index calculus, Math. Comput., 76, 475-492 (2007) · Zbl 1179.94062 |
| [10] | Harris, J., Algebraic Geometry, Graduate Texts in Math. (1992), Springer · Zbl 0779.14001 |
| [11] | Hartshorne, R., Algebraic Geometry, Graduate Texts in Mathematics (1977), Springer · Zbl 0367.14001 |
| [12] | Laine, K.; Lauter, K., Time-memory trade-offs for index calculus in genus 3, J. Math. Cryptol., 9, 2, 95-114 (2015) · Zbl 1370.94522 |
| [13] | Nagao, K., Index calculus attack for Jacobian of hyperelliptic curve of small genus using two large prime, Jpn. J. Appl. Ind. Math., 24, 289-305 (2007) · Zbl 1221.94055 |
| [14] | Petri, K., Über die Invarianten Darstellung algebraischer Funktionen einer Veränderlichen, Math. Ann., 88, 3-4, 242-289 (1923) · JFM 49.0264.02 |
| [15] | Saint-Donat, B., On Petri’s analysis of the linear system of quadrics through a canonical curve, Math. Ann., 206, 157-175 (1973) · Zbl 0315.14010 |
| [16] | Thériault, N., Index calculus attack for hyperelliptic curves of small genus, (Advances in Cryptology—ASIACRYPT 2003. Advances in Cryptology—ASIACRYPT 2003, Lecture Notes in Comput. Sci., vol. 2894 (2003), Springer), 75-92 · Zbl 1205.94103 |
| [17] | Vitse, V.; Wallet, A., Improved sieving on algebraic curves, (Advances in Cryptology—LATINCRYPT 2015. Advances in Cryptology—LATINCRYPT 2015, Lecture Notes in Comput. Sci., vol. 9230 (2015), Springer), 295-307 · Zbl 1370.94548 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
