Evaluation of Computational Approaches of Short Weierstrass Elliptic Curves for Cryptography

Abhishek, Kunal; Raj, E. George Dharma Prakash

doi:10.2478/cait-2021-0045

Abstract

The survey presents the evolution of Short Weierstrass elliptic curves after their introduction in cryptography. Subsequently, this evolution resulted in the establishment of present elliptic curve computational standards. We discuss the chronology of attacks on Elliptic Curve Discrete Logarithm Problem (ECDLP) and investigate their countermeasures to highlight the evolved selection criteria of cryptographically safe elliptic curves. Further, two popular deterministic and random approaches for selection of Short Weierstrass elliptic curve for cryptography are evaluated from computational, security and trust perspectives and a trend in existent computational standards is demonstrated. Finally, standard and non-standard elliptic curves are analysed to add a new insight into their usability. There is no such survey conducted in past to the best of our knowledge.

References

1. Koblitz, N. A Course in Number Theory and Cryptography. Springer Science & Business Media, 2 September 1994.10.1007/978-1-4419-8592-7
Search in Google Scholar Back to article
2. Caelli, W. J., E. P. Dawson, S. A. Rea. PKI, Elliptic Curve Cryptography, and Digital Signatures. – Computers & Security, Vol. 18, 1 January 1999, No 1, pp. 47-66.10.1016/S0167-4048(99)80008-X
Search in Google Scholar Back to article
3. Valenta, L., N. Sullivan, A. Sanso, N. Heninger. In Search of CurveSwap: Measuring Elliptic Curve Implementations in the Wild. – In: Proc. of 2018 IEEE European Symposium on Security and Privacy (EuroS&P’18), 24 April 2018, IEEE, pp. 384-398.10.1109/EuroSP.2018.00034
Search in Google Scholar Back to article
4. Koblitz, N., A. Menezes, S. Vanstone. The State of Elliptic Curve Cryptography. Designs, Codes and Cryptography. – Vol. 19, March 2000, No 2, pp. 173-193.10.1023/A:1008354106356
Search in Google Scholar Back to article
5. Hankerson, D., A. Menezes, S. Vanstone. Guide to Elliptic Curve Cryptography. Springer, 2003. ISBN: 0-387-95273-X.
Search in Google Scholar Back to article
6. Menezes, A. J., T. Okamoto, S. A. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. – IEEE Transactions on Information Theory, Vol. 39, September 1993, No 5, pp. 1639-1646.10.1109/18.259647
Search in Google Scholar Back to article
7. Koblitz, A. H., N. Koblitz, A. Menezes. Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift. – Journal of Number Theory, Vol. 131, 1 May 2011, No 5, pp. 781-814. DOI:10.1016/j.jnt.2009.01.006.10.1016/j.jnt.2009.01.006
Search in Google Scholar Back to article
8. Smart, N. P. The Discrete Logarithm Problem on Elliptic Curves of Trace One. – Journal of Cryptology, Vol. 12, 1 Jun 1999, No 3, pp. 193-196.10.1007/s001459900052
Search in Google Scholar Back to article
9. Flori, J. P., J. Plût, J. R. Reinhard, M. Ekerå. Diversity and Transparency for ECC. – IACR Cryptol. ePrint Arch., 11 Jun 2015, 2015/659.
Search in Google Scholar Back to article
10. Menezes, A. Evaluation of Security Level of Cryptography: The Elliptic Curve Discrete Logarithm Problem (ECDLP). University of Waterloo, 14 December 2001.
Search in Google Scholar Back to article
11. Baier, H., J. Buchmann. Generation Methods of Elliptic Curves. An Evaluation Report for the Information-Technology Promotion Agency, Japan, 27 August 2002.
Search in Google Scholar Back to article
12. Semaev, I. Evaluation of Discrete Logarithms in a Group of p-Torsion Points of an Elliptic Curve in Characteristic p. – Mathematics of Computation, Vol. 67, 1998, No 221, pp. 353-356.10.1090/S0025-5718-98-00887-4
Search in Google Scholar Back to article
13. Washington, L. C. Elliptic Curves: Number Theory and Cryptography. CRC Press, 3 April 2008.
Search in Google Scholar Back to article
14. Konstantinou, E., A. Kontogeorgis, Y. C. Stamatiou, et al. – J Cryptol., Vol. 23, 2010, 477. https://doi.org/10.1007/s00145-009-9037-210.1007/s00145-009-9037-2
Search in Google Scholar Back to article
15. Konstantinou, E., A. Kontogeorgis, Y. C. Stamatiou, C. Zaroliagis. On the Efficient Generation of Prime-Order Elliptic Curves. – Journal of Cryptology, Vol. 23, 1 July 2010, No 3, pp. 477-503.10.1007/s00145-009-9037-2
Search in Google Scholar Back to article
16. Savaş, E., T. A. Schmidt, C. K. Koç. Generating Elliptic Curves of Prime Order. – In: Proc. of International Workshop on Cryptographic Hardware and Embedded Systems, 14 May 2001. Berlin, Heidelberg, Springer, pp. 142-158.10.1007/3-540-44709-1_13
Search in Google Scholar Back to article
17. Schoof, R. Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. – Mathematics of Computation, Vol. 44, 1985, No 170, pp. 483-494.10.1090/S0025-5718-1985-0777280-6
Search in Google Scholar Back to article
18. I. F. Blake, G. Seroussi, N. P. Smart, Eds. Advances in Elliptic Curve Cryptography. – Cambridge University Press, Vol. 317, 25 April 2005.10.1017/CBO9780511546570
Search in Google Scholar Back to article
19. Menezes, A. J., T. Okamoto, S. A. Vanstone. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. – IEEE Transactions on Information Theory, Vol. 39, September 1993, No 5, pp. 1639-1646.10.1109/18.259647
Search in Google Scholar Back to article
20. Shor, P. W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. – In: Proc. of 35th Annual Symposium on Foundations of Computer Science, IEEE, 20 November 1994, pp. 124-134.
Search in Google Scholar Back to article
21. Balasubramanian, R., N. Koblitz. The Improbability that an Elliptic Curve has Subexponential Discrete Log Problem under the Menezes-Okamoto-Vanstone Algorithm. – Journal of Cryptology, Vol. 11, 1 March 1998, No 2, pp. 141-145.10.1007/s001459900040
Search in Google Scholar Back to article
22. Gaudry, P., F. Hess, N. P. Smart. Constructive and Destructive Facets of Weil Descent on Elliptic Curves. – Journal of Cryptology, Vol. 15, March 2002, No 1, pp. 19-46.10.1007/s00145-001-0011-x
Search in Google Scholar Back to article
23. PUB, F. Digital Signature Standard (DSS). – FIPS PUB. 27 January 2000, pp. 186-192.
Search in Google Scholar Back to article
24. SEC, S. 2: Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography Group, Certicom Corp., September 2000.
Search in Google Scholar Back to article
25. Brainpool, E. C. ECC Brainpool Standard Curves and Curve Generation. October, 2005. http://www.ecc-brainpool.org.
Search in Google Scholar Back to article
26. Lochter, M., J. Mekle. RFC 5639: ECC Brainpool Standard Curves & Curve Generation. Internet Engineering Task Force, March 2010.
Search in Google Scholar Back to article
27. Bernstein, D. J., Tanja Lange. SafeCurves: Choosing Safe Curves for Elliptic Curve Cryptography. 2015. Citations in this document. September 2014. https://safecurves.cr.yp.to10.1112/S1461157014000394
Search in Google Scholar Back to article
28. Liu, Z., H. Seo. IoT-NUMS: Evaluating NUMS Elliptic Curve Cryptography for IoT Platforms. – IEEE Transactions on Information Forensics and Security, Vol. 14, 13 July 2018, No 3, pp. 720-729.10.1109/TIFS.2018.2856123
Search in Google Scholar Back to article
29. Chen, L., et. al. Report on Post-Quantum Cryptography. US Department of Commerce, National Institute of Standards and Technology, 28 April 2016.
Search in Google Scholar Back to article
30. Roetteler, M., M. Naehrig, K. M. Svore, K. Lauter. Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. – In: Proc. of International Conference on the Theory and Application of Cryptology and Information Security, 3 December 2017, Cham, Springer, pp. 241-270.10.1007/978-3-319-70697-9_9
Search in Google Scholar Back to article
31. Pohlig, S., M. Hellman. An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance (Corresp.). – IEEE Transactions on Information Theory, Vol. 24, January 1978, No 1, pp. 106-110.10.1109/TIT.1978.1055817
Search in Google Scholar Back to article
32. Van Oorschot, P. C., M. J. Wiener. Parallel Collision Search with Cryptanalytic Applications. – Journal of Cryptology, Vol. 12, January 1999, No 1, pp. 1-28.10.1007/PL00003816
Search in Google Scholar Back to article
33. Bos, J. W., C. Costello, P. Longa, M. Naehrig. Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis. – Journal of Cryptographic Engineering, Vol. 6, November 2016, No 4, pp. 259-286.10.1007/s13389-015-0097-y
Search in Google Scholar Back to article
34. Hamburg, M. Ed448-Goldilocks, a New Elliptic Curve. IACR Cryptol. ePrint Arch. Jun 2015, 2015/625.
Search in Google Scholar Back to article
35. Crandall, R. E. Method and Apparatus for Public Key Exchange in a Cryptographic System. October 1992. US Patent. (5,159,632).
Search in Google Scholar Back to article
36. Dąbrowski, P., R. Gliwa, J. Szmidt, R. Wicik. Generation and Implementation of Cryptographically Strong Elliptic Curves. – In: Proc. of International Conference on Number-Theoretic Methods in Cryptology, 11 September 2017. Cham, Springer, pp. 25-36.10.1007/978-3-319-76620-1_2
Search in Google Scholar Back to article
37. Morain, F. Building Cyclic Elliptic Curves Modulo Large Primes. – In: Proc. of Workshop on the Theory and Application of of Cryptographic Techniques, 8 April 1991. Berlin, Heidelberg, Springer, pp. 328-336.10.1007/3-540-46416-6_28
Search in Google Scholar Back to article
38. Cohen, H. A Course in Computational Algebraic Number Theory. Berlin, Springer-Verlag, August 1993.10.1007/978-3-662-02945-9
Search in Google Scholar Back to article
39. Bernstein, D. J., et.al. How to Manipulate Curve Standards: A White Paper for the Black Hat. – In: Proc. of International Conference on Research in Security Standardisation, 15 December 2015, Cham, Springer, pp. 109-139. http://bada55.cr.yp.to10.1007/978-3-319-27152-1_6
Search in Google Scholar Back to article
40. San, C. V. A Survey of Elliptic Curve Cryptosystems. Part I. Introductory. Technical Report, NAS Technical Report-NAS-03-012, 2003.
Search in Google Scholar Back to article
41. https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html
Search in Google Scholar Back to article
42. Costello, C., P. Longa, M. Naehrig. A Brief Discussion on Selecting New Elliptic Curves. Microsoft Research. Microsoft, 8 June 2015.
Search in Google Scholar Back to article
43. https://www.nist.gov/system/files/documents/2017/05/09/2014-VCAT-Annual-Report_final.pdf
Search in Google Scholar Back to article
44. https://cryptosith.org/michael/data/talks/2015-04-28-UWNumberTheorySeminar.pdf
Search in Google Scholar Back to article
45. Scott, M. Re: NIST Announces Set of Elliptic Curves. Posting to the sci.crypt Mailing List, 1999.
Search in Google Scholar Back to article
46. Savaş, E., T. A. Schmidt, C. K. Koç. Generating Elliptic Curves of Prime Order. – In: Proc. of InInternational Workshop on Cryptographic Hardware and Embedded Systems, 14 May 2001. Berlin, Heidelberg, Springer, pp. 142-158.10.1007/3-540-44709-1_13
Search in Google Scholar Back to article
47. Alekseev, E. K., V. D. Nikolaev, S. V. Smyshlyaev. On the Security Properties of Russian Standardized Elliptic Curves. Vol. 9, 2018, No 3, pp. 5-32.10.4213/mvk260
Search in Google Scholar Back to article
48. Petitcolas, F. La cryptographie Militaire. 1883.
Search in Google Scholar Back to article
49. Yin, E. Curve Selection in Elliptic Curve Cryptography. San Jose State University, Project, Spring, 2005.
Search in Google Scholar Back to article
50. Abhishek, K., E. G. Raj. Computation of Trusted Short Weierstrass Elliptic Curves for Cryptography. – Cybernetics and Information Technologies, Vol. 21, 2021, No 2, pp. 70-88.10.2478/cait-2021-0020
Search in Google Scholar Back to article