# American Institute of Mathematical Sciences

November  2011, 5(4): 623-666. doi: 10.3934/amc.2011.5.623

## Explicit formulas for real hyperelliptic curves of genus 2 in affine representation

 1 Department of Mathematics and Computer Science, Colorado College, 14 E. Cache La Poudre, Colorado Springs, CO 80903, United States 2 Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada 3 Institut für Mathematik, Carl-von-Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany

Received  September 2010 Revised  June 2011 Published  November 2011

We present a complete set of efficient explicit formulas for arithmetic in the degree $0$ divisor class group of a genus two real hyperelliptic curve given in affine coordinates. In addition to formulas suitable for curves defined over an arbitrary finite field, we give simplified versions for both the odd and the even characteristic cases. Formulas for baby steps, inverse baby steps, divisor addition, doubling, and special cases such as adding a degenerate divisor are provided, with variations for divisors given in reduced and adapted basis. We describe the improvements and the correctness together with a comprehensive analysis of the number of field operations for each operation. Finally, we perform a direct comparison of cryptographic protocols using explicit formulas for real hyperelliptic curves with the corresponding protocols presented in the imaginary model.
Citation: Stefan Erickson, Michael J. Jacobson, Jr., Andreas Stein. Explicit formulas for real hyperelliptic curves of genus 2 in affine representation. Advances in Mathematics of Communications, 2011, 5 (4) : 623-666. doi: 10.3934/amc.2011.5.623
##### References:
 [1] R. M. Avanzi, Aspects of hyperelliptic curves over large prime fields in software implementations,, in, (2004), 148. Google Scholar [2] H. Cohen and G. Frey (editors), "Handbook of Elliptic and Hyperelliptic Curve Cryptography,'', Chapman & Hall/CRC, (2005). Google Scholar [3] P. Gaudry, E. Thomé, N. Thériault and C. Diem, A double large prime variation for small genus hyperelliptic index calculus,, Math. Comput., 76 (2007), 475. doi: 10.1090/S0025-5718-06-01900-4. Google Scholar [4] A. Enge, How to distinguish hyperelliptic curves in even characteristic,, in, (2001), 49. Google Scholar [5] S. Erickson, T. Ho and S. Zemedkun, Explicit projective formulas for real hyperelliptic curves of genus $2$,, preprint., (). Google Scholar [6] S. Erickson, M. J. Jacobson, Jr., N. Shang, S. Shen and A. Stein, Explicit formulas for real hyperelliptic curves of genus $2$ in affine representation,, in, (2007), 202. Google Scholar [7] F. Fontein, Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures,, Adv. Math. Commun., 2 (2008), 293. doi: 10.3934/amc.2008.2.293. Google Scholar [8] F. Fontein, "The Infrastructure of a Global Field and Baby Step-Giant Step Algorithms,'', Ph.D thesis, (2008). Google Scholar [9] S. D. Galbraith, M. Harrison and D. J. Mireles Morales, Efficient hyperelliptic arithmetic using balanced representation for divisors,, in, (2008), 342. Google Scholar [10] S. D. Galbraith, X. Lin and D. J. Mireles Morales, Pairings on hyperelliptic curves with a real model,, in, (2008), 265. Google Scholar [11] P. Gaudry, On breaking the discrete log on hyperelliptic curves,, in, (2000), 19. Google Scholar [12] M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Hyperelliptic curves and cryptography,, in, (2004), 255. Google Scholar [13] M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real and imaginary hyperelliptic curves,, Adv. Math. Commun., 1 (2007), 197. doi: 10.3934/amc.2007.1.197. Google Scholar [14] M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions,, in, (2007), 201. doi: 10.1142/9789812772022_0013. Google Scholar [15] N. Koblitz, Hyperelliptic cryptosystems,, J. Cryptology, 1 (1988), 139. doi: 10.1007/BF02252872. Google Scholar [16] T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves,, Appl. Algebra Engin. Commun. Comput., 15 (2005), 295. doi: 10.1007/s00200-004-0154-8. Google Scholar [17] D. J. Mireles Morales, An analysis of the infrastructure in real function fields,, eprint archive, (2008). Google Scholar [18] V. Müller, A. Stein and C. Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus,, Math. Comput., 68 (1999), 807. doi: 10.1090/S0025-5718-99-01040-6. Google Scholar [19] D. Mumford, "Tata Lectures on Theta I, II,'', Birkhäuser, (1983). Google Scholar [20] A. J. Menezes, Y. Wu and R. J. Zuccherato, An elementary introduction to hyperelliptic curves,, in, (1998). Google Scholar [21] National Institute of Standards and Technology, Recommendation on key establishment schemes,, NIST Special Publication, (2003). Google Scholar [22] S. Paulus and H.-G. Rück, Real and imaginary quadratic representations of hyperelliptic function fields,, Math. Comput., 68 (1999), 1233. doi: 10.1090/S0025-5718-99-01066-2. Google Scholar [23] J. Pelzl, T. Wollinger and C. Paar, Low cost security: explicit formulae for genus-4 hyperelliptic curves,, in, (2003), 1. Google Scholar [24] R. Scheidler, Cryptography in quadratic function fields,, Des. Codes Crypt., 22 (2001), 239. doi: 10.1023/A:1008346322837. Google Scholar [25] R. Scheidler, A. Stein and H. C. Williams, Key-exchange in real quadratic congruence function fields,, Des. Codes Crypt., 7 (1996), 153. doi: 10.1007/BF00125081. Google Scholar [26] V. Shoup, NTL: A library for doing number theory,, Software, (2001). Google Scholar [27] A. Stein, Sharp upper bounds for arithmetics in hyperelliptic function fields,, J. Ramanujan Math. Soc., 9-16 (2001), 9. Google Scholar [28] T. Wollinger, J. Pelzl and C. Paar, Cantor versus Harley: optimization and analysis of explicit formulae for hyperelliptic curve cryptosystems,, IEEE Trans. Comp., 54 (2005), 861. doi: 10.1109/TC.2005.109. Google Scholar

show all references

##### References:
 [1] R. M. Avanzi, Aspects of hyperelliptic curves over large prime fields in software implementations,, in, (2004), 148. Google Scholar [2] H. Cohen and G. Frey (editors), "Handbook of Elliptic and Hyperelliptic Curve Cryptography,'', Chapman & Hall/CRC, (2005). Google Scholar [3] P. Gaudry, E. Thomé, N. Thériault and C. Diem, A double large prime variation for small genus hyperelliptic index calculus,, Math. Comput., 76 (2007), 475. doi: 10.1090/S0025-5718-06-01900-4. Google Scholar [4] A. Enge, How to distinguish hyperelliptic curves in even characteristic,, in, (2001), 49. Google Scholar [5] S. Erickson, T. Ho and S. Zemedkun, Explicit projective formulas for real hyperelliptic curves of genus $2$,, preprint., (). Google Scholar [6] S. Erickson, M. J. Jacobson, Jr., N. Shang, S. Shen and A. Stein, Explicit formulas for real hyperelliptic curves of genus $2$ in affine representation,, in, (2007), 202. Google Scholar [7] F. Fontein, Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures,, Adv. Math. Commun., 2 (2008), 293. doi: 10.3934/amc.2008.2.293. Google Scholar [8] F. Fontein, "The Infrastructure of a Global Field and Baby Step-Giant Step Algorithms,'', Ph.D thesis, (2008). Google Scholar [9] S. D. Galbraith, M. Harrison and D. J. Mireles Morales, Efficient hyperelliptic arithmetic using balanced representation for divisors,, in, (2008), 342. Google Scholar [10] S. D. Galbraith, X. Lin and D. J. Mireles Morales, Pairings on hyperelliptic curves with a real model,, in, (2008), 265. Google Scholar [11] P. Gaudry, On breaking the discrete log on hyperelliptic curves,, in, (2000), 19. Google Scholar [12] M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Hyperelliptic curves and cryptography,, in, (2004), 255. Google Scholar [13] M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real and imaginary hyperelliptic curves,, Adv. Math. Commun., 1 (2007), 197. doi: 10.3934/amc.2007.1.197. Google Scholar [14] M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions,, in, (2007), 201. doi: 10.1142/9789812772022_0013. Google Scholar [15] N. Koblitz, Hyperelliptic cryptosystems,, J. Cryptology, 1 (1988), 139. doi: 10.1007/BF02252872. Google Scholar [16] T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves,, Appl. Algebra Engin. Commun. Comput., 15 (2005), 295. doi: 10.1007/s00200-004-0154-8. Google Scholar [17] D. J. Mireles Morales, An analysis of the infrastructure in real function fields,, eprint archive, (2008). Google Scholar [18] V. Müller, A. Stein and C. Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus,, Math. Comput., 68 (1999), 807. doi: 10.1090/S0025-5718-99-01040-6. Google Scholar [19] D. Mumford, "Tata Lectures on Theta I, II,'', Birkhäuser, (1983). Google Scholar [20] A. J. Menezes, Y. Wu and R. J. Zuccherato, An elementary introduction to hyperelliptic curves,, in, (1998). Google Scholar [21] National Institute of Standards and Technology, Recommendation on key establishment schemes,, NIST Special Publication, (2003). Google Scholar [22] S. Paulus and H.-G. Rück, Real and imaginary quadratic representations of hyperelliptic function fields,, Math. Comput., 68 (1999), 1233. doi: 10.1090/S0025-5718-99-01066-2. Google Scholar [23] J. Pelzl, T. Wollinger and C. Paar, Low cost security: explicit formulae for genus-4 hyperelliptic curves,, in, (2003), 1. Google Scholar [24] R. Scheidler, Cryptography in quadratic function fields,, Des. Codes Crypt., 22 (2001), 239. doi: 10.1023/A:1008346322837. Google Scholar [25] R. Scheidler, A. Stein and H. C. Williams, Key-exchange in real quadratic congruence function fields,, Des. Codes Crypt., 7 (1996), 153. doi: 10.1007/BF00125081. Google Scholar [26] V. Shoup, NTL: A library for doing number theory,, Software, (2001). Google Scholar [27] A. Stein, Sharp upper bounds for arithmetics in hyperelliptic function fields,, J. Ramanujan Math. Soc., 9-16 (2001), 9. Google Scholar [28] T. Wollinger, J. Pelzl and C. Paar, Cantor versus Harley: optimization and analysis of explicit formulae for hyperelliptic curve cryptosystems,, IEEE Trans. Comp., 54 (2005), 861. doi: 10.1109/TC.2005.109. Google Scholar
 [1] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [2] M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197 [3] Xinwei Gao. Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants. Advances in Mathematics of Communications, 2019, 13 (2) : 221-233. doi: 10.3934/amc.2019015 [4] Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247 [5] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [6] Haibo Yi. Efficient systolic multiplications in composite fields for cryptographic systems. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1135-1145. doi: 10.3934/dcdss.2019078 [7] Roberto Avanzi, Michael J. Jacobson, Jr., Renate Scheidler. Efficient reduction of large divisors on hyperelliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 261-279. doi: 10.3934/amc.2010.4.261 [8] Laurent Imbert, Michael J. Jacobson, Jr.. Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$. Advances in Mathematics of Communications, 2013, 7 (4) : 485-502. doi: 10.3934/amc.2013.7.485 [9] Roberto Avanzi, Nicolas Thériault. A filtering method for the hyperelliptic curve index calculus and its analysis. Advances in Mathematics of Communications, 2010, 4 (2) : 189-213. doi: 10.3934/amc.2010.4.189 [10] Azniv Kasparian, Ivan Marinov. Duursma's reduced polynomial. Advances in Mathematics of Communications, 2017, 11 (4) : 647-669. doi: 10.3934/amc.2017048 [11] Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022 [12] Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023 [13] Mohammad Sadeq Dousti, Rasool Jalili. FORSAKES: A forward-secure authenticated key exchange protocol based on symmetric key-evolving schemes. Advances in Mathematics of Communications, 2015, 9 (4) : 471-514. doi: 10.3934/amc.2015.9.471 [14] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 [15] Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. [16] Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134 [17] Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028 [18] Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 [19] Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417 [20] Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

2018 Impact Factor: 0.879