6
$\begingroup$

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

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

with the quote "recommendation to avoid using base curves defined over Fp 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.

$\endgroup$
5
$\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.

$\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

$\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.

$\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.