[curves] The genus 3 setting
Ben Smith
hyperelliptic at gmail.com
Wed Apr 16 08:58:38 PDT 2014
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
More information about the Curves
mailing list