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

$\endgroup$
2
  • $\begingroup$ Where is the claim that it is easy from? $\endgroup$
    – Myath
    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$ Mar 7, 2023 at 19:43

2 Answers 2

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

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

$\endgroup$
2
  • $\begingroup$ So it's not possible even if $E$ is computed in a weird manner? $\endgroup$ 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
    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.