CRYPTO : Paco Azevedo Oliveira (LMV) : Quelques applications de la programmation linéaire à Dilithium
2025-04-14 11:00 - 12:00 (Europe/Paris) | Bâtiment Fermat, salle 4205
Dilithium est un algorithme de signature, réputé post-quantique, et récemment standardisé sous le nom ML-DSA par le NIST. Dû à sa sécurité et à ses performances, il est conseillé dans la plupart des cas d’usage.

Durant cet exposé je présente les idées principales derrières deux travaux, fait en collaboration avec Andersson Calle-Vierra, Benoît Cogliati et Louis Goubin qui permettent de mieux
comprendre la sécurité pratique de Dilithium.

Je montre qu’en introduisant une faute pendant la génération de la signature de Dilithium, on peut forcer la personne qui signe à fournir des signatures « incorrectes » qui donnent de l’information sur la clé secrète sous la forme d’inéquations sur ses coefficients.
On reformule ensuite le problème de retrouver la clé secrète à partir de signatures incorrectes en un problème de programmation linéaire.

Parmi les données de l’instance MLWE (A,t), qui est au cœur de la construction de Dilithium,
la partie la moins significative de t — dénotée par t_0 — n’est pas incluse dans la clé publique et est formellement considérée comme une partie de la clé secrète. Connaître t_0 n’a aucun impact sur la sécurité boîte noire de Dilithium, elle permet néanmoins de construire des attaques par canaux cachés beaucoup plus efficaces. J’explique les idées principales pour construire une attaque qui retrouve t0 à partir des signatures de Dilithium, la encore en détournant des outils de programmation linéaire.

Ces deux résultats utilisent des techniques de programmation linéaire plus ou moins détournées de leurs usages traditionnels, ce qui est plutôt rare pour de la cryptanalyse d’algorithmes à clé publique.
