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

Improve this question
$\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
    Commented Jan 9, 2021 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
    Commented Jan 11, 2021 at 2:27

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jan 27, 2021 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
    Commented Jan 28, 2021 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
    Commented Jan 28, 2021 at 9:03
  • $\begingroup$ oh sure, what makes the difference was E. I guess I had a typo. $\endgroup$
    – Taylor Huang
    Commented Feb 1, 2021 at 3:05

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.