American Institute of Mathematical Sciences

Advanced
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

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]

Akbar Mahmoodi Rishakani, Seyed Mojtaba Dehnavi, Mohmmadreza Mirzaee Shamsabad, Nasour Bagheri. Cryptographic properties of cyclic binary matrices. Advances in Mathematics of Communications, 2021, 15 (2) : 311-327. doi: 10.3934/amc.2020068
[2]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271
[3]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082
[4]

Yuxi Zheng. Absorption of characteristics by sonic curve of the two-dimensional Euler equations. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 605-616. doi: 10.3934/dcds.2009.23.605
[5]

Takiko Sasaki. Convergence of a blow-up curve for a semilinear wave equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1133-1143. doi: 10.3934/dcdss.2020388
[6]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[7]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[8]

Masaharu Taniguchi. Axisymmetric traveling fronts in balanced bistable reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3981-3995. doi: 10.3934/dcds.2020126
[9]

Joan Carles Tatjer, Arturo Vieiro. Dynamics of the QR-flow for upper Hessenberg real matrices. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1359-1403. doi: 10.3934/dcdsb.2020166
[10]

Michiel Bertsch, Flavia Smarrazzo, Andrea Terracina, Alberto Tesei. Signed Radon measure-valued solutions of flux saturated scalar conservation laws. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3143-3169. doi: 10.3934/dcds.2020041
[11]

Huanhuan Tian, Maoan Han. Limit cycle bifurcations of piecewise smooth near-Hamiltonian systems with a switching curve. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020368
[12]

Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352
[13]

Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164
[14]

Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350
[15]

Guoliang Zhang, Shaoqin Zheng, Tao Xiong. A conservative semi-Lagrangian finite difference WENO scheme based on exponential integrator for one-dimensional scalar nonlinear hyperbolic equations. Electronic Research Archive, 2021, 29 (1) : 1819-1839. doi: 10.3934/era.2020093

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (36)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences