Optimal Strategies for Computation of Degree degree ℓⁿ Isogenies for SIDH

• Autorzy: Wroński Michał , Chojnacki Andrzej

Identyfikatory

DOI

10.24425/ijet.2020.131900

• Języki publikacji: EN

Abstrakty

EN

This article presents methods and algorithms for the computation of isogenies of degree ℓⁿ. Some of these methods are obtained using recurrence equations and generating functions. A standard multiplication based algorithm for computation of isogeny of degree ℓⁿ has time complexity equal to O(n²M (n log n)), where M (N) denotes the cost of integers of size N multiplication. The memory complexity of this algorithm is equal to O (n log (n log (n))). In this article are presented algorithms for: - determination of optimal strategy for computation of degree ℓⁿ isogeny, - determination of cost of optimal strategy of computation of ℓⁿ isogeny using solutions of recurrence equations, - determination of cost of optimal strategy of computation of ℓⁿ isogeny using recurrence equations, where optimality in this context means that, for the given parameters, no other strategy exists that requires fewer operations for computation of isogeny. Also this article presents a method using generating functions for obtaining the solutions of sequences (սₘ) and (cₘ) where cₘ denotes the cost of computations of isogeny of degree ℓᵘᵐum for given costs p, q of ℓ-isogeny computation and ℓ-isogeny evaluation. These solutions are also used in the construction of the algorithms presented in this article.

Słowa kluczowe

EN

SIDH; optimal strategies; generating functions

• 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: 465--472
• Opis fizyczny: Bibliogr. 3 poz., rys.

Twórcy

autor

Wroński Michał

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

autor

Chojnacki Andrzej

• Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology, Warsaw, Poland

Bibliografia

• [1] L. D. Feo, D. Jao, and J. Plût, “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” Cryptology ePrint Archive, Report 2011/506, 2011, https://eprint.iacr.org/2011/506.
• [2] C. Costello and H. Hisil, “A simple and compact algorithm for sidh with arbitrary degree isogenies,” in Advances in Cryptology – ASIACRYPT 2017, T. Takagi and T. Peyrin, Eds. Cham: Springer International Publishing, 2017, pp. 303–329.
• [3] C. Costello, P. Longa, and M. Naehrig, “Efficient algorithms for supersingular isogeny diffie-hellman,” in Advances in Cryptology – CRYPTO 2016, M. Robshaw and J. Katz, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016, pp. 572–601.

Uwagi

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