Cryptanalyse algèbrique pour la cryptographie post-quantum – POSTCRYPTUM

La cryptanalyse algébrique consiste à modéliser un système de chiffrement (ou toute méthode décrivant une attaque sur celui-ci) sous la forme d'équations polynomiales, amenant la sécurité de celui-ci à la difficulté de la résolution du système associé. Plus spécifiquement, le projet POSTCRYPTUM propose
d’étudier les schémas de chiffrement dont la modélisation permet de se ramener à un système d'équations booléennes. La cryptanalyse du schéma de chiffrement consiste à exhiber une solution satisfaisant l’ensemble des équations du système relevant alors d’un problème de décision bien connu :
le problème de la SATisfaisabilité logique (Problème SAT) . La résolution de tels systèmes relève de la classe des problèmes NP-Complets et constitue, sur le plan fondamental, un problème crucial s’inscrivant dans le champ de l’informatique théorique. La formulation d’un système de chiffrement en une
expression logique se fonde sur la correspondance entre la multiplication et le ET logique et entre l'addition et le XOR (relaxation faite de la propagation de la retenue). Ceci constitue le point de départ du projet POSTCRYPTUM, qui se propose de développer des algorithmes efficaces visant à étudier l’impact du
formalisme propositionnel, éventuellement hybridé à d’autres techniques de cryptanalyse, sur l’affaiblissement des schémas asymétriques proposés au NIST pour standardisation de la cryptographie post-quantum. POSTCRYPTUM propose notamment de concentrer ses efforts à l’étude de la sécurité des schémas de signature relevant de la cryptographie multivariée.