High-Performance Scalar Multiplication Using 8-Dimensional GLV/GLS Decomposition

1. Acar, T., Shumow, D.: Modular reduction without pre-computation for special moduli. Technical report, Microsoft Research (2010)

   Google Scholar 

2. Adleman, L., DeMarrais, J., Huang, M.: A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over GF(q). Theoretical Computer Science 226(1-2), 7–18 (1999)

   Article  MathSciNet  Google Scholar 

3. Aranha, D.F., Karabina, K., Longa, P., Gebotys, C.H., López, J.: Faster explicit formulas for computing pairings over ordinary curves. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 48–68. Springer, Heidelberg (2011)

   Chapter  Google Scholar 

4. Beagle Board. BeagleBoard-xM System Reference Manual (2013), http://beagleboard.org/static/BBxMSRM_latest.pdf

5. Bernstein, D.J.: Curve25519: New Diffie-Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 207–228. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

6. Bernstein, D.J., Lange, T. (eds.): eBACS: ECRYPT Benchmarking of Cryptographic Systems, http://bench.cr.yp.to (accessed March 1, 2013)

7. Bernstein, D.J., Schwabe, P.: NEON crypto. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 320–339. Springer, Heidelberg (2012)

   Chapter  Google Scholar 

8. Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 194–210. Springer, Heidelberg (2013)

   Chapter  Google Scholar 

9. Bos, J.W., Costello, C., Hisil, H., Lauter, K.: High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition. Cryptology ePrint Archive, Report 2013/146 (2013), http://eprint.iacr.org/

10. Buhler, J., Koblitz, N.: Lattice basis reduction, Jacobi sums and hyperelliptic cryptosystems. Bul. of the Australian Mathematical Society 58(1), 147–154 (1998)

    Article  MathSciNet  Google Scholar 

11. Diem, C.: The GHS attack in odd characteristic. J. Ramanujan Math. Soc. 18(1), 1–32 (2003)

    MathSciNet  MATH  Google Scholar 

12. Diem, C.: On the discrete logarithm problem in elliptic curves. Compositio Mathematica 147(01), 75–104 (2011)

    Article  MathSciNet  Google Scholar 

13. Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976)

    Article  MathSciNet  Google Scholar 

14. Faz-Hernandez, A., Longa, P., Sanchez, A.H.: Keep calm and stay with one (and p > 3). Cryptology ePrint Archive, Report 2013/158 (2013)

    Google Scholar 

15. Frey, G.: How to disguise an elliptic curve (Weil descent). Talk at ECC: slides available at http://cacr.uwaterloo.ca/conferences/1998/ecc98/frey.ps (September 1998)

16. Galbraith, S.D.: Weil descent of Jacobians. Discrete Applied Mathematics 128(1), 165–180 (2003)

    Article  MathSciNet  Google Scholar 

17. Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Cryptology 24(3), 446–469 (2011)

    Article  MathSciNet  Google Scholar 

18. Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

19. Gaudry, P.: An algorithm for solving the discrete log problem on hyperelliptic curves. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 19–34. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

20. Gaudry, P.: Fast genus 2 arithmetic based on theta functions. Journal of Mathematical Cryptology JMC 1(3), 243–265 (2007)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

22. Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptology 15(1), 19–46 (2002)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

24. Goren, E.Z., Lauter, K.E.: Genus 2 curves with complex multiplication. International Mathematics Research Notices 2012(5), 1068–1142 (2012)

    Article  MathSciNet  Google Scholar 

25. Hamburg, M.: Fast and compact elliptic-curve cryptography. Cryptology ePrint Archive, Report 2012/309 (2012), http://eprint.iacr.org/

26. Iijima, T., Momose, F., Chao, J.: Classification of elliptic/hyperelliptic curves with weak coverings against GHS attack without isogeny condition. Cryptology ePrint Archive, Report 2009/613 (2009), http://eprint.iacr.org/

27. Käsper, E.: Fast elliptic curve cryptography in OpenSSL. In: Danezis, G., Dietrich, S., Sako, K. (eds.) FC 2011 Workshops. LNCS, vol. 7126, pp. 27–39. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

28. Knežević, M., Vercauteren, F., Verbauwhede, I.: Speeding up bipartite modular multiplication. In: Hasan, M.A., Helleseth, T. (eds.) WAIFI 2010. LNCS, vol. 6087, pp. 166–179. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

29. Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), 203–209 (1987)

    Article  MathSciNet  Google Scholar 

30. Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

31. Lenstra, A.K.: Generating RSA moduli with a predetermined portion. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 1–10. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

32. Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

33. Longa, P., Sica, F.: Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 718–739. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

34. Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)

    Google Scholar 

35. Momose, F., Chao, J.: Scholten forms and elliptic/hyperelliptic curves with weak Weil restrictions. Cryptology ePrint Archive, Report 2005/277 (2005)

    Google Scholar 

36. Montgomery, P.L.: Modular multiplication without trial division. Mathematics of Computation 44(170), 519–521 (1985)

    Article  MathSciNet  Google Scholar 

37. Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48(177), 243–264 (1987)

    Article  MathSciNet  Google Scholar 

38. Morozov, S., Tergino, C., Schaumont, P.: System integration of elliptic curve cryptography on an OMAP platform. In: IEEE 9th Symposium on Application Specific Processors – SASP, pp. 52–57. IEEE Computer Society (2011)

    Google Scholar 

39. Nagao, K.-I.: Decomposition attack for the Jacobian of a hyperelliptic curve over an extension field. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS-IX 2010. LNCS, vol. 6197, pp. 285–300. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

40. National Institute of Standards and Technology. Special publication 800-57: Recommendation for key management part 1: General (revised), http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf

41. National Security Agency. The case for elliptic curve cryptography (2009), http://www.nsa.gov/business/programs/elliptic_curve.shtml

42. 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)

    Chapter  Google Scholar 

43. Pollard, J.M.: Monte Carlo methods for index computation (mod p). Mathematics of Computation 32(143), 918–924 (1978)

    MathSciNet  MATH  Google Scholar 

44. Solinas, J.A.: Generalized Mersenne numbers. Technical Report CORR 99–39, Centre for Applied Cryptographic Research, University of Waterloo (1999)

    Google Scholar 

45. Thériault, N.: Weil descent attack for Kummer extensions. J. Ramanujan Math. Soc. 18(3), 218–312 (2003)

    MathSciNet  MATH  Google Scholar 

46. U.S. Department of Commerce/National Institute of Standards and Technology. Digital Signature Standard (DSS). FIPS-186-3 (2009), http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf

47. Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electronics Letters 35(21), 1831–1832 (1999)

    Article  Google Scholar 

Download references