Computing endomorphism rings of supersingular elliptic curves by finding cycles in concatenated supersingular isogeny graphs (Q6637319)

An elliptic curve \(E\) defined over the finite field \({\mathbb F}_{q}\) of characteristic \(p > 0\) is called supersingular if the order \(\sharp E({\mathbb F}_{q})\) of the group of \({\mathbb F}_{q}\)-rational points on \(E\) is \(q + 1 - t\), where \(t\) is divisible by \(p\). It is known that every supersingular elliptic curve defined over \({\mathbb F}_{q}\) is isomorphic to such a curve \(E\) defined over \({\mathbb F}_{p^{2}}\) whose endomorphism ring \(\mathrm{End}(E)\) is isomorphic to a maximal order of the quaternion algebra \(B_{p, \infty}\) over \({\mathbb Q}\) ramified exactly at \(p\) and \(\infty\). Computing such endomorphism rings is closely related to the security of supersingular isogeny-based cryptography, and in the present paper, the authors study the feasibility of computing \(\mathrm{End}(E)\) when \(E\) is defined over \({\mathbb F}_{p}\). Based on works of \textit{J. F. Mestre} [in: Class numbers and fundamental units of algebraic number fields, Proc. Int. Conf., Katata/Jap.217--242 (1986; Zbl 0621.14021)] and \textit{D. Kohel} [Endomorphism rings of elliptic curves over finite fields, Ph.D. thesis, University of California, Berkeley (1996)], the authors consider the set \(V\) of \(\overline{\mathbb F}_{p}\)-isomorphism classes of supersingular elliptic curves defined over \({\mathbb F}_{p^{2}}\), and the set \(G_{\ell}\) of pairs of elements of \(V\) with isogeny of degree \(\ell\) between them for a prime \(\ell \neq p\). Take a supersingular elliptic curve \(E_{0}\) defined over \({\mathbb F}_{p^{2}}\), and a set \(L\) of (small) primes with \(p \not\in L\). If there is a cycle containing (the \(\overline{\mathbb F}_{p}\)-isomorphism class of) \(E_{0}\) in the graph \N\[ \N{\mathcal G}_{L} \left( \overline{\mathbb F}_{p} \right) = \left( V, \ \bigcup_{l \in L} G_{\ell} \right), \N\] \Nthen we have an associated endomorphism of \(E_{0}\) as a product of isogenies of degree \(\ell \in L\). The authors improve works of \textit{E. Bank} et al. [Assoc. Women Math. Ser. 19, 41--66 (2019; Zbl 1436.11148)] and \textit{K. Eisenträger} et al. [Open Book Ser. 4, 215--232 (2020; Zbl 1460.11148)] for computing \(\mathrm{End}(E_{0})\) especially by finding such cycles of short length by random walks in \({\mathcal G}_{L} \left( \overline{\mathbb F}_{p} \right)\) until the cycles generate \(\mathrm{End}(E_{0})\). They also reported the running times of computing \(\mathrm{End}(E_{0})\) when \(E_{0}\) is defined over \({\mathbb F}_{p}\) for primes \(p\) with 10 to 30 bits.