# CSIDH Squaring Fixing the Base Curve

Consider the following variants of the CSIDH squaring problem.

P1. Given $$sE, E$$ where $$s$$ is a random ideal class and $$E$$ is a random curve (reachable from initial $$E_0$$), find $$s^2E$$

P2. Given $$sE_0$$ where $$s$$ is a random ideal class and $$E_0:y^2=x^3+x$$ is a fixed initial curve, find $$s^2E_0$$.

Of course, there's also the decisional variant:

DP1. Given $$sE,tE,E$$ where $$E$$ is a random curve as above and $$s,t$$ are either i.i.d. sample of ideal class or $$s^2=t$$, decide which.

DP2. Given $$sE_0,tE_0$$ where $$E_0:y^2=x^3+x$$ and $$s,t$$ are either i.i.d. sample of ideal class or $$s^2=t$$, decide which.

What do we know about the hardness of (D)P1 compared to (D)P2? Are they even comparable?

I would also like to stress that, for another equivalent problem called the inverse problem stated in P3, fixing the base curve to $$E_0$$ would weakens P3 to P4 as easy as finding a quadratic twist. However, computing quadratic twists would only reduce (D)P2 to itself. So it is not so obvious whether the hardness of (D)P2 is weaken.

P3. Given $$sE,E$$ find $$s^{-1}E$$.

P4. Given $$sE_0$$ find $$s^{-1}E_0$$.

• P1 and P2 look incomplete: what's the goal? Find s? As for DP1 and DP2, they're trivial as stated: sE = tE iff s = t. – Luca De Feo Jan 9 at 11:45
• @LucaDeFeo oops, I've fixed the description. P1 and P2 are to find $s^2 E$ and the constraint in DP1, DP2 are $s^2=t$ rather than $s=t$... my bad – Taylor Huang Jan 11 at 2:27

• hi, thanks for your reply. but I think that P1 and P2 are only comparable in their worst-case hardness? since here $s$ is drawn randomly form Cl(O), we are talking about their average hardness. is it still comparable? – Taylor Huang Jan 27 at 7:45