محاسبه آيزوجني هاي بين خم هاي بيضوي ابرمنفرد

چكيده انگليسي :

Computing isogenies between supersingular elliptic curves Peyman Shahbazi peyman shahbazi sw @gmail com January 26 2020 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Reza Rezaeian Farashahi farashahi@cc iut ac irAdvisor Dr Majid Gazor mgazor@cc iut ac ir2000 MSC 11G20 11G15 14G50 11Y16 11T71Keywords Supersingular Elliptic curves Isogeny Supersingular isogeny Isogeny graph Abstract This M Sc thesis is based on the following papers S D Computing isogenies between supersingular elliptic curves over Fp Codes D C G Cryptography 78 2 425 440 2016 Computational problems in supersingular elliptic curve S D G F V isogenies Quantum Information Processing 17 2018 IACR Cryptology ePrint Archive 2017 774 The problem of computing an isogeny between two given elliptic curves has been studied by many authors and hasseveral applications A natural question that has not previously been considered is to construct isogenies between twogiven supersingular elliptic curves over Fp Let p 3 be a prime and let E E be supersingular elliptic curves over Fp We want to construct an isogeny E E The currently fastest algorithm for finding isogenies between supersingular elliptic curves solves this 1 1problem in the full supersingular isogeny graph over Fp2 It takes an expected O p 2 bit operations and also O p 2 space we consider the structure of the isogeny graph of supersingular elliptic curves over Fp We give an algorithm to 1construct isogenies between supersingular curves over Fp that works in O p 4 We then discuss howthis algorithmcan be used to obtain an improved algorithm for the general supersingular isogeny problem Let p be a prime q pn for some integer n and let L be a non empty set of small primes with p L Let K be p The supersingular isogeny graph X K L is a directed graph where the vertices are K isomorphismeither Fq or Fclasses of supersingular elliptic curves over K and the edges are equivalence classes of l isogenies defined over K between such curves for l L If we regard the full supersingular isogeny graph X Fp l it suffices to considerelliptic curves defined over Fp2 since the j invariant of a supersingular elliptic curve always lies in Fp2 In general the isogenies will still be defined over Fp though Let Sp2 be the set of all supersingular j invariants in Fp2 It is well known that for a prime p 3 we have 0 p 1 12 p 12 1 p 5 7 #Sp2 12 12 2 p 11 In contrast to the ordinary case the graph X Fp l has an irregular structure but is always fully connected for everyprime l Thus we can use a chain of isogenies of small prime degree i e l 2 to construct an isogeny betweentwo given supersingular elliptic curves over Fp2 Those isogenies are fast to compute These graphs are known to beexpanders so they have small diameter and there is a short path between any two vertices A natural problem is to finda path between any two vertices in the graph Ageneral meet in the middle idea for finding paths in graphs alsocalled bi directional search was proposed by Pohl This idea was used by Galbraith 6 to construct isogenies

شهبازي، پيمان

محاسبه آيزوجني هاي بين خم هاي بيضوي ابرمنفرد

خم بيضوي ابرمنفرد , آيزوجني هاي بين خم هاي بيضوي , گراف آيزوجني