[curves] The genus 3 setting
Johannes Merkle
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.
>
> Cheers,
>
> ben
>
>
> 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):
>
> https://eprint.iacr.org/2012/232.pdf
>
> 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
in practice.
--
Johannes
More information about the Curves
mailing list