# DSSP reduction to DSSI

In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional Supersingular Isogeny (DSSI) problem is mentioned. However, I could not find such a reduction anywhere, or even some kind of idea how to compute such a reduction.

Question: How to reduce DSSP to DSSI?

Alternativly some source for post-quantum cryptography reductions featuring the given problem?

## 1 Answer

Suppose given a DSSP instance $\phi$, $(E_1,E_2,\phi')$ as defined in the paper. The goal is to use a DSSI oracle to decide if $\phi'$ is "parallel" to $\phi$ with "distance" $\ell_B^{e_B}$, that is, whether there exist $\ell_B^{e_B}$-isogenies $\psi,\psi'$ that make the following diagram commute.

$$\require{AMScd}\begin{CD} E_0 @>\phi>> E_3\\ @V\psi VV @VV \psi'V\\ E_1 @>>\phi'> E_2 \end{CD}$$

By definition of the DSSP problem, we are in one of two worlds:

• $(E_1,E_2)$ were chosen by picking an $\ell_B^{e_B}$-isogeny $\psi$ and computing $(E_1,E_2,\phi')$ to satisfy the diagram; in particular, $E_1$ is $\ell_B^{e_B}$-isogenous to $E_0$.
• $(E_1,E_2)$ were chosen randomly among all pairs of $\ell_A^{e_A}$-isogenous supersingular curves over $\mathbb F_{p^2}$; in particular, $E_1$ is random.

Hence by applying the DSSI oracle with respect to $\ell_B^{e_B}$-isogenies to $E_1$, we may distinguish between those two worlds with high probability.

There is a chance of false positives: A random curve $E_1$ may still be $\ell_B^{e_B}$-isogenous to $E_0$ by chance, and it's unlikely that $E_2$ would be $\ell_B^{e_B}$-isogenous to $E_3$ in that case. However, it is not hard to show that the advantage of our constructed DSSP oracle is at least $1-\varepsilon$ times that of the DSSI oracle, where $\varepsilon$ is the proportion of curves $\ell_B^{e_B}$-isogenous to $E_0$ within the set of all supersingular elliptic curves over $\mathbb F_{p^2}$. Typically, parameters are chosen such that $\ell_B^{e_B}\approx\sqrt p$, hence since the number of supersingular elliptic curves over $\mathbb F_{p^2}$ is lower bounded by $p/12$ we have $\varepsilon\leq (\ell_B+1)\ell_B^{e_B-1}\cdot 12/p\approx1/\sqrt p$ which is exponentially small in $\log p$. Therefore our DSSP oracle has non-negligible advantage assuming the DSSI oracle does.

Note that the DSSI problem is only stated for $\ell_A^{e_A}$-isogenies in the paper. I assume the intention was to leave the degree variable, or at least (by symmetry) also allow Bob's degree $\ell_B^{e_B}$, which I used above.