# Elliptic curve subgroup with $p$ elements in field of characteristic $p$

Are there any elliptic curves defined over a finite field $$\mathrm{GF}(p^k)$$ with a subgroup of order $$p$$ where the discrete log (and preferably DDH) problem is hard? Elliptic curve with prime subgroup equal to field size answers this question in the negative when $$k = 1$$, but Hasse's theorem doesn't rule out e.g. curves of order $$p (p - 1)$$ over $$\mathrm{GF}(p^2)$$. Smart's attack (and some similar approaches) works for anomalous elliptic curves, which have exactly $$p^k$$ points, but I'm not sure if it generalizes.

My motivation for asking this question is that I am trying to construct an elliptic curve in $$p^2$$ characteristic (so over a ring, not a field) where DDH is hard and can be used to hide something in the part of the ring that wouldn't be there if you mod out to characteristic $$p$$. This would allow the construction of an ECC-based additively homomorphic encryption scheme that has efficient decryption for long plaintexts because discrete log would be efficient for only those points that are the identity modulo $$p$$, similarly to how Paillier encryption uses that discrete log is efficient in a subgroup of $$(\mathbb Z / N^2 \mathbb Z)^\times$$.

However, there is an issue with doing this for most curves. Let $$E_p$$ be the group of the modulo $$p$$ elliptic curve, and $$E_{p^2}$$ a corresponding curve modulo $$p^2$$. It turns out that Hensel lifting allows $$p^k$$ ways of lifting a point in $$E_p$$ to one in $$E_{p^2}$$, so $$|E_{p^2}| = p^k |E_p|$$. The problem is then that if $$|E_p|$$ is not divisible by $$p$$ then multiplication by $$|E_p|$$ would give a point that is the identity modulo $$p$$, so the part I am attempting to hide would have an easy discrete log. The only hope to fix this is if $$E_{p^2} = E_p \times (\mathbb Z/p\mathbb Z)^k$$ and $$p$$ divides $$|E_p|$$, because then multiplication by $$|E_p|$$ would always output the identity element of $$E_{p^2}$$, losing all information. Hence my question about whether any such curve can be secure.

• This paper explains how to construct an isomorphism from the subgroup of order $p$ to the additive group of $GF(p^k)$. This answer in the thread you cited shows explicitely how to do it. I didn't try it, but I don't see why it shouldn't work. – corpsfini Sep 19 at 8:50
• @corpsfini I don't see how that is different from Smart's attack. I thought that the times-$p$ terms in the $p$-adic expansion of $x$ and $y$ essentially tracks the derivative. Also, maybe I missed something, but the paper you cite states that "Since $\phi$ is non-vanishing on ⟨P⟩, then φ is an isomorphism and the lemma is proved.", but doesn't say why $\phi(P) \ne 0$. – qbt937 Sep 19 at 20:03
• Semaev's approach definitely works over extension fields of characteristic $p$. – Samuel Neves Sep 29 at 17:29