Generating isogenies between ordinary elliptic curves in quantum sub-exponential time

93 Views Asked by At

I'm a Computer Science major, so the mathematics in "Constructing elliptic curve isogenies in quantum subexponential time" by Childs et al. (2010) go way over my head.

I'm currently looking at supersingular curves, for which the isogeny problem is still conjectured to be hard.

My question is, if any of you read that paper, if you can condense for a higher-mathematics somewhat-illiterate student, what the assumptions of the structure of the curve the authors of the paper made, that hold for ordinary curves but not supersingular ones. Thank you!

Edit: I found the answer in a different paper, namely "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by Jao and De Feo. See section 5, last paragraph.

2

There are 2 best solutions below

1
On

That paper shows an attack on isogenies on nonsupersingular curves. The other paper which is on supersingular curves is more secure and the attack is subexponential (p^1/6).

0
On

One of the constructional differences between ordinary and suppersingular eliptic curves appears in their endomorphism rings. ‎The subexponential quantum algorithm that breaks the isogeny problem for ordinary elliptic curves uses the commutativity of the endomorphism ring of these curves‎. ‎In contrast‎, ‎supersingular curves are secure against this attack due to non-commutativity of their corresponding endomorphism rings.