Scalar multiplication is the most important and expensive operation in elliptic curve cryptosystems. In this study, the authors improve the efficiency of the elliptic net algorithm to compute scalar multiplication by using the equivalence of elliptic nets. The proposed method saves four multiplications by a constant in each iteration loop. Experimental results also indicate that the proposed algorithm will be more efficient than the previously known results on this line while it is still slower than the state-of-the-art algorithm to compute scalar multiplication.

References

1. 1)
  - 2. Miller, V.: ‘Use of elliptic curves in cryptography’. Advances in Cryptology – CRYPTO'85 Proc., ser., 1986 (LNCS, 218), pp. 417–426.
2. 2)
  - 19. Cohen, H., Miyaji, A., Ono, T.: ‘Efficient elliptic curve exponentiation using mixed coordinates’. Advances in Cryptology – ASIACRYPT'98 Proc., ser., 1998 (LNCS, 1514), pp. 51–65.
3. 3)
  - 9. Stange, K.E.: ‘The Tate pairing via elliptic nets’. Pairing-Based Cryptography – Pairing 2007, ser. Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2007, 4575, pp. 329–348.
4. 4)
  - 18. Chen, B.L., Zhao, C.A.: ‘An improvement of the elliptic net algorithm’, IEEE Trans. Comput., 2016, 65, 9, 2903–2909. to appear.
5. 5)
  - 13. Silverman, J.: ‘The arithmetic of elliptic curves’ (Springer-Verlag, New York, 1986).
6. 6)
  - 4. Hankerson, D., Vanstone, S., Menezes, A.J.: ‘Guide to elliptic curve cryptography’ (Springer Science & Business Media, 2004).
7. 7)
  - 15. Certicom Research: ‘Standards for efficient cryptography – sec 2: Recommended elliptic curve cryptography domain parameters. version 1.0, 2000’, 2000.
8. 8)
  - 11. Bernstein, D.J.: ‘Differential addition chains’, Technical Report, 2006. Available at https://cr.yp.to/ecdh/diffchain-20060219.pdf, accessed 5 July 2016.
9. 9)
  - 10. Brier, E., Joye, M.: ‘Weierstraß elliptic curves and side-channel attacks’. Public Key Cryptography – PKC 2002 Proc., ser., 2002 (LNCS), 2274, pp. 335–345.
10. 10)
  - 3. Blake, I.F., Seroussi, G., Smart, N.: ‘Elliptic curves in cryptography’ (Cambridge University Press, 1999).
11. 11)
  - 5. Cohen, H., Frey, G.: ‘Handbook of elliptic and hyperelliptic curve cryptography’ (CRC Press, 2005).
12. 12)
  - 20. Shoup, V.: ‘NTL: a library for doing number theory’. Available at http://shoup.net/ntl/index.html, accessed 1 December 2015.
13. 13)
  - 7. Ward, M.: ‘Memoir on elliptic divisibility sequences’, Am. J. Math., 1948, 70, pp. 31–74.
14. 14)
  - 16. Hamburg, M.: ‘Ed448-goldilocks, a new elliptic curve’, Cryptology ePrint Archive, Report 2015/625, 2015. Available at http://eprint.iacr.org/, accessed 15 June 2016.
15. 15)
  - 1. Koblitz, N.: ‘Constructing elliptic curve cryptosystems in characteristic 2’. Advances in Cryptology – CRYPTO'90 Proc., ser., 1991(LNCS, 537), pp. 156–167.
16. 16)
  - 14. IEEE P1363 Working Group and others: ‘IEEE P1363: Standard specifications for public key cryptography’, 1999.
17. 17)
  - 6. Galbraith, S.D.: ‘Mathematics of public key cryptography’ (Cambridge University Press, 2012).
18. 18)
  - 17. Bernstein, D.J..: ‘Curve25519: new Diffie-Hellman speed records’. Public Key Cryptography – PKC 2006 Proc., ser., 2006 (LNCS), 3958, pp. 207–228.
19. 19)
  - 8. Shipsey, R.: ‘Elliptic divisibility sequences’, PhD thesis, Goldsmiths, University of London, 2001.
20. 20)
  - 12. Kanayama, N., Liu, Y., OKamoto, E., et al: ‘Implementation of an elliptic curve scalar multiplication method using division polynomials’, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2014, E97.A, (1), pp. 300–302.

Note on scalar multiplication using division polynomials

References

Related content