Time-memory trade-offs for index calculus in genus 3

DOI10.1515/JMC-2014-0033MaRDI QIDQ2515965zbMATH OpenOpenAlexFDO

Authors Kim Laine, Kristin Lauter

Publication date 7 August 2015

Published in Journal of Mathematical Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/jmc-2014-0033

zbMATH Keywords

discrete logarithm problemdouble large primegenus 3index calculusnon-hyperelliptic curveplane curvequartic curvetime-memory trade-off

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Cryptography (94A60)

Review text

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.

Recommendations

• Index calculus in class groups of non-hyperelliptic curves of genus three
• Isogenies and the Discrete Logarithm Problem in Jacobians of Genus 3 Hyperelliptic Curves
• Index calculus attack for hyperelliptic curves of small genus
• An L (1/3 + ε) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
• Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with \((\ell ,\ell ,\ell)\)-isogenies

Cited in

(10)

• Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves
• On the discrete logarithm problem for plane curves
• Improved sieving on algebraic curves
• Constructing genus-3 hyperelliptic Jacobians with CM
• Fractional LWE: a nonlinear variant of LWE
• The arithmetic of Jacobian groups of superelliptic cubics
• Field extensions and index calculus on algebraic curves
• Index calculus algorithm for non-planar curves
• On the concrete security of LWE with small secret
• Trustless unknown-order groups

This page was built for publication: Time-memory trade-offs for index calculus in genus 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515965)