CryptoDB
Index Calculus in Class Groups of Plane Curves of Small Degree
| Authors: | |
|---|---|
| Download: | |
| 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)})$. |
BibTeX
@misc{eprint-2005-12455,
title={Index Calculus in Class Groups of Plane Curves of Small Degree},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / discrete logarithm problem},
url={http://eprint.iacr.org/2005/119},
note={ diem@iem.uni-due.de 12891 received 18 Apr 2005},
author={Claus Diem},
year=2005
}