Abstract
Koblitz, Solinas, and others investigated a family of elliptic curves which admit faster cryptosystem computations.In this paper, we generalize their ideas to hyperelliptic curves of genus 2.We consider the following two hyperelliptic curves C α : v 2 + uv = u 5 + αu 2 + 1 defined over F2 with α = 0, 1, and show how to speed up the arithmetic in the Jacobian JCα(F2n) by making use of the Frobenius automorphism.With two precomputations, we are able to obtain a speed-up by a factor of 5.5 compared to the generic double-and-add-method in the Jacobian.If we allow 6 precomputations, we are even able to speed up by a factor of 7.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Cantor, D.G.: Computing in the Jacobian of a Hyperelliptic Curve.Math.Comp. 48 (1987) 95–101
Diffie, W., Hellman, M.E.: New Directions in Cryptography.IEEE Trans.Inform. Theory 22(1976) 644–654
ElGamal, T.: A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.IEEE Trans.Inform.Theory 31 (1985) 469–472
Frey, G., Rück, H.-G.: A Remark Concerning m-Divisibility and the Discrete Logarithm Problem in the Divisor Class Group of Curves.Math.Comp. 62(1994) 865–874
Gallant, R., Lambert, R., Vanstone, S.: Improving the Parallelized Pollard Lambda Search on Binary Anomalous Curves.To Appear in Math.Comp. http://www.certicom.com/chal/download/paper.ps
Gaudry, P., Hess, F., Smart, N.: Constructive and Destructive Facets of Weil Descent on Elliptic Curves, preprint, 1999.
Gaudry, P., Morain, F., Duursma, I.: Speeding Up the Discrete Log Computation on Curves with Automorphisms In: Proc.of The Mathematics of Public Key Cryptography.Fields-Institute Toronto (1999)
Gordon, D.: A Survey of Fast Exponentiation Methods.J.Algorithms 27 (1998) 129–146
Koblitz, N.: Elliptic Curve Cryptosystems.Math.Comp. 48 (1987) 203–209
Koblitz, N.: Hyperelliptic Cryptosystems.J.Cryptology 1 (1989) 139–150
Koblitz, N.: CM Curves with Good Cryptographic Properties. In: Advances in Cryptology-Crypto ’91.LNCS, Vol.576.Springer-Verlag, Berlin Heidelberg New York (1992) 279–287
Koblitz, N.: An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm.In: Advances in Cryptology-Crypto ’98.Lecture Notes in Computer Science, Vol.1462.Springer-Verlag, Berlin Heidelberg New York (1998) 327–337
Lange, T.: Efficient Arithmetic on Hyperelliptic Koblitz Curves. preprint, 2000.
Lehmer, D.H.: Factorization of Certain Cyclotomic Functions. Ann. Math. 34(1933) 461–479
Meier, W., Staffelbach, O.: Efficient Multiplication on Certain Nonsupersingular Elliptic Curves.In: Advances in Cryptology-Crypto ’92.LNCS, Vol.740. Springer-Verlag, Berlin Heidelberg New York (1993) 333–344
Menezes, A., Wu, Y., Zuccherato, R.: An Elementary Introduction to Hyperelliptic Curves.In: Koblitz, N.: Algebraic Aspects of Cryptography.Springer-Verlag, Berlin Heidelberg New York (1998)
Miller, V.: Use of Elliptic Curves in Cryptography. In: Advances in Cryptology — Crypto ’85.LNCS, Vol.218.Springer-Verlag, Berlin Heidelberg New York (1986) 417–426
Müller, V., Stein, A., Thiel, C.: Computing Discrete Logarithms in Real Quadratic Congruence Function Fields of Large Genus.Math.Comp. 68 (1999) 807–822
Mumford, D.: Tata Lectures on Theta I, II. Birkhäuser-Verlag, Boston (1983/84)
van Oorschot, P., Wiener, M. J.: Parallel Collision Search with Cryptanalytic Applications. J.Cryptology 12 (1999) 1–28
Pierce, T.A.: The Numerical Factors of the Arithmetic Forms Πn i=1(1±αm i.Ann. Math. 18(1916), 53–64.
Pollard, J.M.: Kangaroos, Monopoly and Discrete Logarithms.To appear in J. Cryptology.
Solinas, J.: An Improved Algorithm for Arithmetic on a Family of Elliptic Curves. In: Advances in Cryptology-Crypto ’97.LNCS, Vol.1294.Springer-Verlag, Berlin Heidelberg New York (1997) 357–371
Solinas, J.: Efficient Arithmetic on Koblitz Curves.Techn.Report CORR 99-09, University of Waterloo (1999), 61 pages. http://www.cacr.math.uwaterloo.ca
Stein, A.: Sharp Upper Bounds for Arithmetics in Hyperelliptic Function Fields. Techn.Report CORR 99-23, University of Waterloo (1999), 68 pages.Available at http://www.cacr.math.uwaterloo.ca
Stichtenoth, H.: Algebraic Function Fields and Codes. Springer-Verlag, Berlin Heidelberg New York (1993)
Teske, E.: Speeding up Pollard’s rho method for computing discrete logarithms. In: Algorithmic Number Theory Seminar ANTS-III.LNCS, Vol.1423.Springer-Verlag, Berlin Heidelberg New York (1998) 541–554
Wiener, M., Zuccerato, R.: Faster Attacks on Elliptic Curve Cryptosystems. In: Proceedings of SAC, Workshop on Selected Areas in Cryptography.LNCS, Springer-Verlag, Berlin Heidelberg New York (1998).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Günther, C., Lange, T., Stein, A. (2001). Speeding up the Arithmetic on Koblitz Curves of Genus Two. In: Stinson, D.R., Tavares, S. (eds) Selected Areas in Cryptography. SAC 2000. Lecture Notes in Computer Science, vol 2012. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44983-3_8
Download citation
DOI: https://doi.org/10.1007/3-540-44983-3_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42069-9
Online ISBN: 978-3-540-44983-6
eBook Packages: Springer Book Archive