0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Luca De Feo Jan 9 at 11:45
  • $\begingroup$ @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 $\endgroup$ – Taylor Huang Jan 11 at 2:27
1
$\begingroup$

If you have a solver for P1, then it can also solve P2, so the problems are comparable: P2 is easier.

P1 is assumed hard, and is used as the basis of, e.g. https://eprint.iacr.org/2020/1012.

P1 is known to be generically equivalent to P3 (see https://hal.archives-ouvertes.fr/hal-02373179 and https://eprint.iacr.org/2020/1012), however P2 is probably not equivalent to P4: the reduction does not work for these more constrained problems, and P4 is known to be easy, whereas P2 is likely not.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – Taylor Huang Jan 27 at 7:45
  • $\begingroup$ just for clarification, by ''worst-case'' I meant that an P1 solver are required to solve for s^2E for each E that is given to him, while in the ''average-case'' such solver are only required to solve for s^2 E for most E. The main difference is that, in the average-case hardness of P1, we require s^2 E to not only be hard to solve at some instances of E but also that it is hard to solve for most E. Therefore, a reduction algorithm from P2 to P1 couldn't query the P1 solver on a fixed curve E0. $\endgroup$ – Taylor Huang Jan 28 at 2:40
  • 1
    $\begingroup$ So what counts is where E is drawn from, not where s is drawn from. But, yes, you're right, I'm talking about worst case. $\endgroup$ – Luca De Feo Jan 28 at 9:03
  • $\begingroup$ oh sure, what makes the difference was E. I guess I had a typo. $\endgroup$ – Taylor Huang Feb 1 at 3:05

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.