Ce résultat, publié sur le site de l’International association of cryptologic research et sur l’archive ouverte HAL sera présenté lors de la conférence internationale Eurocrypt 2014 qui se tiendra à Copenhague jusqu’au 15 mai et publié dans « Advances in cryptology. » Il permet d’ores et déjà de rejeter plusieurs systèmes cryptographiques supposés jusqu’alors offrir des garanties de sécurité suffisantes. Bien qu’encore théoriques, ces travaux devraient avoir des répercussions, notamment dans les applications cryptographiques des cartes à puces, des puces RFID etc.
Pour protéger la confidentialité de l’information, la cryptographie cherche à utiliser des problèmes mathématiques difficiles à résoudre, même pour les machines les plus puissantes et les algorithmes les plus sophistiqués.
La sécurité d’une variante du logarithme discret, réputé très difficile, a été battue en brèche par quatre chercheurs du CNRS, d’Inria et du Laboratoire d’informatique de Paris 6 (CNRS/UPMC) : Pierrick Gaudry, Răzvan Bărbulescu, Emmanuel Thomé et Antoine Joux.
L’algorithme conçu par ces chercheurs se démarque des meilleurs algorithmes connus jusqu’alors pour ce problème. D’une part il est significativement plus simple à expliquer et d’autre part sa complexité est bien meilleure : ceci signifie qu’il est à même de résoudre des problèmes de logarithmes discrets de plus en plus grands, en voyant son temps de calcul croître beaucoup plus modérément que par les algorithmes précédents. Le calcul de logarithmes discrets associé aux problèmes voulus difficiles pour les applications cryptographiques s’en trouve grandement facilité.
Résoudre cette variante du logarithme discret étant désormais à la portée des calculateurs actuels, il devient donc inenvisageable de reposer sur sa difficulté dans les applications cryptographiques. Ces travaux sont encore à un stade théorique et l’algorithme doit encore être affiné avant de pouvoir fournir une démonstration pratique de la faiblesse de cette variante du logarithme discret. Néanmoins, ces résultats ouvrent une faille dans la sécurité cryptographique et la voie à d’autres recherches. En effet, il pourrait être adapté afin de tester la solidité d’autres solutions cryptographiques.
