Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves

  • Published:
Journal of Cryptology Aims and scope Submit manuscript

Abstract

Efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the Gallant–Lambert–Vanstone (GLV) method. Iijima, Matsuo, Chao and Tsujii gave such homomorphisms for a large class of elliptic curves by working over\({\mathbb{F}}_{p^{2}}\). We extend their results and demonstrate that they can be applied to the GLV method.

In general we expect our method to require about 0.75 the time of previous best methods (except for subfield curves, for which Frobenius expansions can be used). We give detailed implementation results which show that the method runs in between 0.70 and 0.83 the time of the previous best methods for elliptic curve point multiplication on general curves.

Article PDF

Similar content being viewed by others

Chapter© 2020
Use our pre-submission checklist

Avoid common mistakes on your manuscript.

References

  1. A. Antipa, D.R.L. Brown, R.P. Gallant, R.J. Lambert, R. Struik, S.A. Vanstone, Accelerated verification of ecdsa signatures, inSAC 2005, ed. by B. Preneel, S.E. Tavares. LNCS, vol. 3879 (Springer, Berlin, 2006), pp. 307–318

    Google Scholar 

  2. R. Avanzi, Aspects of hyperelliptic curves over large prime fields in software implementations, inCHES 2004, ed. by M. Joye, J.-J. Quisquater. LNCS, vol. 3156 (Springer, Berlin, 2004), pp. 148–162

    Google Scholar 

  3. R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, F. Vercauteren,Handbook of Elliptic and Hyperelliptic Curve Cryptography (Chapman and Hall/CRC, London, Boca Raton, 2006)

    MATH  Google Scholar 

  4. D.J. Bernstein, Curve25519: new Diffie–Hellman speed records, inPKC 2006, ed. by M. Yung et al. LNCS, vol. 3958 (Springer, Berlin, 2006), pp. 207–228

    Google Scholar 

  5. D.J. Bernstein, Differential addition chains, preprint (2006).http://cr.yp.to/papers.html#diffchain

  6. D.J. Bernstein, Elliptic vs. hyperelliptic, part 1 ECC 2006, Toronto, Canada.http://www.cacr.math.uwaterloo.ca/conferences/2006/ecc2006/slides.html

  7. D.J. Bernstein, T. Lange, Faster addition and doubling on elliptic curves, inAsiacrypt 2007, ed. by K. Kurosawa. LNCS, vol. 4833 (Springer, Berlin, 2007), pp. 29–50

    Chapter  Google Scholar 

  8. D.J. Bernstein, T. Lange, Inverted Edwards coordinates, inAAECC 2007, ed. by S. Boztas, H.-F. Lu. LNCS, vol. 4851 (Springer, Berlin, 2007), pp. 20–27

    Google Scholar 

  9. D.J. Bernstein, T. Lange, Analysis and optimization of elliptic-curve single-scalar multiplication, inFinite Fields and Applications: Proceedings of Fq8. Contemporary Mathematics, vol. 461 (Am. Math. Soc., Providence, 2008), pp. 1–18

    Google Scholar 

  10. D.J. Bernstein, P. Birkner, M. Joye, T. Lange, C. Peters, Twisted Edwards curves, inAfricacrypt 2008, ed. by S. Vaudenay. LNCS, vol. 5023 (Springer, Berlin, 2008), pp. 389–405

    Chapter  Google Scholar 

  11. I. Blake, G. Seroussi, N.P. Smart (eds.),Elliptic Curves in Cryptography (Cambridge University Press, Cambridge, 1999)

    MATH  Google Scholar 

  12. eBATS: ECRYPT benchmarking of asymmetric systems,http://www.ecrypt.eu.org/ebats/

  13. D.J. Bernstein, T. Lange (eds.), eBACS: ECRYPT benchmarking of cryptographic systems,http://bench.cr.yp.to/, accessed 9 January 2009

  14. D.R.L. Brown, Multi-dimensional Montgomery ladders for elliptic curves, eprint 2006/220.http://www.eprint.iacr.org/2006/220

  15. E. Dahmen, K. Okeya, D. Schepers, Affine precomputation with sole inversion in elliptic curve cryptography, inACISP 2007, ed. by J. Pieprzyk, H. Ghodosi, E. Dawson. LNCS, vol. 4586 (Springer, Berlin, 2007), pp. 245–258

    Google Scholar 

  16. I.M. Duursma, P. Gaudry, F. Morain, Speeding up the discrete log computation on curves with automorphisms, inASIACRYPT 1999, ed. by K.-Y. Lam, E. Okamoto, C. Xing. LNCS, vol. 1716 (Springer, Berlin, 1999), pp. 103–121

    Google Scholar 

  17. H.M. Edwards, A normal form for elliptic curves.Bull. Am. Math. Soc.44, 393–422 (2007)

    Article MATH  Google Scholar 

  18. S.D. Galbraith, M. Scott, Exponentiation in pairing-friendly groups using homomorphisms, inPairing 2008, ed. by S.D. Galbraith, K.G. Paterson. LNCS, vol. 5209 (Springer, Berlin, 2008), pp. 211–224

    Chapter  Google Scholar 

  19. S.D. Galbraith, X. Lin, M. Scott, Endomorphisms for faster elliptic curve cryptography on a large class of curves, inEUROCRYPT 2009, ed. by A. Joux. LNCS, vol. 5479 (Springer, Berlin, 2009), pp. 518–535

    Chapter  Google Scholar 

  20. R.P. Gallant, R.J. Lambert, S.A. Vanstone, Improving the parallelized Pollard lambda search on anomalous binary curves.Math. Comput.69, 1699–1705 (2000)

    MATH MathSciNet  Google Scholar 

  21. R.P. Gallant, R.J. Lambert, S.A. Vanstone, Faster point multiplication on elliptic curves with efficient endomorphisms, inCRYPTO 2001, ed. by J. Kilian. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 190–200

    Chapter  Google Scholar 

  22. P. Gaudry, Index calculus for Abelian varieties of small dimension and the elliptic curve discrete logarithm problem.J. Symb. Comput.44(12), 1690–1702 (2009)

    Article MATH MathSciNet  Google Scholar 

  23. P. Gaudry, E. Thomé, The mpFq library and implementing curve-based key exchanges, SPEED workshop presentation, Amsterdam, June 2007.www.hyperelliptic.org/SPEED/record.pdf

  24. P. Gaudry, E. Thomé, N. Thériault, C. Diem, A double large prime variation for small genus hyperelliptic index calculus.Math. Comput.76(257), 475–492 (2007)

    Article MATH  Google Scholar 

  25. P. Gaudry, E. Schost, Hyperelliptic curve point counting record: 254 bit Jacobian, post to NMBRTHRY list, 22 Jun 2008.http://www.loria.fr/gaudry/record127/

  26. R. Granger, On the static Diffie–Hellman problem on elliptic curves over extension fields, eprint 2010/177

  27. D. Hankerson, A.J. Menezes, S. Vanstone,Guide to Elliptic Curve Cryptography (Springer, Berlin, 2004)

    MATH  Google Scholar 

  28. D. Hankerson, K. Karabina, A.J. Menezes, Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields.IEEE Trans. Comput.58(10), 1411–1420 (2009)

    Article MathSciNet  Google Scholar 

  29. F. Hess, N. Smart, F. Vercauteren, The eta-pairing revisited.IEEE Trans. Inf. Theory52(10), 4595–4602 (2006)

    Article MATH MathSciNet  Google Scholar 

  30. T. Iijima, K. Matsuo, J. Chao, S. Tsujii, Construction of Frobenius maps of twist elliptic curves and its application to elliptic scalar multiplication, inSCIS 2002, IEICE Japan, January 2002, pp. 699–702

  31. D. Kim, S. Lim, Integer decomposition for fast scalar multiplication on elliptic curves, inSAC 2002, ed. by K. Nyberg, H. Heys. LNCS, vol. 2595 (Springer, Berlin, 2003), pp. 13–20

    Google Scholar 

  32. S. Kozaki, K. Matsuo, Y. Shimbara, Skew-Frobenius maps on hyperelliptic curves.IEICE Trans.E91-A(7), 1839–1843 (2008)

    Article  Google Scholar 

  33. P. Longa, A. Miri, New composite operations and precomputation scheme for elliptic curve cryptosystems over prime fields, inPKC 2008, ed. by R. Cramer. LNCS, vol. 4939 (Springer, Berlin, 2008), pp. 229–247

    Google Scholar 

  34. B. Möller, Algorithms for multi-exponentiation, inSAC 2001, ed. by S. Vaudenay, A.M. Youssef. LNCS, vol. 2259 (Springer, Berlin, 2001), pp. 165–180

    Google Scholar 

  35. B. Möller, Improved techniques for fast exponentiation, inICISC 2002, ed. by P. Lee, C. Lim. LNCS, vol. 2587 (Springer, Berlin, 2003), pp. 298–312

    Google Scholar 

  36. B. Möller, Fractional windows revisited: improved signed-digit representations for efficient exponentiation, inICISC 2004, ed. by C. Park, S. Chee. LNCS, vol. 3506 (Springer, Berlin, 2005), pp. 137–153

    Google Scholar 

  37. B. Möller, A. Rupp, Faster multi-exponentiation through caching: accelerating (EC)DSA signature verification, inSCN 2008, ed. by R. Ostrovsky, R. De Prisco, I. Visconti. LNCS, vol. 5229 (Springer, Berlin, 2008), pp. 39–56

    Google Scholar 

  38. P.L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization.Math. Comput.47, 243–264 (1987)

    Google Scholar 

  39. Y. Nogami, Y. Morikawa, Fast generation of elliptic curves with prime order over extension field of even extension degree, inProceedings 2003 IEEE International Symposium on Information Theory (2003), p. 18

  40. Y. Nogami, Y. Morikawa, Fast generation of elliptic curves with prime order over\({\mathbb{F}}_{p^{2^{c}}}\). Workshop on Coding and Cryptography (WCC2003) (2003), pp. 347–356

  41. Y.-H. Park, S. Jeong, C.H. Kim, J. Lim, An alternate decomposition of an integer for faster point multiplication on certain elliptic curves, inPKC 2002, ed. by D. Naccache, P. Paillier. LNCS, vol. 2274 (Springer, Berlin, 2002), pp. 323–334

    Google Scholar 

  42. A.G. Rostovtsev, E.B. Markovenko, Elliptic curve point multiplication, inMMM-ACNS 2003, ed. by V. Gorodetsky. LNCS, vol. 2776 (Springer, Berlin, 2003), pp. 328–336

    Google Scholar 

  43. K. Schmidt-Samoa, O. Semay, T. Takagi, analysis of fractional window recoding methods and their application to elliptic curve cryptosystems.IEEE Trans. Comput.55(1), 48–57 (2006)

    Article  Google Scholar 

  44. M. Scott, MIRACL—multiprecision integer and rational arithmetic C/C++ library,http://ftp.computing.dcu.ie/pub/crypto/miracl.zip (2008)

  45. M. Scott, P. Szczechowiak, Optimizing multiprecision multiplication for public key cryptography, eprint 2007/299.http://eprint.iacr.org/2007/299

  46. F. Sica, M. Ciet, J.-J. Quisquater, Analysis of the Gallant–Lambert–Vanstone method based on efficient endomorphisms: elliptic and hyperelliptic curves, inSAC 2002, ed. by K. Nyberg, H.M. Heys. LNCS, vol. 2595 (Springer, Berlin, 2003), pp. 21–36

    Google Scholar 

  47. J.H. Silverman,The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106 (Springer, Berlin, 1986)

    MATH  Google Scholar 

  48. J.A. Solinas, Efficient arithmetic on Koblitz curves.Designs Codes and Cryptogr.19(2–3), 195–249 (2000)

    Article MATH MathSciNet  Google Scholar 

  49. J.A. Solinas, Low-weight binary representations for pairs of integers. Technical Report CORR 2001–41, CACR (2001)

  50. M.J. Wiener, R.J. Zuccherato, Faster attacks on elliptic curve cryptosystems, inSAC 1998, ed. by S. Tavares, H. Meijer. LNCS, vol. 1556 (Springer, Berlin, 1999), pp. 190–200

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics Department, Auckland University, Private Bag 92019, Auckland, 1142, New Zealand

    Steven D. Galbraith

  2. School of Mathematics and Computational Science, Sun Yat-Sen University, Guangzhou, 510275, P.R. China

    Xibin Lin

  3. School of Computing, Dublin City University, Ballymun, Dublin 9, Ireland

    Michael Scott

Authors
  1. Steven D. Galbraith

    You can also search for this author inPubMed Google Scholar

  2. Xibin Lin

    You can also search for this author inPubMed Google Scholar

  3. Michael Scott

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toSteven D. Galbraith.

Additional information

Communicated by Nigel Smart

This is the full version of a paper published at Eurocrypt 2009.

The work of S.D. Galbraith supported by EPSRC grant EP/D069904/1.

The work of S.D. Galbraith described in this report has in part been supported by the Commission of the European Communities through the ICT program under contract ICT-2007-216676. The information in this document is provided as is, and no warranty is given or implied that the information is fit for any particular purpose. The user thereof uses the information at its sole risk and liability.

X. Lin thanks the Chinese Scholarship Council.

M. Scott acknowledges support from the Science Foundation Ireland under Grant No. 06/MI/006.

Rights and permissions

About this article

Use our pre-submission checklist

Avoid common mistakes on your manuscript.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp