{{ message }}

Instantly share code, notes, and snippets.

# defeo/ss-graphs

Created Feb 28, 2015
Problems on supersingular graphs and crypto
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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.