Cryptanalyse de schémas multivariés et résolution du problème Isomorphisme de Polynômes
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Multivariate cryptography is a field of research where has appeared a rich family of cryptographic schemes based on hardness of the Multivariate Quadratic Problem which goal is the resolution of an average System of multivariate polynomials. Among those schemes are C*, SFLASH, HFE, UOV, etc. The purpose of this thesis is a presentation of recent works of cryptanalysis of some of these schemes. In a first part, common properties of those schemes are described and exploited, such as the fact that the differentials of the public coordinates hold a characteristic equation for conjugales of multiplications and one of the secret transformations. The main result is the resolution of the Isomorphism of Polynomial Problem related to the corresponding schemes. In a second part, a new analysis approach is presented, based on the computation of kernel of pencils of differentials derived from the polynomials of the public key, which leads for the SFLASH scheme to the direct recovery of the secret decomposition from merely three public coordinates and with a low polynomial complexity.
Abstract FR:
La cryptographie multivariée est un domaine de recherche dans lequel est apparue une riche famille de schémas fondés sur la difficulté du problème de résolution d'un système multivarié quadratique quelconque, appelé problème MQ (pour Multivariate Quadratic). Parmi ces schémas, on trouve C*, SFLASH, HFE, UOV, etc. L'objet de cette thèse est une présentation de travaux récents de cryptanalyse de certains de ces schémas. Une première partie décrit et exploite plusieurs propriétés communes à ces schémas, dont entre autres le fait qu'à partir des différentiels des coordonnées publiques des schémas, il est possible d'exprimer et de résoudre une équation caractéristique de transformations linéaires appelées multiplications, conjuguées par une des transformations secrètes du schéma. Le résultat principal est la résolution du problème IP (pour Isomorphisme de Polynômes) associé aux schémas considérés, ou autrement dit, le recouvrement d'une représentation équivalente de la décomposition secrète des schémas. Une deuxième partie aborde une nouvelle approche d'analyse fondée sur le calcul de noyaux de pinceaux de différentiels issus des représentations des clés publiques, qui dans le cas de SFLASH mène directement au recouvrement de la décomposition secrète, à partir de seulement trois coordonnées publiques et avec une complexité polynomiale faible.