Abstract
We present normal forms for elliptic curves over a field of characteristic 2 analogous to Edwards normal form, and determine bases of addition laws, which provide strikingly simple expressions for the group law. We deduce efficient algorithms for point addition and scalar multiplication on these forms. The resulting algorithms apply to any elliptic curve over a field of characteristic 2 with a 4-torsion point, via an isomorphism with one of the normal forms. We deduce algorithms for duplication in time 2M + 5S + 2m c and for addition of points in time 7M + 2S, where M is the cost of multiplication, S the cost of squaring, and m c the cost of multiplication by a constant. By a study of the Kummer curves \(\mathcal{K}\) = E/{[±1]}, we develop an algorithm for scalar multiplication with point recovery which computes the multiple of a point P with 4M + 4S + 2m c + m t per bit where m t is multiplication by a constant that depends on P.
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
Bernstein, D.J., Lange, T.: Faster Addition and Doubling on Elliptic Curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards Curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)
Bernstein, D.J., Lange, T.: A complete set of addition laws for incomplete Edwards curves. J. Number Theory 131, 858–872 (2011)
Bernstein, D.J., Lange, T., Rezaeian Farashahi, R.: Binary Edwards Curves. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 244–265. Springer, Heidelberg (2008)
Bernstein, D.J., Kohel, D., Lange, T.: Twisted Hessian curves (unpublished 2009)
Bernstein, D.J., Lange, T.: Explicit-formulas database (2012), http://www.hyperelliptic.org/EFD/
Bosma, W., Lenstra Jr., H.W.: Complete systems of two addition laws for elliptic curves. J. Number Theory 53(2), 229–240 (1995)
Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. in Appl. Math. 7(4), 385–434 (1986)
Coron, J.-S.: Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
Diao, O.: Quelques aspects de l’arithmtique des courbes hyperelliptiques de genre 2, Ph.D. thesis, Université de Rennes (2011)
Edwards, H.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393–422 (2007)
Gaudry, P., Lubicz, D.: The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines. Finite Fields and Their Applications 15(2), 246–260 (2009)
Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards Curves Revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008)
Farashahi, R.R., Joye, M.: Efficient Arithmetic on Hessian Curves. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 243–260. Springer, Heidelberg (2010)
Joye, M., Yen, S.-M.: The Montgomery Powering Ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
Kim, K.H., Kim, S.I.: A new method for speeding up arithmetic on elliptic curves over binary fields (2007), http://eprint.iacr.org/2007/181
Kohel, D.: Addition law structure of elliptic curves. Journal of Number Theory 131(5), 894–919 (2011)
Kohel, D.: A normal form for elliptic curves in characteristic 2. In: Arithmetic, Geometry, Cryptography and Coding Theory (AGCT 2011), Luminy, talk notes (March 15, 2011)
Kohel, D., et al.: Echidna algorithms, v.3.0 (2012), http://echidna.maths.usyd.edu.au/echidna/index.html
Lange, H., Ruppert, W.: Complete systems of addition laws on abelian varieties. Invent. Math. 79(3), 603–610 (1985)
Magma Computational Algebra System, Computational Algebra Group, University of Sydney (2012), http://magma.maths.usyd.edu.au/
Milne, J.S.: Abelian Varieties, version 2.00 (2012), http://www.jmilne.org/math/CourseNotes/av.html
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48, 243–264 (1987)
Stam, M.: On Montgomery-Like Representationsfor Elliptic Curves over GF(2k). In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 240–253. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kohel, D. (2012). Efficient Arithmetic on Elliptic Curves in Characteristic 2. In: Galbraith, S., Nandi, M. (eds) Progress in Cryptology - INDOCRYPT 2012. INDOCRYPT 2012. Lecture Notes in Computer Science, vol 7668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34931-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-34931-7_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34930-0
Online ISBN: 978-3-642-34931-7
eBook Packages: Computer ScienceComputer Science (R0)