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.

  • 1
    $\begingroup$ 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. $\endgroup$ – corpsfini Sep 19 at 8:50
  • $\begingroup$ @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$. $\endgroup$ – qbt937 Sep 19 at 20:03
  • $\begingroup$ Semaev's approach definitely works over extension fields of characteristic $p$. $\endgroup$ – Samuel Neves Sep 29 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.