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.
Type de document :
Article dans une revue
Designs, Codes and Cryptography, Springer Verlag, In press, 〈10.1007/s10623-017-0449-y〉
Liste complète des métadonnées

Littérature citée [47 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01658573
Contributeur : Jean-Charles Faugère <>
Soumis le : vendredi 15 décembre 2017 - 15:23:17
Dernière modification le : vendredi 31 août 2018 - 09:25:58

Fichier

HyperSum.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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, In press, 〈10.1007/s10623-017-0449-y〉. 〈hal-01658573〉

Partager

Métriques

Consultations de la notice

627

Téléchargements de fichiers

49