3
$\begingroup$

I started studying CSIDH a few weeks ago and, seeing these papers [1] [2], I was wondering:

  • Given $[a]E$ and $E$, find $[a]^{-1}E$.

I read that is easy to find $[a]^{-1}E_0$ knowing $[a]E_0$ by quadratic twisting, but I haven't found any resources explaining how to compute $[a]^{-1}E$.

So, is it possible to compute $[a]^{-1}E$ knowing $[a]E$ and $E$?

Improve this question
$\endgroup$
2
  • $\begingroup$ Where is the claim that it is easy from? $\endgroup$
    – Myath
    Commented Mar 6, 2023 at 20:52
  • $\begingroup$ @Myath Sorry, my mistake. I meant that if the coefficient A is 0 in this equation: y^2 = x^3 + Ax^2 + x. $\endgroup$
    – OptimalNailcutter1337
    Commented Mar 7, 2023 at 19:43

2 Answers 2

Reset to default
3
$\begingroup$

In "traditional" CSIDH, where $E\colon\ y^2=x^3+x$, it always holds true that $[\mathfrak a^{-1}]E$ is the quadratic twist of $[\mathfrak a]E$.

Very concretely, if $[\mathfrak a]E$ is the Montgomery curve $E_A\colon\ y^2=x^3+Ax^2+x$, then $[\mathfrak a^{-1}]E$ is the Montgomery curve $E_{-A}\colon y^2 = x^3-Ax^2+x$.

Improve this answer
$\endgroup$
2
$\begingroup$

You are describing the inverse hard homogenous space ($\mathrm{InvHHS}$) problem (see definition 2.1.6 of your first paper) also known as the Inverse CSIDH problem (see problem 4 of your second paper). This is believed to be hard. It is analogous to the inverse Diffie-Hellman problem: given generator $G$ and a multiple $aG$ compute $a^{-1}G$. However, although the inverse Diffie-Hellman problem is known to be as hard as the regular computational Diffie-Hellman problem in cyclic groups of prime order, I do not know of a proof that solving $\mathrm{InvHHS}$ solves $\mathrm{CDH-HSS}$ (the reverse is true; again see the first paper) in the classical setting. There is a reduction for the in the quantum setting when the HHS is an isogeny space (see Appendix A of the second paper) where the quantum capability is used to compute the associated quadratic class group using the methods of Sean Hallgren.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So it's not possible even if $E$ is computed in a weird manner? $\endgroup$
    – OptimalNailcutter1337
    Commented Mar 7, 2023 at 19:44
  • $\begingroup$ @OptimalNailcutter1337 Not sure that I follow you; your problem statement furnished the solver with $E$ and $[a]E$ and no additional information. Additional information could render the problem easier e.g. if you also tell the solver the value of $a$. $\endgroup$
    – Daniel S
    Commented Mar 7, 2023 at 21:13

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.