Can someone explain how the Gallant-Lambert-Vanstone method works (or which literature explains it)?

It is also unclear to me how the Frobenius endomorphism can be used in some cases for a speedup.

Also: how does it make sure that an attack remains infeasible (by using this method)?

(I am especially interested because of the sec256k1 curve which uses the method)

  • $\begingroup$ Does crypto.stackexchange.com/a/60626 answer your question? We don't know that an attack is impossible but after two decades nobody's found one, other than the obvious speedup of using the endomorphism in rho attacks or similar. $\endgroup$ Mar 29, 2019 at 16:22
  • $\begingroup$ Thansk for the link, very helpful. Why is β a nontrivial root of unity when β^2 + β + 1 = 0? $\endgroup$ Mar 29, 2019 at 16:53
  • $\begingroup$ Note that $\beta^2 = -\beta - 1$. Can you find what $\beta^3$ is using this relation? (Side note: If the equation $\beta^2 + \beta + 1 = 0$ isn't familiar, or perhaps as it is more often written, $\omega^2 + \omega + 1 = 0$, consider brushing up on some algebra, maybe Galois-flavored.) $\endgroup$ Mar 29, 2019 at 17:04
  • $\begingroup$ I was aware that this holds in e.g. GF(4) using polynomials (x^3 = 1) but not for β in Fp. I guess I'll look into that, thanks! $\endgroup$ Mar 29, 2019 at 17:17
  • $\begingroup$ It holds in any field, even in those of characteristic zero like $\mathbb C$! Of course, there may not be a nontrivial cube root of unity in the field, but if there is some $\beta$ with $\beta^2 + \beta + 1 = 0$ then $\beta$ is a cube root of unity. Exercise: If $p \equiv 1 \pmod 3$, how can you find such a $\beta$? $\endgroup$ Mar 29, 2019 at 17:24