×

A review on the isomorphism classes of hyperelliptic curves of genus 2 over finite fields admitting a Weierstrass point. (English) Zbl 1113.11036

It is well-known so far that very interesting connections with cryptography matters can be obtained by using hyperelliptic curves, specially in characteristic 2 or 3; see e.g. L. M. Adleman, J. DeMarrais and M.-D. Huang [Algorithmic number theory. 1st international symposium, ANTS–I, Ithaca, NY, USA. May 6–9, 1994. Proceedings. Berlin: Springer-Verlag, Lect. Notes Comput. Sci. 877, 28–40 (1994; Zbl 0829.11068)]. In characteristic 2, these curves were classified by G. Cardona, E. Nart and Pujolás [Curves of genus two over fields of even characteristic. http:\slash\slash www.arxiv.org/math.NT/0210105].
In this paper the authors consider non-isomorphic plane models of hyperelliptic curves of genus 2 admitting a Weierstrass point over an arbitrary finite field. As a matter of fact, they subsume results that were noticed and published by several authors by working with different methods. These plane models allow us to design and implement the so called hyperelliptic curve cryptosystems.

MSC:

11G20 Curves over finite and local fields
14H10 Families, moduli of curves (algebraic)
14G50 Applications to coding theory and cryptography of arithmetic geometry
14H45 Special algebraic curves and curves of low genus
14H50 Plane and space curves
94A60 Cryptography

Citations:

Zbl 0829.11068

Software:

HECC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adleman, L.: A subexponential algorithm for discrete logarithm problem with applications to cryptography. In: Proc. 20th IEEE Found. Comp. Sci. Symp., pp. 55–60 (1979)
[2] Adleman, L., DeMarrais, J.: A subexponential algorithm for discrete logarithms over all finite fields. Math. Comp. 61, 1–15 (1993) · Zbl 0784.11060 · doi:10.1090/S0025-5718-1993-1225541-3
[3] Adleman, L., DeMarrais, J., Huang, M.: A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. In: Proc. of Algorithmic Number Theory, LNCS, vol. 877, pp. 28–40 (1994) · Zbl 0829.11068
[4] Adleman, L., Huang, M.: Primality testing and abelian varieties over finite fields. In: LNM 1512. Springer, Berlin Heidelberg New York (1992) · Zbl 0744.11065
[5] American National Standards Institute: Public key cryptography for the financial services industry: The elliptic curve digital signature algoritm (ECDSA), ANSI X9.62-1998.
[6] Blake, I., Seroussi, G., Smart, N.: Elliptic curves in cryptography, vol. 265. London Math. Soc. (1999) · Zbl 0937.94008
[7] Boneh, D.: Twenty years of attacks on the RSA cryptosystem. Notices Amer. Math. Soc. 46(2), 203–213 (1999) · Zbl 0914.94007
[8] Brickell, E., Odlyzko, A.: Cryptanalysis: A survey of recent results. Proc. IEEE 76, 578–593 (1988) · Zbl 0818.94014 · doi:10.1109/5.4443
[9] Le Brigand, D.: Decoding of codes on hyperelliptic curves. In: Proc. of Eurocode’90, LNCS, vol. 514, pp. 126–134 (1991) · Zbl 0941.94515
[10] Brown, M., Cheung, D., Hankerson, D., Hernandez, J., Kirkup, M., Menezes, A.: PGP in constrained wireless devices. In: Proceedings of the Ninth USENIX Security Symposium, pp. 247–261 (2000)
[11] Buchmann, J., Williams, H.: A key-exchange system based on imaginary quadratic fields. J. Cryptology. 1, 107–118 (1988) · Zbl 0659.94004 · doi:10.1007/BF02351719
[12] Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. In: Lenstra, A.K., Lenstra Jr., H.W. (eds.) The Development of the Number Field Sieve, LNM 1554, pp. 50–94. Springer, Berlin Heidelberg New York (1993) · Zbl 0806.11067
[13] Cantor, D.: Computing in the Jacobian of a hyperelliptic curve. Math. Comp. 48, 95–101 (1987) · Zbl 0613.14022 · doi:10.1090/S0025-5718-1987-0866101-0
[14] Cardona, G.: On the number of curves of genus 2 over a finite field. Finite Fields Appl. 9, 505–526 (2003) · Zbl 1091.11023 · doi:10.1016/S1071-5797(03)00039-X
[15] Cardona, G., Nart, E., Pujolás, J.: Curves of genus two over fields of even characteristic. Available at http://arxiv.org/abs/math.NT/0210105 . · Zbl 1097.11033
[16] Cavalar, S., et al.: Factorization of a \(512\) -bit RSA modulus. In: Proc. of Eurocrypt’2000, LNCS, vol. 1807, pp. 1–18 (2000) · Zbl 1082.94511
[17] Choie, Y., Jeong, E.: Isomorphism classes of hyperelliptic curves of genus 2 over \(\mathbb{F}_{2^{n}}\) . Cryptology ePrint Archive 2003/213.
[18] Choie, Y., Yun, D.: Isomorphism classes of hyperelliptic curves of genus 2 over \(\mathbb{F}_{q}\) . In: Proc. of ACISP’02, LNCS, vol. 2384, pp. 190–202 (2002) · Zbl 1022.11029
[19] Cohen, H., Frey, G.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, Boca Raton, FL (2006) · Zbl 1082.94001
[20] Coppersmith, D.: Fast evaluation of logarithms in finite fields of characteristic two. IEEE Trans. Inform. Theory 30(4), 587–594 (1984) · Zbl 0554.12013 · doi:10.1109/TIT.1984.1056941
[21] Coppersmith, D., Odlyzko, A., Schroeppel, R.: Discrete logarithms in \(GF(p)\) . Algorithmica 1, 1–15 (1986) · Zbl 0631.12010
[22] Deng, Y., Liu, M.: Isomorphism classes of hyperelliptic curves of genus 2 over finite fields with characteristic 2. Sci. China Ser. A 49(2), 173–184 (2005) · Zbl 1101.14036 · doi:10.1007/s11425-004-0043-4
[23] Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inform. Theory 22, 644–654 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[24] ElGamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithm. IEEE Trans. Inform Theory 31, 469–472 (1985) · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074
[25] Enge, A.: Computing discrete logarithms in high-genus hyperelliptic Jacobians in probably subexponential time. Math. Comp. 71, 729–742 (2002) · Zbl 0988.68069 · doi:10.1090/S0025-5718-01-01363-1
[26] Enge, A., Gaudry, P.: A general framework for subexponential discrete logarithm algorithms. Acta Arith. 1, 83–103 (2002) · Zbl 1028.11079 · doi:10.4064/aa102-1-6
[27] Frey, G., Rück, H.: A remark concerning \(m\) -divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp. 62, 865–874 (1994) · Zbl 0813.14045
[28] Galbratih, S., Menezes, A.: Algebraic curves and cryptography. Finite Fields Appl. 11, 544–577 (2005) · Zbl 1079.94014 · doi:10.1016/j.ffa.2005.05.001
[29] Galbrait, S., Paulus, S., Smart, N.: Arithmetic of superelliptic curves. Math. Comp. 71, 393–405 (2002) · Zbl 1013.11026 · doi:10.1090/S0025-5718-00-01297-7
[30] Gaudry, P.: An algorithm for solving the discrete log problem on hyperelliptic curves. In: Proc. of Eurocrypt 2000, LNCS, vol. 1807, pp. 19–34 (2000) · Zbl 1082.94517
[31] Gaudry, P., Thériault, N., Thomé, E.: A double large prime variation for small genus hyperelliptic index calculus. Cryptology ePrint Archive 2004/153 · Zbl 1179.94062
[32] Gilbert, H., Gupta, D., Odlyzko, A., Quisquater, J.J.: Attacks on Shamir’s ’RSA for paranoids’. Inform Process. Lett. 68(4), 197–199 (1998) · Zbl 1339.94044 · doi:10.1016/S0020-0190(98)00160-4
[33] Hartshorne, R.: Algebraic Geometry. Springer, Berlin Heidelberg New York (1977) · Zbl 0367.14001
[34] Hernández Encinas, L., Menezes, A.J., Muñoz Masqué, J.: Isomorphism classes of genus-2 hyperelliptic curves over finite fields. Appl. Algebra Engrg. Comm. Comput. 13, 57–65 (2002) · Zbl 1066.14026 · doi:10.1007/s002000100092
[35] Hernández Encinas, L., Muñoz Masqué, J.: Isomorphism classes of hyperelliptic curves of genus 2 in characteristic 5. Technical Report CORR2002-07, Centre For Applied Cryptographic Research (CACR), University of Waterloo (2002) · Zbl 1066.14026
[36] Hernández Encinas, L., Muñoz Masqué, J.: Isomorphism classes of genus-2 hyperelliptic curves over finite fields \(\mathbb{F}_{5^{m}}\) . Information 8(6), 8 pp. (2005) · Zbl 1066.14026
[37] Jacobson Jr., M., Menezes, A., Stein, A.: Hyperelliptic curves and cryptography. Technical Report CORR 2003-13, Centre for Applied Cryptography Research (CACR), University of Waterloo (2003) · Zbl 1098.94023
[38] Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48, 203–209 (1987) · Zbl 0622.94015 · doi:10.1090/S0025-5718-1987-0866109-5
[39] Koblitz, N.: Hyperelliptic cryptosystems. J. Cryptology 1, 139–150 (1989) · Zbl 0674.94010 · doi:10.1007/BF02252872
[40] Koblitz, N.: Algebraic Aspects of Cryptography. Springer, Berlin Heidelberg New York (1998) · Zbl 0890.94001
[41] Kurosawa, K., Ito, T., Takeuchi, M.: Public key cryptosystem using a reciprocal number with the same intractability as factoring a large number. Cryptologia 12, 225–233 (1988) · Zbl 0654.94010 · doi:10.1080/0161-118891862972
[42] Lange, T.: Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, Report 2002/121.
[43] Lenstra, A., Verheul, E.: Selecting cryptographic key sizes. In: Proc. of PKC 2000, LNCS, vol. 1751, pp. 446–465 (2000) · Zbl 0972.94502
[44] Lenstra, H.W., Pila, J., Pomerance, C.: A hyperelliptic smoothness test. I. R. Soc. Philos. Trans., Ser. A Math. Phys. Eng. Sci. 345, 397–408 (1993) · Zbl 0808.11073 · doi:10.1098/rsta.1993.0138
[45] Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1994) · Zbl 0820.11072
[46] Lockhart, P.: On the discriminant of a hyperelliptic curve. Trans. Amer. Math. Soc. 342(2), 729–752 (1994) · Zbl 0815.11031 · doi:10.2307/2154650
[47] McCurley, K.: A key distribution system equivalent to factoring. J. Cryptology 1, 95–105 (1988) · Zbl 0659.94003 · doi:10.1007/BF02351718
[48] Menezes, A.: Elliptic Curve Public Key Cryptosystems. Kluwer Academic, Dordrecht (1993) · Zbl 0806.94011
[49] Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory 39, 1639–1646 (1993) · Zbl 0801.94011 · doi:10.1109/18.259647
[50] Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC, Boca Raton, FL (1997) · Zbl 0868.94001
[51] Menezes, A., Wu, Y., Zuccherato, R.: An elementary introduction to hyperelliptic curves. In: Koblitz, N. (ed.) Algebraic Aspects of Cryptography, pp. 155–178. Springer, Berlin Heidelberg New York (1998)
[52] Miller, V.: Uses of elliptic curves in cryptography. In: Proc. of Crypto’85, LNCS, vol. 218, pp. 417–426 (1986)
[53] Müller, V., Stein, A., Thiel, C.: Computing discrete logarithms in real quadratic congruence function fields of large genus. Math. Comp. 68, 807–822 (1999) · Zbl 1036.11064 · doi:10.1090/S0025-5718-99-01040-6
[54] National Institute for Standards and Technology, Digital Signature Standard, FIPS PUB 186 (1993)
[55] National Institute for Standards and Technology, Digital Signature Standard (DSS), FIPS PUB 186-2 (2000)
[56] National Institute for Standards and Technology, Elliptic curve Diffie-Hellman or elliptic curve MQV, Draft NIST Special Publication 800-56 (2003)
[57] Pelzl, J., Wollinger, T., Guajardo, J., Paar, C.: Hyperelliptic curve cryptosystems: closing the performance gap to elliptic curves (update). Cryptology ePrint Archive, Report 2003/026 · Zbl 1274.94105
[58] Pelzl, J., Wollinger, T., Guajardo, J., Paar, C.: Low cost security: Explicit formulae for genus 4 hyperelliptic curves. Cryptology ePrint Archive, Report 2003/097. · Zbl 1274.94105
[59] Pelzl, J., Wollinger, T., Paar, C.: Low cost security: explicit formulae for genus-4 hyperelliptic curves. In: Proc. Tenth Annual Workshop on Selected Areas in Cryptography, LNCS, vol. 3006, pp. 1–16 (2004) · Zbl 1081.94033
[60] Petersen, M.: Hyperelliptic Cryptosystems. Technical Report, University of Aarhus, Denmark (1994)
[61] Pollard, J.: Monte Carlo methods for index computation \(\operatorname{mod}p\) . Math. Comp. 32, 918–924 (1978) · Zbl 0382.10001
[62] Rabin, M.O.: Digitalized signatures and public key functions as intractable as factorization. Technical Report TM-212, Lab. for Computer Science, M.I.T. (1979)
[63] Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342
[64] Schirokauer, O., Weber, D., Denny, T.: Discrete logarithms: the effectiveness of the index calculus method. In: Proc. of Algorithmic Number Theory, LNCS, vol. 1122, pp. 337–361 (1996) · Zbl 0895.11054
[65] Schnorr, C.: Efficient signature generation by smart cards. J. Cryptology 4, 161–174 (1991) · Zbl 0743.68058 · doi:10.1007/BF00196725
[66] Schoof, R.: Elliptic curves over finite fields and the computation of square roots \(\operatorname{mod}p\) . Math. Comp. 44, 483–494 (1985) · Zbl 0579.14025
[67] Shamir, A.: RSA for paranoids. CryptoBytes 1(3), 1, 3 and 4 (1995)
[68] Shamir, A.: Factoring large numbers with the TWINKLE device, (Extended abstract) Eurocrypt’99, Rump session · Zbl 1044.11630
[69] Silverman, J.: The Arithmetic of Elliptic Curves. Springer, Berlin Heidelberg New York (1986) · Zbl 0585.14026
[70] Silverman, J.: Advanced Topics in the Arithmetic of Elliptic Curves. Springer, Berlin Heidelberg New York (1994) · Zbl 0911.14015
[71] Smart, N.: On the performance of hyperelliptic cryptosystems. In: Proc. of Eurocrypt 1999, LNCS, vol. 1592, pp. 165–175 (1999) · Zbl 0938.94010
[72] Takagi, T.: Fast RSA-type cryptosystems using \(N\) -adic expansion. Lecture Notes in Comput. Sci. 1294, 372–384 (1997) · Zbl 0890.94025 · doi:10.1007/BFb0052249
[73] Takagi, T.: Fast RSA-type cryptosystem modulo \(p^{k}q\) . Lecture Notes in Comput. Sci. 1462, 318–326 (1998) · Zbl 0931.94041
[74] Thériault, N.: Index calculus attack for hyperelliptic curves of small genus. In: Proc. of Asiacrypt 2003, LNCS, vol. 2894, pp. 75–92 (2003) · Zbl 1205.94103
[75] Williams, H.C.: A modification of the RSA public-key encryption procedure. IEEE Trans. Inform. Theory 26, 726–729 (1980) · Zbl 0466.94018 · doi:10.1109/TIT.1980.1056264
[76] Williams, H.C.: An \(M^{3}\) public-key encryption scheme. Lecture Notes in Comput. Sci. 218, 358–368 (1986) · Zbl 0612.94010 · doi:10.1007/3-540-39799-X_26
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.