Abstract
Elliptic curves have a well-known and explicit theory for the construction and application of endomorphisms, which can be applied to improve performance in scalar multiplication. Recent work has extended these techniques to hyperelliptic Jacobians, but one obstruction is the lack of explicit models of curves together with an efficiently computable endomorphism. In the case of hyperelliptic curves there are limited examples, most methods focusing on special CM curves or curves defined over a small field. In this article we describe three infinite families of curves which admit an efficiently computable endomorphism, and give algorithms for their efficient application.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cantor, D.: Computing in the Jacobian of a hyperelliptic curve. Math. Comp. 48, 95–101 (1987)
Ciet, M., Lange, T., Sica, F., Quisquater, J.-J.: Improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 387–400. Springer, Heidelberg (2003)
Duursma, I., Sakurai, K.: Efficient algorithms for the Jacobian variety of hyperelliptic curves y 2 = x p − x + 1 over a finite field of odd characteristic p. In: Coding theory, cryptography and related areas (Guanajuato, 1998), pp. 73–89. Springer, Berlin (2000)
Ellenberg, J.: Endomorphism algebras of Jacobians. Advances in Mathematics 162, 243–271 (2001)
Cassels, J.W.S., Flynn, E.V.: Prolegomena to a middlebrow arithmetic of curves of genus 2. London Mathematical Society Lecture Note Series, vol. 230. Cambridge University Press, Cambridge (1996)
Gallant, R., Lambert, R., Vanstone, S.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001)
Gaudry, P., Gürel, N.: Counting points in medium characteristic using Kedlaya’s algorithm. Experiment. Math. 12(4), 395–402 (2003)
Hashimoto, K.-I.: On Brumer’s family of RM-curves of genus two. Tohoku Math. J. (2) 52(4), 475–488 (2000)
Kedlaya, K.: Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. J. Ramanujan Math. Soc. 16(4), 323–338 (2001)
Koblitz, N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992)
Lange, T.: Efficient arithmetic on hyperelliptic Koblitz curves, Ph.D. Thesis (2001)
Lidl, R., Mullen, G.L., Turnwald, G.: Dickson polynomials, Pitman monographs and surveys in pure and applied mathematics 65, Longman Scientific & Technical (1993)
Menezes, A.J., Vanstone, S.A.: The implementation of elliptic curve cryptosystems. In: Seberry, J., Pieprzyk, J.P. (eds.) AUSCRYPT 1990. LNCS, vol. 453, pp. 2–13. Springer, Heidelberg (1990)
Mestre, J.-F.: Familles de courbes hyperelliptiques à multiplications réelles. In: Arithmetic algebraic geometry (Texel, 1989). Progress in Math., vol. 89, pp. 193–208. Birkhäuser, Boston (1991)
Park, Y.-H., Jeong, S., Lim, J.: Speeding up point multiplication on hyperelliptic curves with efficiently-computable endomorphisms. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 197–208. Springer, Heidelberg (2002)
Smith, B.A.: Explicit endomorphisms and correspondences, Ph.D. Thesis, The University of Sydney (2005)
Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19(2-3), 195–249 (2000)
Stoll, M.: Two simple 2-dimensional abelian varieties defined over Q with Mordell-Weil group of rank at least 19. C. R. Acad. Sci. Paris Sér. I Math. 321(10), 1341–1345 (1995)
Takashima, K.: A new type of fast endomorphisms on Jacobians of hyperelliptic curves and their cryptographic application. IEICE Trans. Fundamentals E89-A(1), 124–133 (2006)
Tautz, W., Top, J., Verberkmoes, A.: Explicit hyperelliptic curves with real multiplication and permutation polynomials. Canad. J. Math. 43(5), 1055–1064 (1991)
Weil, A.: On some exponential sums. Proc. Nat. Acad. Sci. 34, 204–207 (1948)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kohel, D.R., Smith, B.A. (2006). Efficiently Computable Endomorphisms for Hyperelliptic Curves. In: Hess, F., Pauli, S., Pohst, M. (eds) Algorithmic Number Theory. ANTS 2006. Lecture Notes in Computer Science, vol 4076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11792086_35
Download citation
DOI: https://doi.org/10.1007/11792086_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36075-9
Online ISBN: 978-3-540-36076-6
eBook Packages: Computer ScienceComputer Science (R0)