Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
type: Item
instance of: scholarly article
title: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
zbMATH Open document ID: 1177.94148
author: Pierrick Gaudry
published in: Journal of Symbolic Computation
publication date: 2009-10-16T00:00:00Z
review text: The present paper proposes an index calculus algorithm for computing the discrete logarithm problem (DLP) on abelian varieties and deduces an algorithm for the DLP on elliptic curves defined over small extensions fields, which is asymptotically faster than Pollard's rho method. Section 2 begins specifying the type of abelian variety to which the method applies: an abelian variety \(A\)\, of (small) dimension \(n\),\, defined over a finite field \(\mathbb F_q\),\, together with an explicit embedding of (a dense Zariski open of) \(A\)\, into an affine space of dimension \(n+m\). Also the points \(P=(x_1, \dots , x_n, y_1, \dots y_m)\in A\)\, are supposed to verify a triangular system of \(m\) equations. As the paper points out this definition covers the cases usually considered in Cryptography, as Jacobians of curves and Weil restrictions of them. Then Section 2 describes the algorithm, whose factor base is defined as the set of points \({\mathcal F}=\{(x_1,0,\dots, 0,y_1,\dots ,y_m)\in A;\,\, x_1,y_i\in\mathbb F_q \}\),\, assumed to be an absolutely irreducible curve and studies its complexity. If the parameters \(n,m\)\, and the degrees of the equations defining \(A\)\, are supposed to be constants, the ``Heuristic result 3'' says that for \(n\geq 2\)\, the asymptotic complexity is \(\widetilde{O}(q^{2-2/n})\). Section 3 applies the proposed algorithm to elliptic curves defined over \(\mathbb F_{q^n}\)\,,\, (\(n\)\, small). Using the Weil restriction approach and the summation polynomials of \textit{I. Semaev} [Preprint, \url{http://eprint.iacr.org/2004/031} (2004)], the paper obtains (Heuristic result 4) a probabilistic algorithm to solve the DLP on such a curve in heuristic time \(\widetilde{O}(q^{2-2/n})\). It also shows an explicit example in the case \(n=2\). Section 4 compares the above algorithm with the classical Weil descent attack [see \textit{P. Gaudry}, \textit{F. Hess} and \textit{N. P. Smart}, J. Cryptology 15, No. 1, 19--46 (2001; Zbl 0996.94036)], su…
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11G10
zbMATH DE Number: 5616454
zbMATH Keywords: discrete logarithm problem
zbMATH Keywords: index calculus
zbMATH Keywords: abelian varieties
zbMATH Keywords: elliptic curves
zbMATH Keywords: Weil descent
reviewed by: Juan Tena Ayuso
describes a project that uses: FGb
MaRDI profile type: Publication
full work available at URL: j.jsc.2008.08.005
OpenAlex ID: W2083052384
cites work: Q4847910
cites work: Q2707419
cites work: Algebraic groups and discrete logarithm
cites work: Q4450525
cites work: Algorithmic Number Theory
cites work: Index calculus in class groups of non-hyperelliptic curves of genus three
cites work: Q4317713
cites work: A general framework for subexponential discrete logarithm algorithms
cites work: An L (1/3 + ε) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
cites work: A new efficient algorithm for computing Gröbner bases \((F_4)\)
cites work: Q4660688
cites work: The Jacobian and formal group of a curve of genus 2 over an arbitrary ground field
cites work: Q4945368
cites work: Factoring multivariate polynomials via partial differential equations
cites work: Q3374896
cites work: Constructive and destructive facets of Weil descent on elliptic curves
cites work: A double large prime variation for small genus hyperelliptic index calculus
cites work: On the Discrete Logarithm Problem on Algebraic Tori
cites work: Q4434887
cites work: Q2739457
cites work: Analysis of the Xedni calculus attack
cites work: Elliptic Curve Cryptosystems
cites work: Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Q2724449
cites work: Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
cites work: Monte Carlo Methods for Index Computation (mod p)
cites work: Q4217446
cites work: Evaluation of discrete logarithms in a group of 𝑝-torsion points of an elliptic curve in characteristic 𝑝
cites work: The Xedni calculus and the elliptic curve discrete logarithm problem
cites work: The discrete logarithm problem on elliptic curves of trace one
cites work: Advances in Cryptology - ASIACRYPT 2003
cites work: Parallel collision search with cryptanalytic applications
DOI: 10.1016/J.JSC.2008.08.005
description: scientific article; zbMATH DE number 5616454