[curves] The genus 3 setting

[Ben Smith]

Hi Diego,

2014-04-16 16:47 GMT+02:00 Diego Aranha <dfaranha at gmail.com>:
>
> If I get your message correctly, we actually do use curves over GF(p^3) in
> the context of pairing-based cryptography.

Sorry, I should have added the standard "non-pairing-based" disclaimer...

> 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?

I don't think so.  The 192-bit security means r has to have 384 bits,
so p has way more (being a pairing-based scenario; it has 508 bits in
your paper, right?)...  And then reducing to a nonhyperelliptic genus
3 curve over GF(p) gives you index calculus for discrete logs running
in O~(p) (with Diem) or O~(p^{1/2}) (with Laine, according to the
first post).  The point being that O~(p^{1/2}) is much more than
O~(r^{1/2}), so you could solve your DLP using Pollard rho faster than
you could by Weil-descent-plus-isogeny-plus-index-calculus.

For the KSS curve in your paper, if I've understood things properly,
the curve subgroup and the finite field were chosen so that solving a
DLP would require a work factor of about 2^192 (with rho on the curve,
or NFS-DL in the field).  But solving a DLP in a genus 3 Jacobian over
GF(p) would be on the order of 2^254 (assuming O~(p^{1/2}) IC): no
loss of security there.  I'd be much more concerned about the hardness
of the FF dlog in that case.


ben

-- 
You know we all became mathematicians for the same reason: we were lazy.
  --Max Rosenlicht