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

Previous Article
Fast multi-sequence shift-register synthesis with the Euclidean algorithm
AMC Home
This Issue
Next Article
On the number of bent functions from iterative constructions: lower bounds and hypotheses

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

Stefan Erickson ^1, , Michael J. Jacobson, Jr. ^2, and Andreas Stein ^3,

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

Abstract
Related Papers

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.

Keywords: Cantor’s algorithm, efficient implementation, reduced divisor, infrastructure and distance, cryptographic key exchange., explicit formulas, Hyperelliptic curve.

Mathematics Subject Classification: Primary: 94A60, 14H45; Secondary: 14Q0.

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 "Cryptographic Hardware and Embedded Systems--CHES 2004,'' Springer-Verlag, (2004), 148-162.
[2]	H. Cohen and G. Frey (editors), "Handbook of Elliptic and Hyperelliptic Curve Cryptography,'' Chapman & Hall/CRC, 2005.
[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-492. doi: 10.1090/S0025-5718-06-01900-4.
[4]	A. Enge, How to distinguish hyperelliptic curves in even characteristic, in "Public-Key Cryptography and Computational Number Theory'' (eds. K. Alster, J. Urbanowicz and H.C. Williams), De Gruyter, (2001), 49-58.
[5]	S. Erickson, T. Ho and S. Zemedkun, Explicit projective formulas for real hyperelliptic curves of genus $2$,, preprint., ().
[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 "WAIFI 2007'' (eds. C. Carlet and B. Sunar), Springer-Verlag, (2007), 202-218.
[7]	F. Fontein, Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures, Adv. Math. Commun., 2 (2008), 293-307. doi: 10.3934/amc.2008.2.293.
[8]	F. Fontein, "The Infrastructure of a Global Field and Baby Step-Giant Step Algorithms,'' Ph.D thesis, University of Zürich, Zürich, Switzerland, 2008.
[9]	S. D. Galbraith, M. Harrison and D. J. Mireles Morales, Efficient hyperelliptic arithmetic using balanced representation for divisors, in "ANTS VIII'' (eds. A.J. van der Poorten and A. Stein), Springer-Verlag, (2008), 342-356.
[10]	S. D. Galbraith, X. Lin and D. J. Mireles Morales, Pairings on hyperelliptic curves with a real model, in "Pairing 08,'' Springer-Verlag, (2008), 265-281.
[11]	P. Gaudry, On breaking the discrete log on hyperelliptic curves, in "Advances in Cryptology - Eurocrypt'2000,'' Springer-Verlag, (2000), 19-34.
[12]	M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Hyperelliptic curves and cryptography, in "High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams,'' American Mathematical Society, (2004), 255-282.
[13]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real and imaginary hyperelliptic curves, Adv. Math. Commun., 1 (2007), 197-221. doi: 10.3934/amc.2007.1.197.
[14]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions, in "Advances in Coding Theory and Cryptology'' (eds. T. Shaska, W.C. Huffman, D. Joyner and V. Ustimenko), World Scientific Publishing, (2007), 201-244. doi: 10.1142/9789812772022_0013.
[15]	N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1988), 139-150. doi: 10.1007/BF02252872.
[16]	T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves, Appl. Algebra Engin. Commun. Comput., 15 (2005), 295-328. doi: 10.1007/s00200-004-0154-8.
[17]	D. J. Mireles Morales, An analysis of the infrastructure in real function fields, eprint archive, No. 2008/299, 2008.
[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-822. doi: 10.1090/S0025-5718-99-01040-6.
[19]	D. Mumford, "Tata Lectures on Theta I, II,'' Birkhäuser, Boston, 1983/84.
[20]	A. J. Menezes, Y. Wu and R. J. Zuccherato, An elementary introduction to hyperelliptic curves, in "Algebraic Aspects of Cryptography'' (ed. N. Koblitz), Springer-Verlag, Berlin, Heidelberg, New York, (1998).
[21]	National Institute of Standards and Technology, Recommendation on key establishment schemes, NIST Special Publication, 2003.
[22]	S. Paulus and H.-G. Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comput., 68 (1999), 1233-1241. doi: 10.1090/S0025-5718-99-01066-2.
[23]	J. Pelzl, T. Wollinger and C. Paar, Low cost security: explicit formulae for genus-4 hyperelliptic curves, in "Selected Areas in Cryptography - SAC 2003,'' Springer-Verlag, (2003), 1-16.
[24]	R. Scheidler, Cryptography in quadratic function fields, Des. Codes Crypt., 22 (2001), 239-264. doi: 10.1023/A:1008346322837.
[25]	R. Scheidler, A. Stein and H. C. Williams, Key-exchange in real quadratic congruence function fields, Des. Codes Crypt., 7 (1996), 153-174. doi: 10.1007/BF00125081.
[26]	V. Shoup, NTL: A library for doing number theory, Software, 2001, available online at http://www.shoup.net/ntl
[27]	A. Stein, Sharp upper bounds for arithmetics in hyperelliptic function fields, J. Ramanujan Math. Soc., 9-16 (2001), 1-86.
[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-872. doi: 10.1109/TC.2005.109.

show all references

References:

[1]	R. M. Avanzi, Aspects of hyperelliptic curves over large prime fields in software implementations, in "Cryptographic Hardware and Embedded Systems--CHES 2004,'' Springer-Verlag, (2004), 148-162.
[2]	H. Cohen and G. Frey (editors), "Handbook of Elliptic and Hyperelliptic Curve Cryptography,'' Chapman & Hall/CRC, 2005.
[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-492. doi: 10.1090/S0025-5718-06-01900-4.
[4]	A. Enge, How to distinguish hyperelliptic curves in even characteristic, in "Public-Key Cryptography and Computational Number Theory'' (eds. K. Alster, J. Urbanowicz and H.C. Williams), De Gruyter, (2001), 49-58.
[5]	S. Erickson, T. Ho and S. Zemedkun, Explicit projective formulas for real hyperelliptic curves of genus $2$,, preprint., ().
[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 "WAIFI 2007'' (eds. C. Carlet and B. Sunar), Springer-Verlag, (2007), 202-218.
[7]	F. Fontein, Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures, Adv. Math. Commun., 2 (2008), 293-307. doi: 10.3934/amc.2008.2.293.
[8]	F. Fontein, "The Infrastructure of a Global Field and Baby Step-Giant Step Algorithms,'' Ph.D thesis, University of Zürich, Zürich, Switzerland, 2008.
[9]	S. D. Galbraith, M. Harrison and D. J. Mireles Morales, Efficient hyperelliptic arithmetic using balanced representation for divisors, in "ANTS VIII'' (eds. A.J. van der Poorten and A. Stein), Springer-Verlag, (2008), 342-356.
[10]	S. D. Galbraith, X. Lin and D. J. Mireles Morales, Pairings on hyperelliptic curves with a real model, in "Pairing 08,'' Springer-Verlag, (2008), 265-281.
[11]	P. Gaudry, On breaking the discrete log on hyperelliptic curves, in "Advances in Cryptology - Eurocrypt'2000,'' Springer-Verlag, (2000), 19-34.
[12]	M. J. Jacobson, Jr., A. J. Menezes and A. Stein, Hyperelliptic curves and cryptography, in "High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams,'' American Mathematical Society, (2004), 255-282.
[13]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real and imaginary hyperelliptic curves, Adv. Math. Commun., 1 (2007), 197-221. doi: 10.3934/amc.2007.1.197.
[14]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions, in "Advances in Coding Theory and Cryptology'' (eds. T. Shaska, W.C. Huffman, D. Joyner and V. Ustimenko), World Scientific Publishing, (2007), 201-244. doi: 10.1142/9789812772022_0013.
[15]	N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1988), 139-150. doi: 10.1007/BF02252872.
[16]	T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves, Appl. Algebra Engin. Commun. Comput., 15 (2005), 295-328. doi: 10.1007/s00200-004-0154-8.
[17]	D. J. Mireles Morales, An analysis of the infrastructure in real function fields, eprint archive, No. 2008/299, 2008.
[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-822. doi: 10.1090/S0025-5718-99-01040-6.
[19]	D. Mumford, "Tata Lectures on Theta I, II,'' Birkhäuser, Boston, 1983/84.
[20]	A. J. Menezes, Y. Wu and R. J. Zuccherato, An elementary introduction to hyperelliptic curves, in "Algebraic Aspects of Cryptography'' (ed. N. Koblitz), Springer-Verlag, Berlin, Heidelberg, New York, (1998).
[21]	National Institute of Standards and Technology, Recommendation on key establishment schemes, NIST Special Publication, 2003.
[22]	S. Paulus and H.-G. Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comput., 68 (1999), 1233-1241. doi: 10.1090/S0025-5718-99-01066-2.
[23]	J. Pelzl, T. Wollinger and C. Paar, Low cost security: explicit formulae for genus-4 hyperelliptic curves, in "Selected Areas in Cryptography - SAC 2003,'' Springer-Verlag, (2003), 1-16.
[24]	R. Scheidler, Cryptography in quadratic function fields, Des. Codes Crypt., 22 (2001), 239-264. doi: 10.1023/A:1008346322837.
[25]	R. Scheidler, A. Stein and H. C. Williams, Key-exchange in real quadratic congruence function fields, Des. Codes Crypt., 7 (1996), 153-174. doi: 10.1007/BF00125081.
[26]	V. Shoup, NTL: A library for doing number theory, Software, 2001, available online at http://www.shoup.net/ntl
[27]	A. Stein, Sharp upper bounds for arithmetics in hyperelliptic function fields, J. Ramanujan Math. Soc., 9-16 (2001), 1-86.
[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-872. doi: 10.1109/TC.2005.109.

[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]	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
[7]	Haibo Yi. Efficient systolic multiplications in composite fields for cryptographic systems. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1135-1145. doi: 10.3934/dcdss.2019078
[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]	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
[12]	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
[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]	Cécilia Tarpau, Javier Cebeiro, Geneviève Rollet, Maï K. Nguyen, Laurent Dumas. Analytical reconstruction formula with efficient implementation for a modality of Compton scattering tomography with translational geometry. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2021075
[17]	Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[18]	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
[19]	Zhiguang Zhang, Qiang Liu, Tianling Gao. A fast explicit diffusion algorithm of fractional order anisotropic diffusion for image denoising. Inverse Problems and Imaging, 2021, 15 (6) : 1451-1469. doi: 10.3934/ipi.2021018
[20]	John D. Towers. An explicit finite volume algorithm for vanishing viscosity solutions on a network. Networks and Heterogeneous Media, 2022, 17 (1) : 1-13. doi: 10.3934/nhm.2021021

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Stefan Erickson Michael J. Jacobson, Jr. Andreas Stein
on Google Scholar
Stefan Erickson Michael J. Jacobson, Jr. Andreas Stein

[Back to Top]