M. Trimoska, S. Ionica, G. Dequen, ‘A SAT-based Approach for Index Calculus on Binary Elliptic Curves‘, Progress in cryptology – AFRICACRYPT, 2020

      Commentaires fermés sur M. Trimoska, S. Ionica, G. Dequen, ‘A SAT-based Approach for Index Calculus on Binary Elliptic Curves‘, Progress in cryptology – AFRICACRYPT, 2020
  • Lien
  • Résumé : La cryptanalyse logique, introduite pour la première fois par Massacci en 2000, constitue une alternative viable aux techniques courantes de cryptanalyse algébrique sur les champs booléens. Étant donné que les opérations xor sont au cœur de nombreux problèmes cryptographiques, les recherches récentes dans ce domaine se sont concentrées sur la gestion efficace des clauses xor. Dans cet article, nous étudions la résolution de l’étape de décomposition des points de la méthode du calcul d’indice pour les champs d’extension de degré premier, en utilisant des méthodes de résolution de problèmes de satisfaction de contraintes (SAT solving). Nous avons expérimenté avec différents solveurs SAT et avons choisi d’utiliser WDSat, un solveur dédié à ce problème spécifique. Nous avons étendu ce solveur en ajoutant une nouvelle technique de rupture de symétrie et en optimisant la complexité temporelle de l’étape de décomposition des points par un facteur de m! pour le polynôme de sommation th. Bien que la résolution asymptotique du problème de décomposition des points avec cette méthode ait une complexité temporelle exponentielle dans la dimension l de l’espace vectoriel définissant la base de facteurs, les temps d’exécution expérimentaux montrent que la technique de résolution SAT présentée est significativement plus rapide que les méthodes algébriques actuelles basées sur le calcul de bases de Gröbner. Pour les valeurs de l et n considérées dans les expériences, le solveur WDSat couplé à notre technique de rupture de symétrie est jusqu’à 300 fois plus rapide que l’implémentation F4 de Magma, et ce facteur augmente avec l et n.