6
$\begingroup$

Found this report detailing a quantum algorithm for computing isogenies between supersingular elliptic curves.

https://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf

with the quote "recommendation to avoid using base curves defined over $\mathbb F_p$ in De Feo-Jao-Plut type schemes".

Is it correct then that 'Supersingular Isogeny Key Exchange' of De Feo is broken?

If so, as this is a fast moving field, are there any recommendations for alternate post quantum key exchange with reasonably good key size and speed?

Thank you.

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
7
$\begingroup$

Sorry I will have to answer my own question.

I received a mail from Luca De Feo a moment ago.
"Nope, I discussed this at length with Jean-François Biasse, and we couldn't find a way to apply this kind of attack to SSIKE."

I'll leave this question around for reference for the next person who wonders.

Improve this answer
$\endgroup$
5
$\begingroup$

Also, the algorithm given in the mentioned paper has a complexity os $\tilde{O}(p^{\frac{1}{4}})$. The best known attack (As mentioned by de Feo, Jao and Plut) on the SSIKE is based on the claw finding problem (see below) and has a complexity of $\theta(p^{\frac{1}{6}})$.

Very interesting paper btw ;): Claw finding algorithm using quantum walk

Improve this answer
$\endgroup$
1
$\begingroup$

Certainly not. This attack has been considered in De Feo's paper and their proposed parameters are resistant against this $O(p^\frac{1}{4})$-complexity attack.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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