Comparison of scalar multiplication on real hyperelliptic curves

Michael J. Jacobson, Jr.; Monireh Rezai Rad; Renate Scheidler

doi:10.3934/amc.2014.8.389

Article Contents

2014, Volume 8, Issue 4: 389-406. Doi: 10.3934/amc.2014.8.389

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

Comparison of scalar multiplication on real hyperelliptic curves

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

Received: February 28, 2014

Revised: August 31, 2014

Published: October 2014

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.
[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, Boca Raton, 2006.doi: 10.1201/9781420034981.
[3]	W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, 22 (1976), 472-492.doi: 10.1109/TIT.1976.1055638.
[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-666.doi: 10.3934/amc.2011.5.623.
[5]	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.
[6]	F. Fontein, Holes in the infrastructure of global hyperelliptic function fields, preprint, arXiv:0911.4346
[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, PQ), de Gruyter, Berlin, 1989, 227-239.
[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), Springer, 2008, 342-356.doi: 10.1007/978-3-540-79456-1_23.
[9]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic protocols on real hyperelliptic curves, Adv. Math. Commun., 1 (2007), 197-221.doi: 10.3934/amc.2007.1.197.
[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, W.C. Huffman, D. Joyner and V. Ustimenko), World Scientific Publishing, 2007, 201-244.doi: 10.1142/9789812772022_0013.
[11]	M. J. Jacobson, Jr., R. Scheidler and A. Stein, Cryptographic aspects of real hyperelliptic curves, Tatra Mountains Math. Publ., 40 (2010), 1-35.doi: 10.2478/v10127-010-0030-9.
[12]	N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150.doi: 10.1007/BF02252872.
[13]	T. Lange, Formulae for arithmetic on genus 2 hyperelliptic curves, Appl. Algebra Eng. Commun. Comput., 15 (2005), 295-328.doi: 10.1007/s00200-004-0154-8.
[14]	D. J. Mireles Morales, An analysis of the infrastructure in real function fields, Cryptology eprint archive no. 2008/299, 2008.
[15]	R. Scheidler, J. A. Buchmann and H. C. Williams, A key exchange protocol using real quadratic fields, J. Cryptology, 7 (1994), 171-199.doi: 10.1007/BF02318548.
[16]	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.
[17]	V. Shoup, NTL: A Library for doing Number Theory (version 5.4.2), http://www.shoup.net, 2008.
[18]	A. Stein, Explicit infrastructure for real quadratic function fields and real hyperelliptic curves, Glas. Mat. Ser. III, 44(64) (2009), 89-126.doi: 10.3336/gm.44.1.05.