Index calculus in the trace zero variety

DOI10.3934/AMC.2015.9.515zbMATH Open1333.14025arXiv1405.1059OpenAlexW2963900975MaRDI QIDQ895005FDOQ895005

Authors: Elisa Gorla, Maike Massierer 

Publication date: 25 November 2015

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Abstract: We discuss how to apply Gaudry's index calculus algorithm for abelian varieties to solve the discrete logarithm problem in the trace zero variety of an elliptic curve. We treat in particular the practically relevant cases of field extensions of degree 3 or 5. Our theoretical analysis is compared to other algorithms present in the literature, and is complemented by results from a prototype implementation.

Full work available at URL: https://arxiv.org/abs/1405.1059

Recommendations

• scientific article; zbMATH DE number 5130646
• Trace formulas and the Conley-Zehnder index
• The index of an algebraic variety
• Index Theory on Curves
• Trace Densities and Algebraic Index Theorems for Sheaves of Formal Cherednik Algebras
• Traces in oriented homology theories of algebraic varieties
• scientific article; zbMATH DE number 4172019
• The index theorem and the trace formula
• Field extensions and index calculus on algebraic curves
• Rational formulas for traces in zero-dimensional algebras

zbMATH Keywords

discrete logarithm problemelliptic curve cryptographyindex calculustrace zero variety

Mathematics Subject Classification ID

Varieties over finite and local fields (11G25) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Algebraic number theory computations (11Y40) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Cites Work

• The Magma algebra system. I: The user language
• Title not available (Why is that?)
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
• A new index calculus algorithm with complexity \(L(1/4+o(1))\) in small characteristic
• Title not available (Why is that?)
• Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
• Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
• An algorithm for solving the discrete log problem on hyperelliptic curves
• Endomorphisms for faster elliptic curve cryptography on a large class of curves
• Title not available (Why is that?)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Solving sparse linear equations over finite fields
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• Information and Communications Security
• Modern computer algebra
• Title not available (Why is that?)
• Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields
• Title not available (Why is that?)
• On the discrete logarithm problem in elliptic curves. II
• Title not available (Why is that?)
• Fast evaluation of logarithms in fields of characteristic two
• Improving the complexity of index calculus algorithms in elliptic curves over binary fields
• On polynomial systems arising from a Weil descent
• Title not available (Why is that?)
• Constructive and destructive facets of Weil descent on elliptic curves
• Title not available (Why is that?)
• On the correct use of the negation map in the Pollard rho method
• A double large prime variation for small genus hyperelliptic index calculus
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• Index calculus in class groups of non-hyperelliptic curves of genus three
• Elliptic curve discrete logarithm problem over small degree extension fields
• Title not available (Why is that?)
• A general framework for subexponential discrete logarithm algorithms
• On the discrete logarithm problem in elliptic curves
• Title not available (Why is that?)
• Using symmetries in the index calculus for elliptic curves discrete logarithm
• Title not available (Why is that?)
• Decomposition attack for the Jacobian of a hyperelliptic curve over an extension field
• An L (1/3 + ε) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
• Algorithmic Number Theory
• Index calculus attack for hyperelliptic curves of small genus
• Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
• Title not available (Why is that?)
• Using abelian varieties to improve pairing-based cryptography
• Point compression for the trace zero subgroup over a small degree extension field
• An \(L(1/3)\) discrete logarithm algorithm for low degree curves
• Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
• Title not available (Why is that?)
• On the Discrete Logarithm Problem on Algebraic Tori
• Solving the elliptic curve discrete logarithm problem using Semaev polynomials, Weil descent and Gröbner basis methods -- an experimental study
• A Variant of the F4 Algorithm
• The Function Field Sieve in the Medium Prime Case
• Title not available (Why is that?)
• Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs
• Solving a $$6120$$ -bit DLP on a Desktop Computer
• Title not available (Why is that?)
• The Special Function Field Sieve
• Discrete logarithm in \(\mathrm{GF}(2^{809})\) with FFS

Cited In (7)

• On index calculus algorithms for subfield curves
• An optimal representation for the trace zero subgroup
• Solving multivariate polynomial systems and an invariant from commutative algebra
• Title not available (Why is that?)
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• Trace Zero Varieties over Fields of Characteristic 2 for Cryptographic Applications
• Title not available (Why is that?)

Uses Software

• Magma

This page was built for publication: Index calculus in the trace zero variety

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