The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic
type: Item
instance of: scholarly article
title: The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic
zbMATH Open document ID: 1400.14072
author: Jean-Charles Faugère
author: Alexandre Wallet
published in: Designs, Codes and Cryptography
publication date: 2018-09-06T00:00:00Z
review text: The paper under review deals with the discrete logarithm problem in the divisor class group \(\mathrm{Jac}(C)\) of a hyperelliptic curve or an elliptic curve \(C\) defined over a finite field. The computation of discrete logarithms in such groups can be done using a variant of the Index-Calculus algorithm called a decomposition attack. Such algorithms run in two phases. This paper focus in the first one, called relations collection or harvesting. In this phase, a linear system is built by finding linear relations between the discrete logarithms of elements of a special subset, the so-called factor base. These relations can be found by solving multiple instances of the Point m-Decomposition Problem (\(PDP_m\)) which is the following: Given an element \(R\) and a subset \(B\) of \(\mathrm{Jac}(C)\), find, if they exist, \(D_1,\ldots,D_m\in B\) such that \(R=D_1+\cdots+D_m\). In [\textit{G. Hanrot} (ed.) et al., Algorithmic number theory. 9th international symposium, ANTS-IX, Nancy, France, July 19--23, 2010. Proceedings. Berlin: Springer (2010; Zbl 1196.11006)] a method is proposed for solve instances of this problem by describing decompositions using functions in suitable Riemann-Roch spaces. When the curve \(C\) is elliptic, an alternate approach involving Weil descent on summation polynomials can also be used. The general goal of this paper is to design an efficient method for solving \(PDP_m\) instances. For this task, the authors propose new techniques to reduce the degree of the systems obtained from the harvesting in even characteristic. They develop in parallel methods which deal with Nagao's approach and with summation approach as well. Finally, they compare them, adding their new degree reduction algorithm, to determine which is more efficient when \(C\) has genus \(> 1\). Finally, Nagao's approach is used to estimate the total running time for the harvesting on a binary genus 2 curve with class group of around \(2^{184}\) elements.
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 14G15
zbMATH DE Number: 6933691
zbMATH Keywords: discrete logarithm
zbMATH Keywords: index calculus
zbMATH Keywords: algebraic curves
zbMATH Keywords: curve-based cryptography
zbMATH Keywords: algebraic attacks
zbMATH Keywords: Gröbner bases
reviewed by: Dimitros Poulakis
describes a project that uses: NTL
describes a project that uses: FGb
describes a project that uses: Magma
describes a project that uses: CADO-NFS
MaRDI profile type: Publication
full work available at URL: s10623-017-0449-y
OpenAlex ID: W2774118421
cites work: The Magma algebra system. I: The user language
cites work: A new efficient algorithm for computing Gröbner bases \((F_4)\)
cites work: Q4412976
cites work: Q3413659
cites work: Algorithmic Number Theory
cites work: On the discrete logarithm problem in elliptic curves
cites work: Q4450525
cites work: FGb: A Library for Computing Gröbner Bases
cites work: Efficient computation of zero-dimensional Gröbner bases by change of ordering
cites work: Q4660688
cites work: Using symmetries in the index calculus for elliptic curves discrete logarithm
cites work: Symmetrized Summation Polynomials: Using Small Order Torsion Points to Speed Up Elliptic Curve Index Calculus
cites work: Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
cites work: The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems
cites work: Recent progress on the elliptic curve discrete logarithm problem
cites work: Summation Polynomial Algorithms for Elliptic Curves in Characteristic Two
cites work: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
cites work: Q3374896
cites work: Fast genus 2 arithmetic based on Theta functions
cites work: The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines
cites work: Cover and Decomposition Index Calculus on Elliptic Curves Made Practical
cites work: Elliptic curve discrete logarithm problem over small degree extension fields
cites work: Factorization of a 768-Bit RSA Modulus
cites work: Computation of a 768-Bit Prime Field Discrete Logarithm
cites work: Q4273679
cites work: Arithmetic on abelian and Kummer varieties
cites work: Handbook of finite fields
cites work: Decomposition Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field
cites work: Q4409130
DOI: 10.1007/S10623-017-0449-Y
Recommended article: Q3374896
Recommended article: Point Decomposition Problem in Binary Elliptic Curves
Recommended article: Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
Recommended article: Hyperelliptic curves for the vector decomposition problem over fields of even characteristic
Recommended article: Encoding Points on Hyperelliptic Curves over Finite Fields in Deterministic Polynomial Time
Recommended article: Computing integral points on genus 2 curves estimating hyperelliptic logarithms
Recommended article: Q3043949
Recommended article: A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over \(\text{GF}(q)\)
Recommended article: Correspondences on Hyperelliptic Curves and Applications to the Discrete Logarithm
Recommended article: Q3413070
description: scientific article; zbMATH DE number 6933691