Muhammad Ashraf1and Barıs¸ B ¨ulent Kırlar1,2

Abstract

On the Alternate Models of Elliptic Curves

Abstract

In the recent years, alternate models of elliptic curves have been studied. Such well-known models are Edwards curves, Jacobi intersections and Jacobi quartics, Hessian curves, Huff curves, and their variants to the more common Weierstrass curve. These models sometimes allow for more efficient computation on elliptic curves or provide other features of interest to cryptographers, such as resistance to side-channel attacks. In this paper, we first give the alternate models of elliptic curves emphasizing point addition and point doubling formulae with computational costs, the suggested improvements in each model and then countermeasures to side channel attacks if any. We also describe the geometric interpretation of the addition law in each model.

Keywords

• —alternate models of elliptic curves
• side channel attack
• unified addition formulae
• computational cost

References

1. D. Agrawal, B. Archambeault, J.R. Rao, P. Rohatgi, The EM Side-Channel(s). Cryptographic Hardware and Embedded Sys- tems - CHES 2002, Lecture Notes in Computer Science Vol. 2523. Springer-Verlag, pp. 29-45, 2003.
2. C. Arenea, T. Lange, M. Naehrig, C. Ritzenthaler, Faster Computation of the Tate Pairing, Journal of Number Theory 131(5), pp. 842857, 2011.
3. D. Bernstein and T. Lange, Faster addition and doubling on elliptic curves. Progress in Cryptology - Africacrypt 2007, Lecture Notes in Computer Science Vol. 4833, Springer, pp. 29-50, 2007.
4. D. Bernstein and T. Lange, Explicit Formulas Database, Avail- able at http://www.hyperelliptic.org/EFD
5. D. Bernstein and T. Lange, Inverted Edwards coordinates. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 17th International Symposium - AAECC-17, Lecture Notes in Computer Science Vol. 4851, Springer, pp. 20-27, 2007.
6. D. Bernstein, D. Kohel and T. Lange, Twisted Hessian curves. Available at http://www.hyperelliptic.org/EFD/g1p/auto- twistedhessian.html.
7. D. Bernstein, T. Lange and R. R. Farashahi, Binary Edwards Curves. Cryptographic Hardware and Embedded Systems - CHES 2008, Lecture Notes in Computer Science Vol. 5154, Springer, pp. 244-265, 2008.
8. D. Bernstein, P. Birkner, M. Joye, T. Lange and C. Peters, Twisted Edwards curves, Progress in Cryptology - Africacrypt 2008, Lecture Notes in Computer Science Vol. 5023, Springer, pp. 389-405, 2008.

9. O. Billet and M. Joye, The Jacobi model of an elliptic curve and side-channel analysis, AAECC 2003, Lecture Notes in Computer Science Vol. 2643, Springer-Verlag, pp. 34-42, 2003.
10. E. Biham and A. Shamir, Differential fault analysis of secret key cryptosystems. Advances in Cryptology - Crypto ’97, Lecture Notes in Computer Science Vol. 1294, Springer-Verlag, pp. 513- 525, 1997.
11. E. Brier and M. Joye, Weierstrass elliptic curves and side- channel attacks. Public Key Cryptography - PKC 2002, Lecture Notes in Computer Science Vol. 2274, Springer, pp. 335-345, 2002.
12. I. F. Blake, G. Seroussi and N. P. Smart, Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series 317, Cambridge University, 2005.
13. A. A. Ciss and D. Sow, On a New Generalization of Huff Curves. Available at http://eprint.iacr.org/2011/580.pdf.
14. J. Devigne and M. Joye, Binary Huff Curves. Topics in Cryptol- ogy - CT-RSA 2011, Lecture Notes in Computer Science Vol. 6558, Springer, pp. 340-355, 2011.
15. H. Edwards, A normal form for elliptic curves. Bulletin of the American Mathematical Society 44(3) , pp. 393-422, 2007.
16. R. R. Farashahi and M. Joye, Efficient Arithmetic on Hessian Curves. Public Key Cryptography - PKC 2010, Lecture Notes in Computer Science Vol. 6056, Springer, pp. 243-260, 2010.
17. H. Gu, D. Gu and W. Xie, Efficient Pairing Computation on Elliptic Curves in Hessian form. Information Security and Cryptology - ICISC 2010, Lecture Notes in Computer Science Vol. 6829, Springer, pp. 169-176, 2011.
18. H. Wu and R. Feng, Elliptic curves in Huff ’s model. Available at http://eprint.iacr.org/2010/390.pdf, 2010.
19. R. Feng, M. Nie and H. Wu, Twisted Jacobi Intersections Curves. Available at http://eprint.iacr.org/2009/597.pdf
20. T. S. Gustavsen and K. Ranestad, A Simple Point Counting Algorithm for Hessian Elliptic Curves in Characteristic Three. Appl. Algebra Eng. Commun. Comput. 17(2), pp. 141150, 2006.
21. G. Huff, Diophantine problems in geometry and elliptic ternary forms. Duke Math. J., 15, pp. 443-453, 1948.
22. H. Hisil, K. Koon-Ho Wong, G. Carter and E. Dawson, Twisted Edwards Curves Revisited. Advances in Cryptology - Asiacrypt 2008, Lecture Notes in Computer Science Vol. 5350, Springer- Verlag, pp. 326-343, 2008.
23. H. Hisil, K. Koon-Ho Wong, G. Carter and E. Dawson, Jacobi Quartic Curves Revisited. ACISP 2009, pp. 452-468, 2009.
24. M. Joye and J. Quisquater, Hessian elliptic curves and side- channel attacks. Cryptographic Hardware and Embedded Sys- tems - CHES 2001, Lecture Notes in Computer Science Vol. 2162, Springer, pp. 402-410, 2001.
25. M.Joye, M. Tibbouchi and D. Vergnaud, Huff ’s Model for El- liptic Curves. Algorithmic Number Theory - ANTS-IX, Lecture Notes in Computer Science Vol. 6197, Springer, pp. 234-250, 2010.
26. P. C. Kocher, Timing Attacks on Implementations of Diffie- Hellman, RSA, DSS, and Other Systems. Advances in Cryp- tology - Crypto ’96, Lecture Notes in Computer Science Vol. 1109, Springer, pp. 104-113, 1996.
27. P. Kocher, J. Jaffe and B. Jun, Differential Power Analysis. Ad- vances in Cryptology - Crypto’99, Lecture Notes in Computer Science Vol. 1666, Springer-Verlag, pp. 388-397, 1999.
28. P. Liardet and N. Smart, Preventing SPA/DPA in ECC systems using the Jacobi form. Cryptographic Hardware and Embedded Systems - CHES 2001, Lecture Notes in Computer Science Vol. 2162, Springer-Verlag, pp. 391-401, 2001.
29. N. Smart and E. J. Westwood, Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three. Appl. Algebra Eng. Commun. Comput. 13(6), pp. 485-497, 2003.
30. H. Wang, K. Wang, L. Zhang and B. Li, Pairing Computation on Elliptic Curves of Jacobi Quartic Form, Chinese Journal of Electronics 20(4), pp. 655-661, 2011.