Index calculus in class groups of non-hyperelliptic curves of genus three (Q1021239)

The first author presented in 2006 an index calculus algorithm, with double large prime variation, to solve the DLP in class groups of curves over finite fields represented by plane models of small degree [\textit{C. Diem}, in: Algorithmic number theory. 7th international symposium, ANTS-VII, Berlin, Germany, July 23--28, 2006. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 4076, 543--557 (2006; Zbl 1143.11361)]. In the paper under review, the authors study in detail some variants of this algorithm in the concrete case of non-hyperelliptic curves of genus \(3\), represented by non-singular plane quartics. Suppose \(C\) is such a quartic over the finite field \(\mathbb{F}_q\); then, asymptotically for \(q\to\infty\), the DLP in the group \(\text{Pic}^0(C)\) can be solved in an expected time of \(\tilde{O}(q)\). This analysis was based in two heuristic assumptions of the former paper; one of them is proved in the present paper, and the other one is studied experimentally. The results confirm that the cryptographic protocols based on the DLP in the group \(\text{Pic}^0(C)\) should use curves \(C\) of genus \(1\) or \(2\), both for efficiency and security reasons.