×

Computing the characteristic polynomials of a class of hyperelliptic curves for cryptographic applications. (English) Zbl 1213.94144

Summary: Hyperelliptic curves have been widely studied for cryptographic applications, and some special hyperelliptic curves are often considered to be used in practical cryptosystems. Computing Jacobian group orders is an important operation in constructing hyperelliptic curve cryptosystems, and the most common method used for the computation of Jacobian group orders is by computing the zeta functions or the characteristic polynomials of the related hyperelliptic curves. For the hyperelliptic curve \(C_q:v^2 = u^p + au + b\) over the field \(\mathbb{F}_q\) with \(q\) being a power of an odd prime \(p\), Duursma and Sakurai obtained its characteristic polynomial for \(q = p\), \(a = -1\), and \(b \in \mathbb{F}_p\). In this paper, we determine the characteristic polynomials of \(C_q\) over the finite field \(\mathbb{F}_{p^n}\) for \(n = 1, 2\) and \(a, b \in \mathbb{F}_{p^n}\). We also give some computational data which show that many of those curves have large prime factors in their Jacobian group orders, which are both practical and vital for the constructions of efficient and secure hyperelliptic curve cryptosystems.

MSC:

94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry

Software:

HECC

References:

[1] N. Koblitz, “Hyperelliptic cryptosystems,” Journal of Cryptology, vol. 1, no. 3, pp. 139-150, 1989. · Zbl 0674.94010 · doi:10.1007/BF02252872
[2] J. Pelzl, T. Wollinger, J. Guajardo, and C. Paar, Hyperelliptic Curve Cryptosystems: Closing the Performance Gap to Elliptic Curves, vol. 2779 of Lecture Notes in Computer Science, Springer, Berlin, Germany, 2003. · Zbl 1274.94105
[3] A. Weil, “Numbers of solutions of equations in finite fields,” Bulletin of the American Mathematical Society, vol. 55, pp. 497-508, 1949. · Zbl 0032.39402 · doi:10.1090/S0002-9904-1949-09219-4
[4] R. Hartshorne, Algebraic Geometry, vol. 52 of Graduate Texts in Mathematics, Springer, New York, NY, USA, 1977. · Zbl 0367.14001
[5] K. S. Kedlaya, “Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology,” Journal of the Ramanujan Mathematical Society, vol. 16, no. 4, pp. 323-338, 2001. · Zbl 1066.14024
[6] I. Duursma and K. Sakurai, “Efficient algorithms for the Jacobian variety of hyperelliptic curves y2=xp - x+1 over a finite field of odd characteristic p,” in Proceedings of the International Conference on Coding Theory, Cryptography and Related Areas, pp. 73-89, Springer, Guanajuato, Mexico, 2000. · Zbl 1009.11047
[7] J. H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, vol. 151 of Graduate Texts in Mathematics, Springer, New York, NY, USA, 1994. · Zbl 0911.14015
[8] P. Lockhart, “On the discriminant of a hyperelliptic curve,” Transactions of the American Mathematical Society, vol. 342, no. 2, pp. 729-752, 1994. · Zbl 0815.11031 · doi:10.2307/2154650
[9] I. Duursma, “Class numbers for some hyperelliptic curves,” in Arithmetic, Geometry and Coding Theory, pp. 45-52, de Gruyter, Berlin, Germany, 1996. · Zbl 0901.11020
[10] S. Tafazolian, On supersingular curves over finite fields, Ph.D. thesis, Instituto Nacional de Matemática Pura e Aplicada, 2008. · Zbl 1186.11034
[11] J. M. Pollard, “Carlo methods for index computation modp,” Mathematics of Computation, vol. 32, no. 143, pp. 918-924, 1978. · Zbl 0382.10001 · doi:10.2307/2006496
[12] O. Schirokauer, D. Weber, and T. Denny, “Discrete logarithms: the effectiveness of the index calculus method,” in Algorithmic Number Theory, vol. 1122 of Lecture Notes in Computer Science, pp. 337-361, Springer, Berlin, Germany, 1996. · Zbl 0895.11054
[13] P. Gaudry, “An algorithm for solving the discrete log problem on hyperelliptic curves,” in Advances in Cryptology-Eurocrypt 2000, vol. 807 of Lecture Notes in Computer Science, pp. 19-34, Springer, Berlin, Germany, 2000. · Zbl 1082.94517 · doi:10.1007/3-540-45539-6_2
[14] P. Gaudry, E. Thomé, N. Thériault, and C. Diem, “A double large prime variation for small genus hyperelliptic index calculus,” Mathematics of Computation, vol. 76, no. 257, pp. 475-492, 2007. · Zbl 1179.94062 · doi:10.1090/S0025-5718-06-01900-4
[15] S. D. Galbraith, “Supersingular curves in cryptography,” in Advances in Cryptology-ASIACRYPT 2001, vol. 2248 of Lecture Notes in Computer Science, pp. 495-513, Springer, Berlin, Germany, 2001. · Zbl 1064.11079 · doi:10.1007/3-540-45682-1_29
[16] H. Stichtenoth, “Über die Automorphismengruppe eines algebraischen Funktionenkörpers von Primzahlcharakteristik. II. Ein spezieller Typ von Funktionenkörpern,” Archiv der Mathematik, vol. 24, pp. 615-631, 1973. · Zbl 0282.14007 · doi:10.1007/BF01228261
[17] D. Boneh, “A brief look at pairings based cryptography,” in Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS ’07), pp. 19-26, IEEE Press, Los Alamitos, CA, USA, 2007. · doi:10.1109/FOCS.2007.4389476
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.