22
$\begingroup$

Previosly my impression on this subject was that hyperelliptic cryptography systems (as well as other possible cryptosystems based on abelian varieties of dimension $>1$) have no advantages over elliptic curve ones and are more difficult to implement. Yet Google search has demonstrated me that people are working on improving hyperelliptic cryptosystems and also implement them as computer programs. So my question is: is anybody currently using hyperelliptic cryptography "in practice", and what is the chance that anyone will prefer hyperelliptic cryptography to the elliptic one "soon enough".

Sorry if this question is not appropriate for MO.

$\endgroup$
  • 2
    $\begingroup$ I'd love to know what happened to Surface1271: cr.yp.to/hecdh.html -- as I understand it the genus 2 hyperelliptic Jacobians are expected to be a bit faster, but exact point counting on them is too difficult. There were some index calculus attacks against higher genus hyperelliptic Jacobians by Gaudry, Thériault, perhaps others. I think that the bottleneck here is really in the mathematicians' corner: exact point counting for ab vars over finite fields (via Schoof--figure out torsion mod small primes and appeal to Weil bounds) is still hard. Out of my depth here, salt liberally. $\endgroup$ – thel Feb 1 '16 at 18:06
  • $\begingroup$ There is a good talk by Steven Galbraith on hyperelliptic pairings math.auckland.ac.nz/~sgal018/Pairing2007.pdf In particular hecompare elliptic and hyperelliptic cases. $\endgroup$ – Alexey Ustinov Jan 3 '18 at 11:32
18
$\begingroup$

I am not aware of anybody seriously considering hyperelliptic curves for actual real-world usage, beyond toys, and I would be rather surprised to hear differently from anyone.

As you say, hyperelliptic provide comparatively few (if any!) advantages over elliptic curves but have the huge disadvantage that virtually nobody has well-tested, battle-hardened code for them. As a matter of fact, even elliptic curves are difficult to implement right, which is one of the reasons Dan Bernstein developed Curve25519 -- this is an elliptic curve (and more) which is designed to make it hard to screw up, compared to previously used ones.

Given all that, why should a practical cryptographer then bother with hyperelliptic curves?

To convince people who implement crypto to use a new cryptosystem is hard. Heck, some standard committees and vendors still are unsure about these new-fangled elliptic curves ;-).

And if they switch to something new, they usually want it to give some serious advantage, to justify the cost and the incompatibility. Such as (a high chance for) being safe against quantum computer attacks -- and hyperelliptic curves are no better in that regard than RSA or elliptic curves (i.e. they are completely broken if we ever get "real" quantum computers).

My best guesses as to why people still research crypto based on hyperelliptic curves are:

  1. habit,
  2. they are genuinely curious, and do the research for its own sake, not caring about applications,
  3. they suffer from the very disturbing, but also sadly widespread disconnection between crypto researchers who work purely theoretically, and people who actually implement it, and know how to do it properly. The intersection between these two sets is rather small, and a lot of crypto systems that look good on paper are completely useless in reality for that reason.

Being an algebraist myself, whose most applied results at best have application in theoretical physics (string theory for that), I am very reluctant to judge any research based on how applicable it is to real-world scenarios. But in this case, I am tempted... ;-)

$\endgroup$
  • $\begingroup$ Thank you! Actually, I am far from being "practical" myself; yet my opinion on the scientific value of an algorithm (that does not include any theorem as its part) does depend on the existence of an explanation why may this algorithm be "useful" (maybe, in future). $\endgroup$ – Mikhail Bondarko Feb 2 '16 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.