A general framework for subexponential discrete logarithm algorithms
A large family of cryptographic systems is based on the difficulty of the discrete logarithm problem: Given a group \(G\) and some element \(a\in G\) and \(b\) such that \(b \in \langle a\rangle\) find an integer \(n\) with \(a^n = b\). Groups used for this purpose include the multiplicative group of finite fields, the class group of number fields (mostly imaginary quadratic fields) and divisor class groups of elliptic and hyperelliptic curves.NEWLINENEWLINENEWLINEOver the last few years a variety of subexponential methods have been developed for these groups to solve the discrete logarithm problem. In this article the authors present a generic framework that, under the additional assumption that the order of \(a\) is known, will find \(n\) in all the above cases. Futhermore, specializations of their framework yield the previously known best algorithms or improve them. In the case of Jacobians of hyperelliptic curves over finite fields, the new methods give a substantial improvement over previously known algorithms.NEWLINENEWLINENEWLINEThe power of their generic approach is also demonstrated by a rigorous complexity analysis showing that under the assumption of the order of \(a\) being known, the discrete logarithm problem is solvable in expected subexponential time. A key ingredient is a randomized version of Lanczos' algorithm, for which they give a complexity analysis too.
- scientific article; zbMATH DE number 1795243
- scientific article; zbMATH DE number 799760
- An algorithm for solving the discrete log problem on hyperelliptic curves
- A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
- An L (1/3 + ε) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
- Index calculus in class groups of non-hyperelliptic curves of genus three
- Constructive and destructive facets of Weil descent on elliptic curves
- Formulae for arithmetic on genus 2 hyperelliptic curves
- Indiscreet logarithms in finite fields of small characteristic
- On the complexity of the discrete logarithm and Diffie-Hellman problems
- Extending the GLS endomorphism to speed up GHS Weil descent using Magma
- Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
- Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms
- Koblitz curves over quadratic fields
- A simple method for obtaining relations among factor basis elements for special hyperelliptic curves
- A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
- An \(L(1/3)\) discrete logarithm algorithm for low degree curves
- Cryptographic implications of Hess' generalized GHS attack
- Smoothness testing of polynomials over finite fields
- Algebraic groups and discrete logarithm
- Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
- Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
- Finding discrete logarithms with a set orbit distinguisher
- On the discrete logarithm problem in class groups of curves
- Cryptanalysing the critical group: efficiently solving Biggs's discrete logarithm problem
- A double large prime variation for small genus hyperelliptic index calculus
- scientific article; zbMATH DE number 5289787 (Why is no real title available?)
- Elementary thoughts on discrete logarithms
- An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
- Smooth ideals in hyperelliptic function fields
- scientific article; zbMATH DE number 1795243 (Why is no real title available?)
- On the discrete logarithm problem in finite fields of fixed characteristic
- Slope packings and coverings, and generic algorithms for the discrete logarithm problem
- The arithmetic of Jacobian groups of superelliptic cubics
- Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree
- Using symmetries in the index calculus for elliptic curves discrete logarithm
- scientific article; zbMATH DE number 799760 (Why is no real title available?)
- Computation of a 30750-bit binary field discrete logarithm
- On algorithmic constructions of isogenies of elliptic curves over finite fields and their applications
- A new method for decomposition in the Jacobian of small genus hyperelliptic curves
- ON BOUNDS FOR BALANCED EMBEDDING DEGREE
- Hyperelliptic curves, Cartier-Manin matrices and Legendre polynomials
- Curves, Jacobians, and cryptography
- Parameterized Splitting Systems for the Discrete Logarithm
- Field extensions and index calculus on algebraic curves
- Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
- LATIN 2004: Theoretical Informatics
- Algebraic curves and cryptography
- A new perspective on the powers of two descent for discrete logarithms in finite fields
- Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures
- The structured generic-group model
- Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
- A review on the isomorphism classes of hyperelliptic curves of genus 2 over finite fields admitting a Weierstrass point
- Index calculus in the trace zero variety
- Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes
This page was built for publication: A general framework for subexponential discrete logarithm algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2781453)
