CSIDH - The inverse problem

OptimalNailcutter1337

3/6/24, 6:08 PM

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

125

2 + 2

elliptic-curves

isogeny

Myath

3/6/24, 8:52 PM

Where is the claim that it is easy from?

OptimalNailcutter1337

3/7/24, 7:43 PM

@Myath Sorry, my mistake. I meant that if the coefficient A is 0 in this equation: y^2 = x^3 + Ax^2 + x.

Score:2

Crypto

Daniel S

3/7/24, 7:27 AM

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.

+ 2

OptimalNailcutter1337

3/7/24, 7:44 PM

So it's not possible even if $E$ is computed in a weird manner?

Daniel S

3/7/24, 9:13 PM

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

Score:2

Crypto

yyyyyyy

3/8/24, 7:18 AM

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

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: CSIDH - The inverse problem

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.