[curves] The genus 3 setting

[Johannes Merkle]

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