Cryptographie multivariée

Le premier schéma de chiffrement de cette famille fut décrit par Tsutomu Matsumoto et Hideki Imai en 1988[1]. Bien que rapidement cryptanalysé[2], il inspira de nombreuses variantes dont HFE[3], dû à Jacques Patarin. Si HFE tel qu'initialement décrit est aujourd'hui considéré comme cassé[4] - [5] - [6] - [7] - [8] - [9], des variantes telles que UOV[10], HFE^v−[11] - [12], ou Rainbow[13] sont encore viables[14] - [15] - [16] - [17]. De même, le schéma de signature Sflash[18], proposé à la compétition NESSIE, est aujourd'hui complètement cassé[19] - [20].

Tous ces cryptosystèmes ont en commun que la clé publique est constituée d'un ensemble de polynômes multivariés, généralement des polynômes quadratiques pour des raisons d'efficacité algorithmique et de taille des clés.

On fixe un corps fini ${\displaystyle \mathbb {F} }$, la clé publique est donnée par un ensemble :

${\displaystyle G(x_{1},\dotsc ,x_{n})=\left(G_{1}(x_{1},\dotsc ,x_{n}),\dotsc ,G_{m}(x_{1},\dotsc ,x_{n})\right)}$

où chaque ${\displaystyle G_{i}\in \mathbb {F} [x_{1},\dotsc ,x_{n}]}$. Un message clair correspond à une suite ${\displaystyle M=(m_{1},\dotsc ,m_{n})\in \mathbb {F} ^{n}}$, et le chiffrement consiste simplement à évaluer chaque polynôme de la clé publique en ce point:

${\displaystyle C=G(M)=\left(G_{1}(M),\dotsc ,G_{m}(M)\right).}$

On voit ici apparaître un des intérêts de cette famille de techniques cryptographiques : l'évaluation polynomiale est calculatoirement très efficace (et même, dans une certaine mesure, parallélisable), ce qui permet un chiffrement relativement très rapide. Jusqu'ici la description ci-dessus s'applique à tous les procédés de chiffrement multivariés.

Pour déchiffrer, il faut posséder comme clé secrète un moyen d'inverser ${\displaystyle G}$, noté généralement ${\displaystyle G^{-1}}$. Ce moyen est spécifique au chiffrement multivarié considéré, et c'est souvent en étudiant la manière dont ${\displaystyle G}$ et son inverse sont choisis qu'une attaque a été découverte : en effet, il s'agit souvent d'une opération aisément inversible « masquée » par deux transformations, de manière tout à fait analogue à l'approche utilisée pour les chiffrements à base de codes, tels que le cryptosystème de McEliece, pour cacher le code.

Pour un ensemble de polynômes ${\displaystyle G}$ général (c'est-à-dire ne présentant pas de structure particulière exploitable par l'attaquant), le problème de l'inversion est prouvé NP-difficile. Supposant P ≠ NP il est donc conjecturé que même un ordinateur quantique ne peut résoudre ce problème efficacement. Comme les polynômes utilisés en cryptographie multivariée ne sont pas tout à fait aléatoires, mais sont choisis avec une structure cachée, l'argument de sécurité n'est toutefois qu'heuristique.

En calculant l'inverse ${\displaystyle G^{-1}(M)}$ au lieu de ${\displaystyle G(M)}$, on obtient un schéma de signature au lieu d'un schéma de chiffrement, où cette fois c'est la vérification publique de la signature qui est particulièrement efficace. Un des attraits de la cryptographie multivariée pour la génération de signatures est leur taille réduite comparée à d'autres approches.

Pour illustrer le fonctionnement sur un exemple simple (tiré du cryptosystème d'Imai-Matsumoto), on se place dans le corps ${\displaystyle \mathbb {F} =\mathbb {F} _{2^{2}}=\mathbb {F} _{2}[X]/(X^{2}+X+1)}$, qui possède 4 éléments ${\displaystyle 0,1,\alpha ,1+\alpha }$, que l'on va noter respectivement ${\displaystyle 0,1,2,3}$. Supposons la clé publique donnée par

${\displaystyle {\begin{aligned}G_{1}&=1+x_{2}+2x_{0}x_{2}+3x_{1}^{2}+3x_{1}x_{2}+x_{2}^{2}\\G_{2}&=1+3x_{0}+2x_{1}+x_{2}+x_{0}^{2}+x_{0}x_{1}+3x_{0}x_{2}+x_{1}^{2}\\G_{3}&=3x_{2}+x_{0}^{2}+3x_{1}^{2}+x_{1}x_{2}+3x_{2}^{2}\\\end{aligned}}}$

et le message ${\displaystyle M=(1,2,3)}$, alors on obtient le chiffré

${\displaystyle C=G(M)=(0,0,1)}$

Schémas de chiffrement :

• Hidden field equations (HFE), et ses variantes HFE⁺, HFE⁻, HFE^v, HFE^f, et HFE^v−.
• Unbalanced oil and vinegar (UOV)

Schémas de signature :

• Sflash
• Quartz[21]