Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem

DOI10.1016/j.jsc.2008.08.005zbMath1177.94148OpenAlexW2083052384MaRDI QIDQ733510

Pierrick Gaudry

Publication date: 16 October 2009

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2008.08.005

zbMATH Keywords

elliptic curvesabelian varietiesdiscrete logarithm problemWeil descentindex calculus

Mathematics Subject Classification ID

Cryptography (94A60) Abelian varieties of dimension (> 1) (11G10) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Related Items (43)

A simple method for obtaining relations among factor basis elements for special hyperelliptic curves ⋮ The Supersingular Isogeny Problem in Genus 2 and Beyond ⋮ On index calculus algorithms for subfield curves ⋮ Semi-Regular Sequences and Other Random Systems of Equations ⋮ A SAT-Based Approach for Index Calculus on Binary Elliptic Curves ⋮ A Note on Diem’s Proof ⋮ Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP ⋮ Fiat-Shamir and correlation intractability from strong KDM-secure encryption ⋮ Solving degree, last fall degree, and related invariants ⋮ The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic ⋮ Summation Polynomial Algorithms for Elliptic Curves in Characteristic Two ⋮ Field extensions and index calculus on algebraic curves ⋮ Quasi-subfield polynomials and the elliptic curve discrete logarithm problem ⋮ Index calculus in the trace zero variety ⋮ Acceleration of Index Calculus for Solving ECDLP over Prime Fields and Its Limitation ⋮ Cover attacks for elliptic curves over cubic extension fields ⋮ The complexity of solving Weil restriction systems ⋮ Elliptic curve cryptography: the serpentine course of a paradigm shift ⋮ Elliptic curve discrete logarithm problem over small degree extension fields ⋮ Recent progress on the elliptic curve discrete logarithm problem ⋮ Endomorphisms for faster elliptic curve cryptography on a large class of curves ⋮ Using symmetries in the index calculus for elliptic curves discrete logarithm ⋮ Solving multivariate polynomial systems and an invariant from commutative algebra ⋮ New results on quasi-subfield polynomials ⋮ On the discrete logarithm problem for prime-field elliptic curves ⋮ An optimal representation for the trace zero subgroup ⋮ Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? ⋮ A generic approach to searching for Jacobians ⋮ Cryptographic implications of Hess' generalized GHS attack ⋮ Complexity bounds on Semaev's naive index calculus method for ECDLP ⋮ Cover attacks for elliptic curves with cofactor two ⋮ On the complexity of computing Gröbner bases for weighted homogeneous systems ⋮ A Variant of the F4 Algorithm ⋮ Improvement of FPPR method to solve ECDLP ⋮ On the discrete logarithm problem in class groups of curves ⋮ Endomorphisms for Faster Elliptic Curve Cryptography on a Large Class of Curves ⋮ Generating Genus Two Hyperelliptic Curves over Large Characteristic Finite Fields ⋮ On the Security of Pairing-Friendly Abelian Varieties over Non-prime Fields ⋮ Faster Halvings in Genus 2 ⋮ Using abelian varieties to improve pairing-based cryptography ⋮ Koblitz curves over quadratic fields ⋮ Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves ⋮ Point compression for the trace zero subgroup over a small degree extension field

Uses Software

• FGb

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Index calculus in class groups of non-hyperelliptic curves of genus three
• Parallel collision search with cryptanalytic applications
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• The discrete logarithm problem on elliptic curves of trace one
• Constructive and destructive facets of Weil descent on elliptic curves
• The Xedni calculus and the elliptic curve discrete logarithm problem
• Analysis of the Xedni calculus attack
• A general framework for subexponential discrete logarithm algorithms
• The Jacobian and formal group of a curve of genus 2 over an arbitrary ground field
• A double large prime variation for small genus hyperelliptic index calculus
• Elliptic Curve Cryptosystems
• Monte Carlo Methods for Index Computation (mod p)
• Reducing elliptic curve logarithms to logarithms in a finite field
• Evaluation of discrete logarithms in a group of 𝑝-torsion points of an elliptic curve in characteristic 𝑝
• Factoring multivariate polynomials via partial differential equations
• Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree
• Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
• An L (1/3 + ε) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
• On the Discrete Logarithm Problem on Algebraic Tori
• Algorithmic Number Theory
• Advances in Cryptology - ASIACRYPT 2003

This page was built for publication: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem