Abstract
We derive an explicit method of computing the composition step in Cantor’s algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor’s general composition involves arithmetic in the polynomial ring \(\mathbb{F}_q[x]\), the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of the group elements.
We apply this method to give more efficient formulas for group operations in both affine and projective coordinates for cryptographic systems based on Jacobians of genus 2 hyperelliptic curves in general form.
Chapter PDF
Similar content being viewed by others
References
Abu Salem, F.K., Khuri-Makdisi, K.: Fast Jacobian group operations for C 3,4 curves over a large finite field. CoRR, abs/math/0610121 (2006)
Avanzi, R., Thériault, N., Wang, Z.: Rethinking low genus hyperelliptic Jacobian arithmetic over binary fields: interplay of field arithmetic and explicit formulæ. J. Math. Crypt. 2(3), 227–255 (2008)
Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: The Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC (2005)
Bernstein, D.J.: Elliptic vs. hyperelliptic, part I. Talk at ECC (September 2006)
Bernstein, D.J., Lange, T.: Explicit-formulas database, http://www.hyperelliptic.org/EFD
Cantor, D.G.: Computing in the Jacobian of a hyperelliptic curve. Math. Comp. 48(177), 95–101 (1987)
Ciet, M., Joye, M., Lauter, K., Montgomery, P.L.: Trading inversions for multiplications in elliptic curve cryptography. Designs, Codes and Cryptography 39(2), 189–206 (2006)
Diem, C.: An Index Calculus Algorithm for Plane Curves of Small Degree. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 543–557. Springer, Heidelberg (2006)
Doche, C., Icart, T., Kohel, D.R.: Efficient scalar multiplication by isogeny decompositions. In: PKC 2006 [54], pp. 191–206 (2006)
Eisenträger, K., Lauter, K., Montgomery, P.L.: Fast Elliptic Curve Arithmetic and Improved Weil Pairing Evaluation. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 343–354. Springer, Heidelberg (2003)
Erickson, S., Jacobson Jr., M.J., Shang, N., Shen, S., Stein, A.: Explicit Formulas for Real Hyperelliptic Curves of Genus 2 in Affine Representation. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 202–218. Springer, Heidelberg (2007)
Fan, X., Gong, G., Jao, D.: Efficient Pairing Computation on Genus 2 Curves in Projective Coordinates. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 18–34. Springer, Heidelberg (2009)
Flon, S., Oyono, R., Ritzenthaler, a.C.: Fast addition on non-hyperelliptic genus 3 curves. Algebraic geometry and its applications 5(3), 227–256 (2008)
Flon, S., Oyono, R.: Fast Arithmetic on Jacobians of Picard Curves. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 55–68. Springer, Heidelberg (2004)
Galbraith, S.D.: Mathematics of Public Key Cryptography, 0.9 edition (February 11, 2011), http://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html
Galbraith, S.D., Harrison, M., Mireles Morales, D.J.: Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp. 342–356. Springer, Heidelberg (2008)
Gaudry, P.: An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 19–34. Springer, Heidelberg (2000)
Gaudry, P.: Hyperelliptic curves and the HCDLP. London Mathematical Society Lecture Notes, vol. 317, ch.VII, pp. 133–150. Cambridge University Press (2005)
Gaudry, P.: Fast genus 2 arithmetic based on Theta functions. J. Math. Crypt. 1(3), 243–265 (2007)
Gaudry, P., Harley, R.: Counting Points on Hyperelliptic Curves Over Finite Fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 313–332. Springer, Heidelberg (2000)
Gaudry, P., Thomé, E., Thériault, N., Diem, C.: A double large prime variation for small genus hyperelliptic index calculus. Math. Comp. 76(257), 475–492 (2007)
Gonda, M., Matsuo, K., Aoki, K., Chao, J., Tsujii, S.: Improvements of addition algorithm on genus 3 hyperelliptic curves and their implementation. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 89–96 (2005)
Gurot, C., Kaveh, K., Patankar, V.M.: Explicit algorithm for the arithmetic on the hyperelliptic Jacobians of genus 3. Journal of the Ramanujan Mathematical Society 19, 75–115 (2004)
Harley, R.: Fast arithmetic on genus 2 curves, for C source code and further explanations, http://cristal.inria.fr/~harley/hyper
Hess, F.: Computing Riemann-Roch spaces in algebraic function fields and related topics. J. Symb. Comput. 33(4), 425–445 (2002)
Hisil, H.: Elliptic curves, group law, and efficient computation. PhD thesis, Queensland University of Technology (2010)
Huang, M.A., Ierardi, D.: Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve. J. Symb. Comput. 18(6), 519–539 (1994)
Katagi, M., Kitamura, I., Akishita, T., Takagi, T.: Novel Efficient Implementations of Hyperelliptic Curve Cryptosystems using Degenerate Divisors. In: Lim, C.H., Yung, M. (eds.) WISA 2004. LNCS, vol. 3325, pp. 345–359. Springer, Heidelberg (2005)
Khuri-Makdisi, K.: Linear algebra algorithms for divisors on an algebraic curve. Math. Comp. 73(245), 333–357 (2004)
Khuri-Makdisi, K.: Asymptotically fast group operations on jacobians of general curves. Math. Comp. 76(260), 2213–2239 (2007)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48(177), 203–209 (1987)
Koblitz, N.: Hyperelliptic cryptosystems. J. Cryptology 1(3), 139–150 (1989)
Lang, S.: Introduction to algebraic geometry. Addison-Wesley (1972)
Lange, T.: Efficient arithmetic on hyperelliptic curves. PhD thesis, Universität-Gesamthochschule Essen (2001)
Lange, T.: Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae. Cryptology ePrint Archive, Report 2002/121 (2002), http://eprint.iacr.org/
Lange, T.: Inversion-free arithmetic on genus 2 hyperelliptic curves. Cryptology ePrint Archive, Report 2002/147 (2002), http://eprint.iacr.org/
Lange, T.: Weighted coordinates on genus 2 hyperelliptic curves. Cryptology ePrint Archive, Report 2002/153 (2002), http://eprint.iacr.org/
Lange, T.: Formulae for arithmetic on genus 2 hyperelliptic curves. Appl. Algebra Eng. Commun. Comput. 15(5), 295–328 (2005)
Lange, T.: Elliptic vs. hyperelliptic, part II. Talk at ECC (September 2006)
Lauter, K.: The equivalence of the geometric and algebraic group laws for Jacobians of genus 2 curves. Topics in Algebraic and Noncommutative Geometry 324, 165–171 (2003)
Lauter, K., Montgomery, P.L., Naehrig, M.: An Analysis of Affine Coordinates for Pairing Computation. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 1–20. Springer, Heidelberg (2010)
Leitenberger, F.: About the group law for the Jacobi variety of a hyperelliptic curve. Contributions to Algebra and Geometry 46(1), 125–130 (2005)
Matsuo, K., Chao, J., Tsujii, S.: Fast genus two hyperelliptic curve cryptosystems. Technical Report 214, IEIC (2001)
Miller, V.S.: Use of Elliptic Curves in Cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Miyamoto, Y., Doi, H., Matsuo, K., Chao, J., Tsujii, S.: A fast addition algorithm of genus two hyperelliptic curve. In: Symposium on Cryptography and Information Security - SCICS (2002) (in Japanese)
Mumford, D.: Tata lectures on theta II. In: Progress in Mathematics, vol. 43. Birkhiauser Boston Inc., Boston (1984)
Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comp. 32(143), 918–924 (1978)
Smith, B.: Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves. Journal of Cryptology 22(4), 505–529 (2009)
Sugizaki, H., Matsuo, K., Chao, J., Tsujii, S.: An extension of Harley addition algorithm for hyperelliptic curves over finite fields of characteristic two. Technical Report ISEC2002-9(2002-5), IEICE (2002)
Takahashi, M.: Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves. In: Symposium on Cryptography and Information Security - SCICS (2002) (in Japanese)
Wollinger, T.: Software and hardware implementation of hyperelliptic curve cryptosystems. PhD thesis, Ruhr-University of Bochum (2004)
Wollinger, T., Kovtun, V.: Fast explicit formulae for genus 2 hyperelliptic curves using projective coordinates. In: Fourth International Conference on Information Technology, pp. 893–897 (2007)
Wollinger, T., Pelzl, J., Paar, C.: Cantor versus Harley: optimization and analysis of explicit formulae for hyperelliptic curve cryptosystems. IEEE Transactions on Computers, 861–872 (2005)
Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.): PKC 2006. LNCS, vol. 3958. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Costello, C., Lauter, K. (2012). Group Law Computations on Jacobians of Hyperelliptic Curves. In: Miri, A., Vaudenay, S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28496-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-28496-0_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28495-3
Online ISBN: 978-3-642-28496-0
eBook Packages: Computer ScienceComputer Science (R0)