PICSI

Algorithme à clé publique: SFLASH (multivariables)

SFLASH est un schéma de signature numérique appartenant à la famille de la cryptographie dite multivariée (ou multivariable), dû à J. Patarin, N. Courtois et L. Goubin [1]. Cette famille regroupe des algorithmes dont la sécurité repose sur la difficulté de résoudre des systèmes d'équations quadratiques, dont les inconnues appartiennent à de très petits corps finis (typiquement les corps à 2 ou 256 éléments) mais nombreuses. Leur petite taille permet des temps d'exécution très courts. Leur grand nombre permet une sécurité élevée. Cette voie de recherche, initiée par Matsumoto et Imaï en 1988 et popularisée par J. Patarin à la fin du siècle dernier est à l'heure actuelle en pleine effervescence. Une connexion étroite avec la cryptographie symétrique a été mise en évidence, notamment au travers des attaques dites algébriques.

Les opérations à effectuer sont, quand on les compare aux schémas reposant sur l'arithmétique, extrêmement rapides. Moins de soixante millisecondes suffisent à un microprocesseur standard de carte à puce pour produire une signature SFLASH. De plus la signature est remarquablement courte : 259 bits seulement. En revanche, la taille de la clé publique est très élevée (typiquement 120 kbit).

SFLASH possède trois versions, dont la plus légère a été cassée en 2002 par H. Gilbert et M. Minier [2]. Par défaut, le nom SFLASH réfère à la version v2, d'ailleurs la première chronologiquement, et labellisée en 1999 par le projet européen NESSIE [3]. Malheureusement cette version a aussi été cassée, sept ans plus tard [4]. En conséquence, l'algorithme n'est plus recommandable en l'état.





[1] J. Patarin, N. Courtois and L. Goubin. FLASH, a fast multivariate algorithm. In CT-RSA‘01, LNCS 2020, pages 297-307, Springer-Verlag, 2001.

[2] H. Gilbert and M. Minier. Cryptanalysis of SFLASH. In Proc. of Eurocrypt‘02, LNCS 2332, pages 288-298, Springer-Verlag, 2002.

[3] https://www.cosic.esat.kuleuven.be/nessie/

[4] V. Dubois, P.-A. Fouque, A. Shamir and J. Stern. Practical Cryptanalysis of SFLASH. 2006. To be published.