[curves] The genus 3 setting

[Watson Ladd]

Dear all,
I'm reporting work by Kim Laine on the discrete log problem on the
Jacobian of a genus 3 hyperelliptic curve.

In this setting the group size of Jac_C(F_q) is roughly q^3 by
Hasse-Weil. However, there is an index calculus attack of time
O~(q^{4/3}), where ~ means ignoring a log factor. However, there is a
problem in that there may be an isogeny to a non-hyperelliptic curve.

On the non hyperelliptic genus 3 curve there is a theorem of Diem that
discrete log can be done in time O~(q). Kim Laine demonstrated that it
can be done in time O~(q^{1/2}). That's why genus 3 isn't competitive:
one has to ensure all isogenous curves are hyperelliptic, and this is
not automatic.

Anyway, bottom line is genus 1 and 2 are where things are interesting.
In genus 1 thanks to Edwards curves we have very nice arithmetic:
genus 2 isn't so nice.

Sincerely,
Watson Ladd