Simple Verification of Completeness of Two Addition Formulas on Twisted Edwards Curves

• Autorzy: Dryło Robert , Kijko Tomasz

Identyfikatory

DOI

10.24425/ijet.2020.131899

• Języki publikacji: EN

Abstrakty

EN

Daniel Bernstein and Tanja Lange [9] proved that two given addition formulas on twisted Edwards elliptic curves ax² + y² = 1 + dxy are complete (i.e. the sum of any two points on a curve can be computed using one of these formulas). In this paper we give simple verification of completeness of these formulas using a program written in Magma, which is based on the fact that completeness means that some systems of polynomial equations have no solutions. This method may also be useful to verify completeness of additions formulas on other models of elliptic curves.

Słowa kluczowe

EN

twisted Edwards curves; complete set of addition formulas; Gröbner bases

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2020
• Tom: Vol. 66, No. 3
• Strony: 459--464
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Dryło Robert

• Warsaw School of Economics, Warsaw, Poland

autor

Kijko Tomasz

• Institute of Mathematics and Cryptology, Military University of Technology, Warsaw, Poland

Bibliografia

• [1] W. W. Adams, P. Loustaunau, An introduction to Gröbner bases (No. 3). American Mathematical Soc. (1994)
• [2] Arene, C., Lange, T., Naehrig, M., & Ritzenthaler, C. Faster computation of the Tate pairing. Journal of number theory, 131(5), 842-857 (2011).
• [3] Atkin, A. O. L., Morain, F. Elliptic curves and primality proving. Mathematics of computation, 61(203), 29-68 (1993).
• [4] Bernstein, D., Birkner, P., Lange, T., & Peters, C. ECM using Edwards curves. Mathematics of Computation, 82(282), 1139-1179 (2013).
• [5] D. Bernstein, P. Birkner, M. Joye, T. Lange and Ch. Peters, ”Twisted Edwards curves”, In: Progress in Cryptology-AFRICACRYPT 2008, Springer, 2008, pp. 389-405.
• [6] Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B. Y. Highspeed high-security signatures. Journal of cryptographic engineering, 2(2), 77-89 (2012).
• [7] D. Bernstein and T. Lange, ”Faster addition and doubling on elliptic curves”, In: Advances in cryptology-ASIACRYPT 2007, Springer, 2007, pp. 29-50.
• [8] Bernstein, D. J., Chuengsatiansup, C., Kohel, D., & Lange, T. Twisted hessian curves. In International Conference on Cryptology and Information Security in Latin America (pp. 269-294). Springer, Cham (2015).
• [9] D. Bernstein and T. Lange, ”A complete set of addition laws for incomplete Edwards curves”. Journal of Number Theory, 131(5), pp. 858-872 (2011).
• [10] O. Billet and M. Joye, ”The Jacobi model of an elliptic curve and side-channel analysis”, In: AAECC-15 Conference Proceedings, Lecture Notes in Computer Science, vol. 2643, Springer, 2003, pp. 34-42.
• [11] Bosma, W., & Lenstra, H. W. Complete systems of two addition laws for elliptic curves. Journal of Number theory, 53(2), 229-240 (1995).
• [12] W. Castryck and F. Vercauteren, ”Toric forms of elliptic curves and their arithmetic”, Journal of Symbolic Computation, vol. 46, issue 8, (2011), Elsevier, 2011, pp. 943-966.
• [13] D. Cox, J. Little, D. O’shea, Ideals, varieties, and algorithms (Vol. 3). New York: Springer (1992)
• [14] De Feo, L., Jao, D., & Plût, J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 8(3), 209-247 (2014).
• [15] Dryło, R., Kijko, T., & Wroński, M. Determining Formulas Related to Point Compression on Alternative Models of Elliptic Curves. Fundamenta Informaticae, 169(4), 285-294 (2019).
• [16] Farashahi, R. R., & Joye, M. Efficient arithmetic on Hessian curves. In International Workshop on Public Key Cryptography (pp. 243-260). Springer, Berlin, Heidelberg (2010).
• [17] Edwards, H. A normal form for elliptic curves. Bulletin of the American mathematical society, 44(3), 393-422 (2007).
• [18] Eicher, J., & Opoku, Y. Using the Quantum Computer to Break Elliptic Curve Cryptosystems (1997).
• [19] R. Farashahi and M. Joye, ”Efficient Arithmetic on Hessian Curves”, Lecture Notes in Computer Science, vol. 6056, Springer, 2010, pp. 243-260.
• [20] R. Farashahi and S. Hosseini, ”Differential Addition on Twisted Edwards Curves”, In: ACISP 2017: Information Security and Privacy, Lecture Notes in Computer Science, vol. 10343, Springer, 2017, pp. 366-378.
• [21] Hisil, H., Wong, K. K. H., Carter, G., & Dawson, E. Faster group operations on elliptic curves. In Information Security 2009: proceedings of the 7th Australasian Information Security Conference (Vol. 98, pp. 11-19). CRPIT/Springer (2009).
• [22] Hisil, H., Wong, K. K. H., Carter, G., & Dawson, E. Jacobi quartic curves revisited. In Australasian Conference on Information Security and Privacy (pp. 452-468). Springer, Berlin, Heidelberg (2009).
• [23] Hisil, H., Wong, K. K. H., Carter, G., & Dawson, E. Twisted Edwards curves revisited. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 326-343). Springer, Berlin, Heidelberg (2008).
• [24] Joye, M., Tibouchi, M., & Vergnaud, D. Huff’s model for elliptic curves. In International Algorithmic Number Theory Symposium (pp. 234-250). Springer, Berlin, Heidelberg (2010).
• [25] Kohel, D. Addition law structure of elliptic curves. Journal of Number Theory, 131(5), 894-919 (2011).
• [26] Lenstra Jr, H. W. Factoring integers with elliptic curves. Annals of mathematics, 649-673 (1987).
• [27] Moody, D., & Shumow, D. Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation, 85(300), 1929-1951 (2016).
• [28] Rostovtsev, A., & Stolbunov, A. Public-Key Cryptosystem Based on sogenies. IACR Cryptology ePrint Archive, 145 (2006).
• [29] Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). Ieee (1994, November).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).