# CSIDH - The inverse problem

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

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

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$$.
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.
• So it's not possible even if $E$ is computed in a weird manner? Mar 7, 2023 at 19:44
• @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$. Mar 7, 2023 at 21:13