HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

The Point Decomposition Problem over Hyperelliptic Curves: toward efficient computations of Discrete Logarithms in even characteristic

Jean-Charles Faugère 1 Alexandre Wallet 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Computing discrete logarithms is generically a difficult problem. For divisor class groups of curves defined over extension fields, a variant of the Index-Calculus called Decomposition attack is used, and it can be faster than generic approaches. In this situation, collecting the relations is done by solving multiple instances of the Point m-Decomposition Problem (PDP$_m$). An instance of this problem can be modelled as a zero-dimensional polynomial system. Solving is done with Gröbner bases algorithms, where the number of solutions of the system is a good indicator for the time complexity of the solving process. For systems arising from a PDP$_m$ context, this number grows exponentially fast with the extension degree. To achieve an efficient harvesting, this number must be reduced as much as as possible. Extending the elliptic case, we introduce a notion of Summation Ideals to describe PDP m instances over higher genus curves, and compare to Nagao's general approach to PDP$_m$ solving. In even characteristic we obtain reductions of the number of solutions for both approaches, depending on the curve's equation. In the best cases, for a hyperelliptic curve of genus $g$, we can divide the number of solutions by $2^{(n−1)(g+1)}$. For instance, for a type II genus 2 curve defined over $\mathbb{F}_{2^{93}}$ whose divisor class group has cardinality a near-prime 184 bits integer, the number of solutions is reduced from 4096 to 64. This is enough to build the matrix of relations in around 7 days with 8000 cores using a dedicated implementation.
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-01658573
Contributor : Jean-Charles Faugère Connect in order to contact the contributor
Submitted on : Friday, December 15, 2017 - 3:23:17 PM
Last modification on : Monday, May 16, 2022 - 4:58:02 PM

File

HyperSum.pdf
Files produced by the author(s)

Identifiers

Citation

Jean-Charles Faugère, Alexandre Wallet. The Point Decomposition Problem over Hyperelliptic Curves: toward efficient computations of Discrete Logarithms in even characteristic. Designs, Codes and Cryptography, Springer Verlag, 2018, 86, pp.2279-2314. ⟨10.1007/s10623-017-0449-y⟩. ⟨hal-01658573⟩

Share

Metrics

Record views

951

Files downloads

195