This article presents methods and algorithms for the computation of isogenies of degree ℓn. Some of these methods are obtained using recurrence equations and generating functions. A standard multiplication based algorithm for computation of isogeny of degree ℓn has time complexity equal to O(n2 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:
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 (um) and (cm) where cm 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.
The concept of a hybrid scheme with connection of SIDH and ECDH is nowadays very popular. In hardware implementations it is convenient to use a classical key exchange algorithm, which is based on the same finite field as SIDH. Most frequently used hybrid scheme is SIDH-ECDH. On the other hand, using the same field as in SIDH, one can construct schemes over Fpn, like Diffie-Hellman or XTR scheme, whose security is based on the discrete logarithm problem. In this paper, idea of such schemes will be presented. The security of schemes, which are based on the discrete logarithm problem over fields Fp; Fp2 ; Fp4 ; Fp6 and Fp8 , for primes p used in SIDH, will be analyzed. At the end, the propositions of practical applications of these schemes will be presented.
en
pl
