Time-memory trade-offs for index calculus in genus 3 (Q2515965)

Motivated by cryptographic applications, the authors of this article discuss an algorithm for solving discrete logarithm problems in Jacobians of genus \(3\) non-hyperelliptic curves over a finite filed \(\mathbb{F}_q\) of \(q\) elements. The methods in [\textit{C. Diem} and \textit{E. Thomé}, J. Cryptology 21, No. 4, 593--611 (2008; Zbl 1167.11047)] and also [\textit{C. Diem}, ANTS-VII, Lect. Notes Comput. Sci. 4076, 543--557 (2006; Zbl 1143.11361)] yield an effective heuristic \(\tilde{O}(q)\) index calculus algorithm for solving discrete logarithm problems in Jacobians of genus \(3\) non-hyperelliptic curves over \(\mathbb{F}_q\). These methods are referred to as Diem's algorithm. In this article, the authors present and analyze an improved variant of Diem's algorithm. On the cost of a moderate memory increase, they show theoretically and practically how the computational complexity of their algorithm improves the computational complexity of Diem's algorithm. The authors also discuss time-memory trade-offs in real-life settings.