Treffer: An $L (1/3 + \varepsilon)$ Algorithm for the Discrete Logarithm Problem for Low Degree Curves

Title:
An $L (1/3 + \varepsilon)$ Algorithm for the Discrete Logarithm Problem for Low Degree Curves
Authors:
Enge, Andreas, Gaudry, Pierrick
Contributors:
Algorithmic number theory for cryptology (TANC), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de Saclay, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Curves, Algebra, Computer Arithmetic, and so On (CACAO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Moni Naor
Source:
Eurocrypt 2007. :379-393
Publisher Information:
CCSD; Springer, 2007.
Publication Year:
2007
Collection:
collection:X
collection:CNRS
collection:INRIA
collection:INPL
collection:IMB
collection:LIX
collection:INRIA-SACLAY
collection:X-DEP-INFO
collection:INRIA_TEST
collection:INRIA-LORRAINE
collection:LORIA2
collection:INRIA-NANCY-GRAND-EST
collection:TESTALAIN1
collection:UNIV-LORRAINE
collection:INRIA2
collection:LORIA
collection:DEPARTEMENT-DE-MATHEMATIQUES
collection:AM2I-UL
Subject Terms:
ACM: G.: Mathematics of Computing, G.4: MATHEMATICAL SOFTWARE, G.4.0: Algorithm design and analysis, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.1: Numerical Algorithms and Problems, F.2.1.4: Number-theoretic computations (e.g., factoring, primality testing), [INFO.INFO-CR]Computer Science [cs], Cryptography and Security [cs.CR], [MATH.MATH-AG]Mathematics [math], Algebraic Geometry [math.AG]
Subject Geographic:
Barcelona, Spain
Original Identifier:
ARXIV: cs.CR/0703032
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/cs.CR/0703032
Access URL:
https://inria.hal.science/inria-00135324
https://inria.hal.science/inria-00135324v1/document
https://inria.hal.science/inria-00135324v1/file/l13.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00135324v1
Database:
HAL

Weitere Informationen

The discrete logarithm problem in Jacobians of curves of high genus $g$ over finite fields $\FF_q$ is known to be computable with subexponential complexity $L_{q^g}(1/2, O(1))$. We present an algorithm for a family of plane curves whose degrees in $X$ and $Y$ are low with respect to the curve genus, and suitably unbalanced. The finite base fields are arbitrary, but their sizes should not grow too fast compared to the genus. For this family, the group structure can be computed in subexponential time of $L_{q^g}(1/3, O(1))$, and a discrete logarithm computation takes subexponential time of $L_{q^g}(1/3+\varepsilon, o(1))$ for any positive~$\varepsilon$. These runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve algorithms.