[curves] The genus 3 setting

[Ben Smith]

Hi All,

Excuse the belated de-lurking...

TL;DR : Don't use hyperelliptic genus 3 curves.  We have a
construction that will transfer DLPs for a reasonably large class of
them.  It looks hard to generalize this to the generic hyperelliptic
genus 3 curve, but the theoreticians are most the way there.  I would
say that right now, attacking any *one* curve outside that class is a
painful-but-not-impossible exercise.

2014-04-10 18:32 GMT+02:00 Kim Laine <laine at math.berkeley.edu>:
> All curves of genus <= 2 are hyperelliptic so the fast non-hyperelliptic
> index calculus methods do not apply. Really the increase in speed comes from
> some simple geometry tricks that work for plane curves, but hyperelliptic
> curves are never plane curves (whereas for instance genus 3 non-HE are plane
> quartics).

Yes.  If you try to apply, say, the original Diem plane curve
algorithm to a hyperelliptic genus 3 curve then it turns out to be
*slower* than traditional (ie, Hess-style) hyperelliptic index
calculus.  I think the main reason for this is that the complexity of
the plane curve algorithm ultimately depends on the degree of the
curve, and one of the distinctive features of hyperelliptic plane
curves is that they have very high degree relative to their genus.  As
Kim says, genus 3 non-hyperelliptics are plane quartics; but genus 3
hyperelliptic plane curves are essentially plane octics.

> Ben Smith's isogeny was the first demonstration of isogeny attacks. Recently
> there has been interesting advance in computing more general explicit
> isogenies using completely different methods (work of Robert, Bisson, Cosset
> and some others) so these isogeny attacks are very relevant now and seem
> hard to avoid in genus 3.

If you can compute an isogeny, then generally you can pass to a
non-hyperelliptic DLP, which is amenable to faster index calculus.  My
original paper used a geometric construction I found in the algebraic
geometry literature to write down such an isogeny, just as a proof of
concept.  The Robert/Bisson/Cosset/Lubicz/etc theta-function based
methods are much more general.  The one thing missing from their
results for fully general index-calculus transfer in genus 3 is an
analogue of Thomae's formulae (which are classical in genus 2):
basically, an algebraic recipe to reconstruct the codomain curve from
theta constants.  Alternatively: we're missing an explicit isomorphism
from a principally polarized abelian threefold the Jacobian of some
curve, which you know must exist.

But while these formulae would be cool to have from a purely
mathematical point of view, there's probably no need for them if you
want to transfer a specific genus 3 hyperelliptic DLP.  Getting
speculative for a moment: if some company set up a particular
challenge curve in genus 3 (where the isogenies I wrote down aren't
rational), then I am certain that someone with enough algebraic
geometry / function-field background, and enough time on their hands,
could go and compute a non-hyperelliptic codomain curve for it.

(For example: the Robert--Bisson--Cosset avIsogenies package will
compute a codomain abelian variety for you, and then you could try to
find any smooth nonhyperelliptic curve in that abelian variety.  Or
even its singular image in the hyperelliptic Jacobian.  There's
nothing to stop you just hacking away to find such a curve---probably
using a *lot* of computer algebra, but even this is a trivial
precomputation compared with the subsequent index calculus.)

Writing down an efficient and fully general algorithm that will
transfer the DLP away from any and all hyperelliptic genus 3 curves
looks like much, much more work.  The point is that ultimately we have
no need for such an algorithm: we know the isogenies exist in general,
and there's no obvious way to guarantee that your chosen genus 3
hyperelliptic curve would be resistant to a determined algebraic
geometer using ad-hoc methods.  We've seen it can be done for a large
class of curves, and I (for one) am pretty confident that we could
improvise a treatment for any particular curve outside that class.

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

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