Suppose there is an elliptic curve $E$ in form $y^2=x^3+b$ defined over $\mathbb{F_p}$, where $p$ is large prime. #$E(\mathbb{F_p})$ is also a large prime but #$E(\mathbb{F_p})\ne p$. ECDLP on this curve is in the form of $Q=[k]P$. Now let's define the same curve but over extension field $\mathbb{F_p}^6$. #$E(\mathbb{F_p}^6)$ is composite with many small primes (this composite number for sure is divided by #$E(\mathbb{F_p})$ and factors of an order of sextic twist of $E$). $P$ on $E$ over $\mathbb{F_p}^6$ have the same prime order as it has on curve over $\mathbb{F_p}$.

Can I use Pohlig-Hellman algorithm to solve $k$ on curve $E$ over $\mathbb{F_p}^6$?

  • $\begingroup$ Pohlig-Hellman requires all factors of the order to be small enough to be brute-forceable with an $O(\sqrt q_i)$ algorithm. Given that $p$ is big and #$E(\mathbb F_p)$ is roughly the same bitlength as $p$ and #$E(\mathbb F_p)$ divides #$E(\mathbb{F_p}^6)$, this sounds unlikely? $\endgroup$ – SEJPM Jun 20 at 12:40
  • $\begingroup$ But if I know something about $k$ for example $k<x$ where $x$ is known there is a possibility to omit largest factors of #$E(\mathbb{F_p}^6)$. But I have doubts about orders. Pohlig-Hellman is applicable if #$E(\mathbb{F_p}^6)$ is not prime or order of $P$ is not prime? Because in this case #$E(\mathbb{F_p}^6)$ is composite, but order of $P$ is prime. $\endgroup$ – NET_BOT Jun 20 at 13:06

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.