Reynald Lercier

A. Joux et R. Lercier. The Function Field Sieve in the Medium Prime Case. Dans S. Vaudenay, editeur, Advances in Cryptology - EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006. Proceedings, volume 4004 de Lecture Notes in Computer Science, pages 254-270. Springer Berlin / Heidelberg, Mai 2006.

Dans cet article, nous étudions l'application de l'algorithme de crible dans les corps de fonctions algébriques pour calculer des logarithmes discrets dans des corps finis de la forme GF(qⁿ) quand q est une puissance de nombre premier de taille moyenne. Cette approche est une alternative à des résultats récents de Granger et Vercauteren pour calculer des logarithmes discrets dans des tores, utilisant une représentation efficace. Nous montrons que quand q n'est pas trop large, une variante très efficace du crible dans les corps de fonctions peut être mise en œuvre. De façon surprenante, avec cet algorithme, les calculs sont même plus faciles que pour des corps premiers ou de caractéristique deux. Nous montrons aussi que ce nouvel algorithme a des conséquences sur la sécurité de cryptosystèmes existants, tels que la cryptographie à base de tore dans T₃₀, des schémas de signature courtes en caractéristique trois et des cryptosystèmes basés sur des variétés abéliennes supersingulières. Mais par ailleurs, des cryptosystèmes mettant en œuvre des corps de plus grande caractéristique et des degrés d'extension plus petits, typiquement de degré au plus 6, tels que LUC, XTR ou tore de type T₆, ne sont pas touchés.

[ bib | preprint | publication ] Retour