Cryptographic aspects of real hyperelliptic curves

Jacobson, Michael J.; Scheidler, Renate; Stein, Andreas

doi:10.2478/v10127-010-0030-9

Abstract

In this paper, we give an overview of cryptographic applications using real hyperelliptic curves. We review previously proposed cryptographic protocols and discuss the infrastructure of a real hyperelliptic curve, the mathematical structure underlying all these protocols. We then describe recent improvements to infrastructure arithmetic, including explicit formulas for divisor arithmetic in genus 2, and advances in solving the infrastructure discrete logarithm problem, whose presumed intractability is the basis of security for the related cryptographic protocols.

References

[1] AVANZI, R.-JACOBSON, M. J., JR.-SCHEIDLER, R.: Efficient reduction of large divisors on hyperelliptic curves, Adv. Math. Communications 4 (2010), 261-279.10.3934/amc.2010.4.261
Search in Google Scholar
[2] BERNSTEIN, D. J.-LANGE, T.: Faster addition and doubling on elliptic curves, in: Advances in Cryptology-ASIACRYPT ’07, Kuching, Malaysia, 2007 (K. Kurosawa, ed.), Lecture Notes in Comput. Sci., Vol. 4833, Springer, Berlin, 2008, pp. 29-50.
Search in Google Scholar
[3] BUCHMANN, J.: A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, in: S´eminaire de Th´eorie des Nombres, Paris, 1988-89, Prog. Math., Vol. 91, 1990, pp. 27-41.
Search in Google Scholar
[4] CANTOR, D. G.: Computing the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), 95-101.10.1090/S0025-5718-1987-0866101-0
Search in Google Scholar
[5] CASSELS, J. W. S.-FLYNN, E. V.: Prolegomena to a Middlebrow Arithmetic of Curvesof Genus 2, in: London Math. Soc. Lecture Note Ser., Vol. 230, Cambridge Univ. Press, Cambridge, 1996.10.1017/CBO9780511526084
Search in Google Scholar
[6] CHEN, Z.-STORJOHANN, A.-FLETCHER, C.: IML: Integer Matrix Library (version 1.0.2), http://www.cs.uwaterloo.ca/ z4chen/iml.html, 2007.
Search in Google Scholar
[7] COHEN, H.-FREY, G.-AVANZI, R.-DOCHE, C.-LANGE, T.-NGUYEN, K.- -VERCAUTEREN, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, in: Discrete Math. Appl., Chapman & Hall/CRC, Boca Raton, FL, 2006.10.1201/9781420034981
Search in Google Scholar
[8] DIFFIE, W.-HELLMAN, M. E.: New directions in cryptography, IEEE Trans. Inform. Theory 22 (1976), 644-654.10.1109/TIT.1976.1055638
Search in Google Scholar
[9] ELGAMAL, V.: A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory IT-31 (1985), 469-472.10.1109/TIT.1985.1057074
Search in Google Scholar
[10] ERICKSON, S.-HO, T.-ZEMEDKUN, S.: Explicit projective formulas for real hyperelliptic curves of genus 2, 2009 (in preparation).
Search in Google Scholar
[11] ERICKSON, S.-JACOBSON,M. J., JR.-SHANG, N.-SHEN, S.-STEIN, A.: Explicit formulas for real hyperelliptic curves of genus 2 in affine representation, in: Proceedings of First InternationalWorkshop-WAIFI ’07, Madrid, 2007 (C. Carlet et al., eds.), Lecture Notes in Comput. Sci., Vol. 4547, Springer, Berlin, 2007, pp. 202-218.
Search in Google Scholar
[12] ERICKSON, S.-JACOBSON, M. J. JR.-STEIN, A.: Explicit formulas for real hyperelliptic curves of genus 2 in affine representation, 2009 (in preparation).
Search in Google Scholar
[13] FONTEIN, F.: Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures, Adv. Math. Commun. 2 (2008), 293-307.10.3934/amc.2008.2.293
Search in Google Scholar
[14] , The Infrastructure of a Global Field and Baby Step-Giant Step Algorithms. Ph.D. Thesis, University of Z¨urich, Z¨urich, Switzerland, 2008.
Search in Google Scholar
[15] GALBRAITH, S. D.-HARRISON, M.-MIRELES MORALES, D. J.: Efficient hyperelliptic curve arithmetic using balanced representation for divisors, in: Algorithmic Number Theory-ANTS ’08, Banff, Canada, 2008 (A. van der Poorten, ed.), Lecture Notes in Comput. Sci., Vol. 5011, Springer, Berlin, 2008, pp. 342-356.
Search in Google Scholar
[16] GALBRAITH, S. D.-LIN, X.-MIRELES MORALES, D. J.: Pairings on hyperelliptic curves with a real model, in: Pairing-Based Cryptography-Pairing ’08 (S. Galbraith, ed.) Egham, UK, 2008, Lecture Notes in Comput. Sci., Vol. 5209, Springer, Berlin, 2008, pp. 265-281.
Search in Google Scholar
[17] GALBRAITH, S. D.-PUJOLAS, J.-RITZENTHALER, C.-SMITH, B.: Distortion maps for supersingular genus two curves, J. Math. Cryptology 3 (2009), 1-18.10.1515/JMC.2009.001
Search in Google Scholar
[18] GAUDRY, P.-THOM´E, E.-TH´ERIAULT, N.-DIEM, C.: A double large prime variation for small genus hyperelliptic index calculus, Math. Comp. 76 (2007), 475-492.10.1090/S0025-5718-06-01900-4
Search in Google Scholar
[19] HAMMELL, J. F.: Index Calculus in the Infrastructure of Real Quadratic Function Fields. Master’s Thesis, University of Calgary, Canada, 2008.
Search in Google Scholar
[20] HAMMELL, J. F.-JACOBSON, M. J., JR.: Index-calculus algorithms in real quadratic function fields, 2009 (in preparation).
Search in Google Scholar
[21] HANKERSON, D.-MENEZES, A.-VANSTONE, S.: Guide to Elliptic Curve Cryptography. Springer, New York, 2004.
Search in Google Scholar
[22] IMBERT, L.-JACOBSON, M. J., JR.-SCHMIDT, A.: Fast ideal cubing in imaginary quadratic number and function fields, Adv. Math. Communications 4 (2010), 237-260.10.3934/amc.2010.4.237
Search in Google Scholar
[23] JACOBSON, M. J., JR.-MENEZES, A. J.-STEIN, A.: Hyperelliptic curves and cryptography, in: Selected papers from the International Conference on Number Theory, Banff, AB, Canada, 2003 (A. van der Poorten, et. al., eds.), Fields Inst. Commun., Vol. 41, Amer. Math. Soc., Providence, RI, 2004, pp. 255-282.10.1090/fic/041/21
Search in Google Scholar
[24] JACOBSON, M. J., JR.-SCHEIDLER, R.-STEIN, A.: Cryptographic protocols on real and imaginary hyperelliptic curves, Adv. Math. Commun. 1 (2007), 197-221.10.3934/amc.2007.1.197
Search in Google Scholar
[25] , Fast arithmetic on hyperelliptic curves via continued fraction expansions, in: Advances in Coding Theory and Cryptology (T. Shaska, T. et al., eds.), Series on Coding Theory and Cryptology, Vol. 3, World Scientific, Hackensack, NJ, 2007, pp. 200-243.10.1142/9789812772022_0013
Search in Google Scholar
[26] JACOBSON, M. J., JR.-STEIN, A.-VELICHKA, M. D.: Computing discrete logarithms on high-genus hyperelliptic curves over even characteristic finite fields (in preparation), 2009.
Search in Google Scholar
[27] JACOBSON, M. J., JR.-VAN DER POORTEN, A. J.: , Computational aspects of NUCOMP, in: Algorithmic Number Theory-ANTS-V, Sydney, Australia, 2002 (C. Fieker et al., eds.), Lecture Notes in Comput. Sci., Vol. 2369, Springer, Berlin, 2002, pp. 120-133.
Search in Google Scholar
[28] KOBLITZ, N.: Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209.10.1090/S0025-5718-1987-0866109-5
Search in Google Scholar
[29] , Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139-150.10.1007/BF02252872
Search in Google Scholar
[30] LANGE, T.: Formulae for arithmetic on genus 2 hyperelliptic curves, Appl. Algebra Engrg. Comm. Comput. 15 (2005), 295-328.10.1007/s00200-004-0154-8
Search in Google Scholar
[31] MENEZES, A. J.-WU, Y.-H.-ZUCCHERATO, R. J.: An elementary introduction to hyperelliptic curves, in: Algebraic Aspects of Cryptography, Algorithms Comput. Math., Vol. 3, Springer, Berlin, 1998, pp. 155-178.
Search in Google Scholar
[32] MILLER, V.: Use of elliptic curves in cryptography, in: Advances in Cryptology- -CRYPTO ’85, Santa Barbara, California, 1985, Lecture Notes in Comput. Sci., Vol. 218, Springer, Berlin, 1986, pp. 417-426.10.1007/3-540-39799-X_31
Search in Google Scholar
[33] MIRELES MORALES, D. J.: An analysis of the infrastructure in real function fields, Eprint archive no. 2008/299, 2008.
Search in Google Scholar
[34] M¨ULLER,V.-STEIN, A.-THIEL, C.: Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), 807-822.10.1090/S0025-5718-99-01040-6
Search in Google Scholar
[35] PAULUS, S.-R¨UCK, H.-G.: Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), 1233-1241.10.1090/S0025-5718-99-01066-2
Search in Google Scholar
[36] POHLIG, S. C.-HELLMAN, M. E.: An improved algorithm for computing logarithms over GF(p) and it’s cryptographic significance, IEEE Trans. Inf. Theory 24 (1978), 106-110.10.1109/TIT.1978.1055817
Search in Google Scholar
[37] SCHEIDLER, R.: Cryptography in quadratic function fields, Des. Codes Cryptogr. 22 (2001), 239-264.10.1023/A:1008346322837
Search in Google Scholar
[38] SCHEIDLER, R.-BUCHMANN, J. A.-WILLIAMS, H. C.: A key exchange protocol using real quadratic fields, J. Cryptology 7 (1994), 171-199.10.1007/BF02318548
Search in Google Scholar
[39] SCHEIDLER, R.-STEIN, A.-WILLIAMS, H. C.: Key-exchange in real quadratic congruence function fields, Des. Codes Cryptogr. 7 (1996), 153-174.
Search in Google Scholar
[40] SHANKS, D.: The infrastructure of a real quadratic field and its applications, in: Proceedings of Number Theory Conf., Univ. Colorado, Boulder, Colorado, 1972, pp. 217-224.
Search in Google Scholar
[41] SHOUP, V.: NTL: A Library for doing Number Theory (version 5.4.2), 2008, http://www.shoup.net.
Search in Google Scholar
[42] STEIN, A.: Equivalences between elliptic curves and real quadratic congruence function fields, J. Th´eorie Nombr. Bordeaux 9 (1997), 75-95.10.5802/jtnb.191
Search in Google Scholar
[43] , Sharp upper bounds for arithmetics in hyperelliptic function fields, J. Ramanujan Math. Soc. 16 (2001), 1-86.
Search in Google Scholar
[44] STEIN, A.-TESKE, E.: Explicit bounds and heuristics on class numbers in hyperelliptic function fields, Math. Comp. 71 (2002), 837-861.10.1090/S0025-5718-01-01385-0
Search in Google Scholar
[45] , The parallelized Pollard kangaroo method in real quadratic function fields, Math. Comp. 71 (2002), 793-814.
Search in Google Scholar
[46] , Optimized baby-step giant-step methods in hyperelliptic function fields, J. Ramanujan Math. Soc. 20 (2005), 1-32.
Search in Google Scholar
[47] STICHTENOTH, H.: Algebraic Function Fields and Codes (2nd ed.), Springer, Berlin, 2009.10.1007/978-3-540-76878-4
Search in Google Scholar
[48] VELICHKA, M. D.: Improvements to Index Calculus Algorithms for Solving the HyperellipticCurve Discrete Logarithm Problem Over Characteristic Two Finite Fields. Master’s thesis, University of Calgary, Calgary, Canada, 2008.
Search in Google Scholar

Cryptographic aspects of real hyperelliptic curves

Abstract

Paradigm

My account