Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

Paper 2005/119

Index Calculus in Class Groups of Plane Curves of Small Degree

Claus Diem

Abstract

We present a novel index calculus algorithm for the discrete logarithm problem (DLP) in degree 0 class groups of curves over finite fields. A heuristic analysis of our algorithm indicates that asymptotically for varying q, ``essentially all'' instances of the DLP in degree 0 class groups of curves represented by plane models of a fixed degree d over $\mathbb{F}_q$ can be solved in an expected time of $\tilde{O}(q^{2 -2/(d-2)})$. A particular application is that heuristically, ``essentially all'' instances of the DLP in degree 0 class groups of non-hyperelliptic curves of genus 3 (represented by plane curves of degree 4) can be solved in an expected time of $\tilde{O}(q)$. We also provide a method to represent ``sufficiently general'' (non-hyperelliptic) curves of genus $g \geq 3$ by plane models of degree $g+1$. We conclude that on heuristic grounds the DLP in degree 0 class groups of ``sufficiently general'' curves of genus $g \geq 3$ (represented initially by plane models of bounded degree) can be solved in an expected time of $\tilde{O}(q^{2 -2/(g-1)})$.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
discrete logarithm problem
Contact author(s)
diem @ iem uni-due de
History
2005-04-21: received
Short URL
https://ia.cr/2005/119
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/119,
      author = {Claus Diem},
      title = {Index Calculus in Class Groups of Plane Curves of Small Degree},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/119},
      year = {2005},
      url = {https://eprint.iacr.org/2005/119}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.