1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2011
    Rep Power

    Genus 2 Hyperelliptic curves

    I'd like to know why the index calculus doesn't work on genus 2 hyperelliptic curves.

    In addiction are these curves used practically in cryptography and for what?

  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Rep Power
    I know almost nothing about ordinary elliptic curves, let alone hyperelliptic curves.

    However, I am brilliant at scanning wikipedia articles. Hyperelliptic curves are a family of equations, of which elliptic curves are a special case.

    According to the wikipedia article, the issue isn't that index calculus (an algorithmic approach to solving the discrete logarithm problem, or DLP) doesn't work on hyperelliptic curves of genus 2. (For these equations, "genus" is related to the exponential degree.)

    Rather, for curves whose genus is greater than 2, index calculus is relatively efficient -- and for this reason, the DLP is not so difficult to solve with such curves. However, for curves of genus 2, index calculus is NOT the best algorithm; and the best algorithms are very computationally expensive.

    This is important, because the security case for cryptosystems based on elliptic curves, rests on the computational complexity of solving the DLP. Where this complexity is believed to be high (in other words, the best known attack algorithm requires very large amounts of computation), the cryposystems are hoped to be secure.

    Therefore, there are some precautions which must be taken when choosing a hyperelliptic curve for cryptography, so as to ensure that there will be no known "shortcut" for solving the DLP -- and one of them restricting the curve to genus 2.

    According to wikipedia, hyperelliptic curves are used in the NTRU cryptosystem, which apparently has been put to practical use. A claimed advantage for this system, is using small amounts of resources, so it is relatively well suited to very small processors.

IMN logo majestic logo threadwatch logo seochat tools logo