Comparison of scalar multiplication on real hyperelliptic curves

Previous Article
Trisection for supersingular genus $2$ curves in characteristic $2$
AMC Home
This Issue
Next Article
Subexponential time relations in the class group of large degree number fields

November 2014, 8(4): 389-406. doi: 10.3934/amc.2014.8.389

Comparison of scalar multiplication on real hyperelliptic curves

Michael J. Jacobson, Jr. ^1, , Monireh Rezai Rad ^2, and Renate Scheidler ^2,

1.	Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4, Canada
2.	Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4, Canada, Canada

Received March 2014 Revised September 2014 Published November 2014

Abstract
Related Papers

Real hyperelliptic curves admit two structures suitable for cryptography --- the Jacobian (a finite abelian group) and the infrastructure. Mireles Morales described precisely the relationship between these two structures, and made the assertion that when implemented with balanced divisor arithmetic, the Jacobian generically yields more efficient arithmetic than the infrastructure for cryptographic applications. We confirm that this assertion holds for genus two curves, through rigorous analysis and the first detailed numerical performance comparisons, showing that cryptographic key agreement can be performed in the Jacobian without any extra operations beyond those required for basic scalar multiplication. We also present a modified version of Mireles Morales' map that more clearly reveals the algorithmic relationship between the two structures.

Keywords: scalar multiplication, Jacobian, infrastructure, Real hyperelliptic curve, cryptographic key agreement., balanced divisor.

Mathematics Subject Classification: Primary: 11G20, 11R11, 11R29, 11Y40; Secondary: 11Y16, 14G5.

Citation: Michael J. Jacobson, Jr., Monireh Rezai Rad, Renate Scheidler. Comparison of scalar multiplication on real hyperelliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 389-406. doi: 10.3934/amc.2014.8.389

References:

[1]	E. Barker, W. Barker, W. Polk and M. Smid, Recommendation for key management - part 1: General (revised),, NIST Special Publication 800-57, (2007), 800. Google Scholar
[2]	H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercouteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography,, Chapman & Hall/CRC, (2006). doi: 10.1201/9781420034981. Google Scholar
[3]	W. Diffie and M. Hellman, New directions in cryptography,, IEEE Trans. Inf. Theory, 22 (1976), 472. doi: 10.1109/TIT.1976.1055638. Google Scholar
[4]	S. Erickson, M. J. Jacobson, Jr. and A. Stein, Explicit formulas for real hyperelliptic curves of genus $2$ in affine representation,, Adv. Math. Commun., 5 (2011), 623. doi: 10.3934/amc.2011.5.623. Google Scholar
[5]	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
[6]	F. Fontein, Holes in the infrastructure of global hyperelliptic function fields,, preprint, (). Google Scholar
[7]	E. Friedman and L. C. Washington, On the distribution of divisor class groups of curves over a finite field,, Théorie des Nombres (Québec, (1989), 227. Google Scholar
[8]	S. D. Galbraith, M. Harrison and D. J. Mireles Morales, Efficient hyperelliptic curve arithmetic using balanced representation for divisors,, in Algorithmic Number Theory - ANTS 2008 (Berlin), (2008), 342. doi: 10.1007/978-3-540-79456-1_23. Google Scholar
[9]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real hyperelliptic curves,, Adv. Math. Commun., 1 (2007), 197. doi: 10.3934/amc.2007.1.197. Google Scholar
[10]	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*, (2007), 201. doi: 10.1142/9789812772022_0013. Google Scholar
[11]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic aspects of real hyperelliptic curves,, Tatra Mountains Math. Publ., 40 (2010), 1. doi: 10.2478/v10127-010-0030-9. Google Scholar
[12]	N. Koblitz, Hyperelliptic cryptosystems,, J. Cryptology, 1 (1989), 139. doi: 10.1007/BF02252872. Google Scholar
[13]	T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves,, Appl. Algebra Eng. Commun. Comput., 15 (2005), 295. doi: 10.1007/s00200-004-0154-8. Google Scholar
[14]	D. J. Mireles Morales, An analysis of the infrastructure in real function fields,, Cryptology eprint archive no. 2008/299, (2008). Google Scholar
[15]	R. Scheidler, J. A. Buchmann and H. C. Williams, A key exchange protocol using real quadratic fields,, J. Cryptology, 7 (1994), 171. doi: 10.1007/BF02318548. Google Scholar
[16]	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
[17]	V. Shoup, NTL: A Library for doing Number Theory (version 5.4.2),, , (2008). Google Scholar
[18]	A. Stein, Explicit infrastructure for real quadratic function fields and real hyperelliptic curves,, Glas. Mat. Ser. III, 44(64) (2009), 89. doi: 10.3336/gm.44.1.05. Google Scholar

show all references

References:

[1]	E. Barker, W. Barker, W. Polk and M. Smid, Recommendation for key management - part 1: General (revised),, NIST Special Publication 800-57, (2007), 800. Google Scholar
[2]	H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercouteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography,, Chapman & Hall/CRC, (2006). doi: 10.1201/9781420034981. Google Scholar
[3]	W. Diffie and M. Hellman, New directions in cryptography,, IEEE Trans. Inf. Theory, 22 (1976), 472. doi: 10.1109/TIT.1976.1055638. Google Scholar
[4]	S. Erickson, M. J. Jacobson, Jr. and A. Stein, Explicit formulas for real hyperelliptic curves of genus $2$ in affine representation,, Adv. Math. Commun., 5 (2011), 623. doi: 10.3934/amc.2011.5.623. Google Scholar
[5]	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
[6]	F. Fontein, Holes in the infrastructure of global hyperelliptic function fields,, preprint, (). Google Scholar
[7]	E. Friedman and L. C. Washington, On the distribution of divisor class groups of curves over a finite field,, Théorie des Nombres (Québec, (1989), 227. Google Scholar
[8]	S. D. Galbraith, M. Harrison and D. J. Mireles Morales, Efficient hyperelliptic curve arithmetic using balanced representation for divisors,, in Algorithmic Number Theory - ANTS 2008 (Berlin), (2008), 342. doi: 10.1007/978-3-540-79456-1_23. Google Scholar
[9]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real hyperelliptic curves,, Adv. Math. Commun., 1 (2007), 197. doi: 10.3934/amc.2007.1.197. Google Scholar
[10]	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*, (2007), 201. doi: 10.1142/9789812772022_0013. Google Scholar
[11]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic aspects of real hyperelliptic curves,, Tatra Mountains Math. Publ., 40 (2010), 1. doi: 10.2478/v10127-010-0030-9. Google Scholar
[12]	N. Koblitz, Hyperelliptic cryptosystems,, J. Cryptology, 1 (1989), 139. doi: 10.1007/BF02252872. Google Scholar
[13]	T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves,, Appl. Algebra Eng. Commun. Comput., 15 (2005), 295. doi: 10.1007/s00200-004-0154-8. Google Scholar
[14]	D. J. Mireles Morales, An analysis of the infrastructure in real function fields,, Cryptology eprint archive no. 2008/299, (2008). Google Scholar
[15]	R. Scheidler, J. A. Buchmann and H. C. Williams, A key exchange protocol using real quadratic fields,, J. Cryptology, 7 (1994), 171. doi: 10.1007/BF02318548. Google Scholar
[16]	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
[17]	V. Shoup, NTL: A Library for doing Number Theory (version 5.4.2),, , (2008). Google Scholar
[18]	A. Stein, Explicit infrastructure for real quadratic function fields and real hyperelliptic curves,, Glas. Mat. Ser. III, 44(64) (2009), 89. doi: 10.3336/gm.44.1.05. Google Scholar

[1]	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
[2]	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
[3]	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
[4]	Chris Guiver, Mark R. Opmeer. Bounded real and positive real balanced truncation for infinite-dimensional systems. Mathematical Control & Related Fields, 2013, 3 (1) : 83-119. doi: 10.3934/mcrf.2013.3.83
[5]	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
[6]	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
[7]	Francisco Braun, José Ruidival dos Santos Filho. The real jacobian conjecture on $\R^2$ is true when one of the components has degree 3. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 75-87. doi: 10.3934/dcds.2010.26.75
[8]	Bernard Dacorogna, Olivier Kneuss. Multiple Jacobian equations. Communications on Pure & Applied Analysis, 2014, 13 (5) : 1779-1787. doi: 10.3934/cpaa.2014.13.1779
[9]	Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413
[10]	Bertrand Lods. Variational characterizations of the effective multiplication factor of a nuclear reactor core. Kinetic & Related Models, 2009, 2 (2) : 307-331. doi: 10.3934/krm.2009.2.307
[11]	Qichun Wang, Chik How Tan, Pantelimon Stănică. Concatenations of the hidden weighted bit function and their cryptographic properties. Advances in Mathematics of Communications, 2014, 8 (2) : 153-165. doi: 10.3934/amc.2014.8.153
[12]	Ruinian Li, Yinhao Xiao, Cheng Zhang, Tianyi Song, Chunqiang Hu. Cryptographic algorithms for privacy-preserving online applications. Mathematical Foundations of Computing, 2018, 1 (4) : 311-330. doi: 10.3934/mfc.2018015
[13]	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
[14]	Pascale Charpin, Jie Peng. Differential uniformity and the associated codes of cryptographic functions. Advances in Mathematics of Communications, 2019, 13 (4) : 579-600. doi: 10.3934/amc.2019036
[15]	Zsolt Páles, Vera Zeidan. $V$-Jacobian and $V$-co-Jacobian for Lipschitzian maps. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 623-646. doi: 10.3934/dcds.2011.29.623
[16]	Andrew D. Lewis, David R. Tyner. Geometric Jacobian linearization and LQR theory. Journal of Geometric Mechanics, 2010, 2 (4) : 397-440. doi: 10.3934/jgm.2010.2.397
[17]	Ronen Peretz, Nguyen Van Chau, L. Andrew Campbell, Carlos Gutierrez. Iterated images and the plane Jacobian conjecture. Discrete & Continuous Dynamical Systems - A, 2006, 16 (2) : 455-461. doi: 10.3934/dcds.2006.16.455
[18]	Neil S. Trudinger. On the local theory of prescribed Jacobian equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1663-1681. doi: 10.3934/dcds.2014.34.1663
[19]	Yvo Desmedt, Niels Duif, Henk van Tilborg, Huaxiong Wang. Bounds and constructions for key distribution schemes. Advances in Mathematics of Communications, 2009, 3 (3) : 273-293. doi: 10.3934/amc.2009.3.273
[20]	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

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences