Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
May 3rd, 2011, 12:19 PM
 yavanna87
Registered User

Join Date: May 2011
Posts: 1
Time spent in forums: 7 m 52 sec
Reputation Power: 0
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?

Thanks

#2
May 5th, 2011, 01:34 AM
 mah\$us
Contributing User

Join Date: Feb 2009
Posts: 179
Time spent in forums: 3 Days 2 h 35 m 17 sec
Reputation Power: 48
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.

 Viewing: Dev Shed Forums > System Administration > Security and Cryptography > Genus 2 Hyperelliptic curves