3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.