Orienting supersingular isogeny graphs

Leonardo Colò
I2M, Aix-Marseille Université

Date(s) : 26/09/2019   iCal
13 h 00 min - 14 h 00 min

Supersingular isogeny graphs have been used in the Charles–Goren–Lauter cryptographic hash function and the supersingular isogeny Diffie–Hellman (SIDH) protocole of De Feo and Jao. A recently proposed alternative to SIDH is the commutative supersingular isogeny Diffie–Hellman (CSIDH) protocole, in which the isogeny graph is first restricted to F_p-rational curves E and  F_p-rational isogenies then oriented by the quadratic subring Z[\pi] of  End(E) generated by the Frobenius endomorphism \pi on E.
We introduce a general notion of orienting supersingular elliptic curves and their isogenies, and use this as the basis to construct a general oriented super- singular isogeny Diffie-Hellman (OSIDH) protocole. By imposing the data of an orientation by an imaginary quadratic ring O, we obtain an augmented category of supersingular curves on which the class group Cl(O) acts faithfully and transitively. This idea is already implicit in the CSIDH protocol, in which supersingular curves over F_p are oriented by the Frobenius subring Z[\pi]  Z[\sqrt{−p}]. In contrast, we consider an elliptic curve E_0 oriented by a CM order O_K of class number one. To obtain a nontrivial group action, we consider l-isogeny chains, on which the class group of an order O of large index l^{n} in O_K acts, a structure we call a whirlpool. The map from l-isogeny chains to its terminus forgets the structure of the orientation, and the original base curve E_0, giving rise to a generic supersingular elliptic curve.
Within this general framework, we define a new oriented supersingular isogeny Diffie-Hellman (OSIDH) protocol, which has fewer restrictions on the proportion of supersingular curves covered and on the torsion group structure of the underlying curves. Moreover, the group action can be carried out effectively solely on the sequences of moduli points (such as j-invariants) on a modular curve, thereby avoiding expensive isogeny computations, and is further amenable to speedup by precomputations of endomorphisms on the base curve E_0.
 This is joint work with David Kohel.


Retour en haut