[curves] The genus 3 setting
johannes.merkle at secunet.com
Wed Apr 16 08:57:37 PDT 2014
Diego Aranha wrote on 16.04.2014 16:47:
> It's the same deal with Weil descent attacks. We know Weil descent
> works in principle in arbitrary characteristic, but most of the
> detailed examples and algorithms in the literature are
> characteristic-2 specific (going back to the Gaudry--Hess--Smart
> paper). While a more general treatment looks more trouble than it's
> worth, that *doesn't* mean that an elliptic curve over GF(p^3) can't
> be easily attacked using the general theory and ad-hoc
> algorithms---and that's why nobody uses those curves.
> Hi Ben!
> If I get your message correctly, we actually do use curves over GF(p^3) in the context of pairing-based cryptography.
> For example, Kachisa-Schaeffer-Scott are curves with embedding degree 18 and a sextic twist, thus group G_2 becomes a
> curve over GF(p^3):
> Could a DLP in G_2 have complexity lower than 2^192 for such parameters?
That is exactly the point I wanted to ask for: According to Gaudry, the DLP in E(GF(p^n)) can be solved in O~(q^(2-2/n))
which gives O~(q^(4/3)) for n=3. This exponent is only by 1/9 better than the exponent 3/2 for a generic attack (e.g.
Pollard's Rho). But this result is only asymptotic. I am wondering if there is any benefit in the Weil-descent for n=3
More information about the Curves