Score:2

Group isomorphisms between elliptic curves defined over ground fields with different extension degrees

au flag

Given $E/K$ defined over a finite field extension $K$, can I find another curve $E'/K'$ and a group isomorphism $\phi: E/K \to E'/K'$, where $K'$ has an extension degree lower than that of $K$?

If $K = K'$ then we speak of isogenies defined over $K$, but I am specifically looking for an isomorphism defined over finite fields of different extension degree.

For instance given $E(\mathbb{F}_{p^2})$ for prime $p$, can I find a curve $E'(\mathbb{F}_r)$ for prime $r$ and an invertible map $\phi$ between the two that preserves addition of points?

(Motivation: implement addition in $E(\mathbb{F}_{p^2})$ using addition in curves defined over prime fields)

kelalaka avatar
in flag
If I were you, I would have asked at math.se where there are many people with good knowledge of this field.
au flag
@kelalaka thanks for the suggestion. I know for a fact that there are experts here at crypto stack exchange with very deep understanding and are willing to help (see e.g. answers to my other questions). In any case, I may add more crypto motivation.
Lev avatar
jp flag
Lev
Given that $E$ and $E'$ are supersingular curves over their respective fields, if you want a group isomorphism between $G = E(\mathbb{F}_{p^2})$ and $G' = E'(\mathbb{F}_{t})$, you need that $|G| = |G'|$. That is, that either $(p+1)^2 = t+1$ or $(p-1)^2 = t+1$. This contradicts the primality of $t$. I think this would extend to other cases too but needs a different argument.
kelalaka avatar
in flag
https://math.stackexchange.com/q/4556659/338051
au flag
@lev, why are you assuming that E, E' are supersingular? In any case, your argument looks good, they can't be (simultaneously) supersingular.
Lev avatar
jp flag
Lev
Hence I didn't add it as an answer. Just a particular case, I am sure you could prove this doesn't work in an easier way, but one method would be to show it would be case by case. For instance, supersingular and ordinary would also not work due to the difference in the group structures. The remaining case would be ordinary to ordinary.
au flag
Thanks. I just want to point out that this argument holds when the extension degrees are 2 and 1. But it doesn't directly rule out the existence of such a map between say supersingular curves defined over $\mathbb{F}_{p^3}$ and $\mathbb{F}_{q^2}$ for primes $p, q$. (My intuition is that your argument can be generalized contradicting primality of $p, q$, perhaps with Weil conjectures?). So perhaps we could limit the scope (for now) to extension degrees 2 and 1, and non-supersingular elliptic curves.
kelalaka avatar
in flag
I’m voting to close this question because already asked Math.se where it got more attention.
au flag
@kelalaka If I get another vote to close, I will close; given that you suggested to ask in math.SE and then voted to close this. But I think that this question might be of more interest here than in Math.SE, given the motivation. Let me know if there are any concerns.
yyyyyyy avatar
in flag
@kelalaka I think this question fits better here. Just have a look at the comments: The Math.SE question received nothing but clarification requests trying to resolve an evident linguistic divide, whereas here it already has a partial answer.
kelalaka avatar
in flag
@yyyyyyy my approach was about not having cross-dupes and this task was mainly on the OP. They could delete this or another. If not receive the attention they needed they can ask even at mathoverflow. Yes, the math people behave like that and they might be right about that on their subject. Anyway, I can cancel my close vote, if the OP deletes the Math version.
forest avatar
vn flag
@zugzwang I think this is fine here, since it may be math, but it's quite specific to cryptography.
Score:1
cn flag

Say you have $E_1/K_1 \rightarrow E_2/K_2$ How would you even define such isomorphism? Assuming it is a rational map then it can be expressed as a pair of polynomials. In what field are the coefficients in? This is expressed usually when you say "a map/curve is defined over $K$" i.e. the coefficients are from $K$.

Imagine in your example $K_1 = \mathbb{F}_p, K_2 = \mathbb{F}_t$ where $gcd(t,p)=1$ then clearly $K_1$ is not a subfield of $K_2$ and vice versa. Also their algebraic closures are different.

Now say you have $Q = (a,b) \in E_1(\mathbb{F}_p)$ so $Q=(a,b)$ is a pair of elements in $\mathbb{F}_p$. $(c,d) = \phi(Q) \in E_2(\mathbb{F}_t)$ is a pair of elements in $\mathbb{F}_t$.

In more detail, the value $c$ is calculated as $c = \frac{f(a,b)}{g(a,b)}$ where $f,g$ are polynomials in 2 variables with coefficients in $K_1$ or $K_2$ (for the sake of the argument).

If $f(x,y)\in K_1[x,y]$ then $f(a,b)$ is an element of $K_1$ and also has to be of $K_2$ since we assume $c$ is in $K_2$. Therefore $K_1$ is a subfield of $K_2$.

If $f(x,y)\in K_2[x,y]$ then when calculating $f(a,b)$ you get a problem. You need to do field operations between elements of $K_1$ ($a$ and $b$) and $K_2$ (coeffs in $f$). How do you do that? How do you multiply $v \in \mathbb{F}_5$ with $w \in \mathbb{F}_7$ for example? It does not make sense. It makes sense if there is some relation between $K_1$ and $K_2$ being subfields but not in general.

I think in general, you need $K_1$ to be a subfield of $K_2$ but I am not sure at the moment. But this is just meant to ilustrate why the question does not really make sense.

au flag
Thanks for the image. Yes, of course such map cannot simply be a polynomial or rational mapping from $\mathbb F_p$ to $\mathbb F_t$, as operations do not make sense. But I can certainly define a map from $\mathbb F_p$ to $\mathbb F_t$ and vice versa by other means. For instance by fixing the representatives, embedding in $\mathbb Z$ and projecting. So I ask, is there a reason to rule out anything that is _not_ a polynomial/rational map?
mangohost

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.