Problems on supersingular graphs and crypto

ss-graphs

Let $p≠2,3$ be a prime, and $\mathbb{F}_p$ the finite field with $p$ elements. We will use the following notation:

- $ℓ,ℓ_0,ℓ_1$ are primes bounded by $\DeclareMathOperator{\poly}{poly}\poly(\log p)$.
- $m,n$ are $\poly(\log p)$-smooth integers bounded by $\poly(p)$, with $m∧n=1$.
- $E, E_0, E_1, \dots$ are supersingular elliptic curves defined over $\mathbb{F}_{p^2}$.
- $j(E)$ is the $j$-invariant of $E$.
- $\DeclareMathOperator{\End}{End}\End(E)$ is the endomorphism ring of $E$.
- $B_{p,∞}$ is the quaternion algebra ramified at $p$ and infinity.
- $\newcommand{\O}{\mathcal{O}}\O, \O_0, \O_1, \dots$ are maximal orders of $B_{p,∞}$.
- $I, I_0, I_1, \dots$ are left ideals of some maximal order $\O$.
- $θ:\O_0→\End(E_0)$ is an isomorphism of maximal orders.
- If $E$ is a curve and $G⊂E(\bar{\mathbb{F}}_p)$ a finite subgroup, we denote by $E/G$ the image of the unique isogeny of kernel $G$.
- If $A$ is a point of $E$, we denote by $〈A〉$ the cyclic subgroup generated by $A$.

# Easy problems

This is a list of problems that are known to be solvable in time polynomial in $\log p$.

1. Given $j(E)$ compute all elliptic curves $ℓ$-isogenous to $E$ (Vélu's formulas, or modular polynomials).
1. Given curves $E_0,E_1$, isogenous of degree $ℓ$, compute the kernel of an isogeny $φ:E_0→E_1$ of degree $ℓ$ (Elkies formulas and related algorithms).
1. Given $E$ and a finite subgroup $A⊂E(\bar{\mathbb{F}}_p)$ of size $ℓ$, compute $E/A$ and the rational maps of the isogeny $φ:E→E/A$. (Vélu's formulas)
1. Given a maximal order $\O$, compute $j(E)$ such that $\End(E)≃\O$.
1. Given $\O_0,\O_1$, find an ideal $I$ which is a left $\O_0$-ideal and a right $\O_1$-ideal. We can further ask that the norm of $I$ is
	- a prime,
	- a prime power,
	- power-smooth.
1. Given $\O$ representing a small $ℓ$, compute $E$ such that $\End(E)≃\O$.

# Hard problems

This is a list of problems for which no algorithm polynomial in $\log p$ is known. Each of the problems below has a more restrictive variant where $m,n$ are prime powers.

1. Given $j(E)$, compute an order $\O$ such that $\O≃\End(E)$.
1. Given $E_0,E_1$ and an integer $m$, decide if $E_0$ and $E_1$ are $m$-isogenous.
1. Given $\O$, given a smooth $m$, is $m$ represented by $\O$?
1. Given $E_0,E_1$, find an isogeny $φ:E_0→E_1$.
1. Given $E_0,E_1$ and a smooth integer $m$, find an isogeny $φ:E_0→E_1$ of degree $m$.
1. Given $E,E/〈A〉,E/〈B〉,E/〈A,B〉$, where $A,B∈E$ are unknown points of orders $m,n$. Determine $A$ or $B$.
1. Given $E,E/〈A〉,E/〈B〉,E/〈A,B〉$ as above, given the image of $A$ in $E/〈B〉$. Determine $A$.
1. Given $E,E/〈A〉$, where $A∈E$ is an unknown point of order $m$. Given points $B,C∈E$ of order $n$, and their images in $E/〈A〉$. Determine $A$.
 
## Known reductions

Here we list known polynomial reductions between the hard problems given above.

- All problems reduce to 1. Indeed, we can combine it with easy problem 5 to solve each.