International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Claus Diem

Publications

Year
Venue
Title
2017
EUROCRYPT
2008
JOFC
2005
EPRINT
Index Calculus in Class Groups of Plane Curves of Small Degree
Claus Diem
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)})$.
2004
ASIACRYPT
2004
EPRINT
A double large prime variation for small genus hyperelliptic index calculus
In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.

Program Committees

Asiacrypt 2009
Asiacrypt 2008