Cryptographie à clé publique

Cours 9

Julien Lavauzelle
Université Paris 8
Master 1 mathématiques et applications – parcours ACC
25/03/2024
 Séance précédente

Vu à la séance précédente :
– Introduction à la cryptographie post-quantique
– Réseaux euclidiens et problèmes difficiles associés
– Chiffrement NTRU
– LWE et chiffrement de Regev

Questions ?

1/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Aujourd’hui

1. Cryptographie fondée sur les systèmes polynomiaux

2. Chiffrement HFE

3. Signature UOV

2/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Plan

1. Cryptographie fondée sur les systèmes polynomiaux

2. Chiffrement HFE

3. Signature UOV

2/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le problème MQ

La cryptographie « multivariée » repose sur le problème de calculer des solutions de systèmes d’équations
polynomiales (de degré ≥ 2) à plusieurs variables.

3/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le problème MQ

La cryptographie « multivariée » repose sur le problème de calculer des solutions de systèmes d’équations
polynomiales (de degré ≥ 2) à plusieurs variables.
Le problème difficile sous-jacent est le problème MQ (pour multivariate quadratic : équations de degré 2). On le
présente ici dans les corps finis.

3/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le problème MQ

La cryptographie « multivariée » repose sur le problème de calculer des solutions de systèmes d’équations
polynomiales (de degré ≥ 2) à plusieurs variables.
Le problème difficile sous-jacent est le problème MQ (pour multivariate quadratic : équations de degré 2). On le
présente ici dans les corps finis.

Problème MQ (Multivariate Quadratic equations). Soit Fq un corps fini, et m, n ≥ 1 deux entiers.

Instance. Un système de m équations quadratiques à n inconnues x1 , x2 , . . . , xn :


 f1 (x1 , . . . , xn ) = u1

 n n n
.. .. où fk (x1 , . . . , xn ) = ∑ ∑ ai,j xi xj + ∑ bi xi + c
. .
i=1 j=1 |{z} i=1


 degré 2
fm (x1 , . . . , xn ) = um


But. Trouver x = (x1 , . . . , xn ) ∈ Fnq une solution du système.

3/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le problème MQ

La cryptographie « multivariée » repose sur le problème de calculer des solutions de systèmes d’équations
polynomiales (de degré ≥ 2) à plusieurs variables.
Le problème difficile sous-jacent est le problème MQ (pour multivariate quadratic : équations de degré 2). On le
présente ici dans les corps finis.

Problème MQ (Multivariate Quadratic equations). Soit Fq un corps fini, et m, n ≥ 1 deux entiers.

Instance. Un système de m équations quadratiques à n inconnues x1 , x2 , . . . , xn :


 f1 (x1 , . . . , xn ) = u1

 n n n
.. .. où fk (x1 , . . . , xn ) = ∑ ∑ ai,j xi xj + ∑ bi xi + c
. .
i=1 j=1 |{z} i=1


 degré 2
fm (x1 , . . . , xn ) = um


But. Trouver x = (x1 , . . . , xn ) ∈ Fnq une solution du système.

Théorème. Le problème MQ est NP-difficile sur tous les corps finis.

3/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Pour une application en cryptographie, il faut déduire du problème MQ une fonction à sens-unique et à trappe ?

4/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Pour une application en cryptographie, il faut déduire du problème MQ une fonction à sens-unique et à trappe ?

Fait. On sait résoudre efficacement des équations polynomiales à une variable sur un corps fini.

4/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Pour une application en cryptographie, il faut déduire du problème MQ une fonction à sens-unique et à trappe ?

Fait. On sait résoudre efficacement des équations polynomiales à une variable sur un corps fini.

Par exemple, algorithme de recherche de racines de Chien (Chien search), ou algorithmes de factorisation de
polynômes (algorithme de Berlekamp, de Cantor–Zassenhaus).
→ leur complexité est polynomiale en log q et en le degré du polynôme.

4/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Pour une application en cryptographie, il faut déduire du problème MQ une fonction à sens-unique et à trappe ?

Fait. On sait résoudre efficacement des équations polynomiales à une variable sur un corps fini.

Par exemple, algorithme de recherche de racines de Chien (Chien search), ou algorithmes de factorisation de
polynômes (algorithme de Berlekamp, de Cantor–Zassenhaus).
→ leur complexité est polynomiale en log q et en le degré du polynôme.

Idée. Pour créer un système d’équations polynomiales multivariées à trappe, on passe de 1 variable à m variables :

Procédé :
– on choisit une extension de corps finis Fqm /Fq ,
– pour tout polynôme f ∈ Fqm [x], l’équation f (x) = 0 (dans Fqm ) peut se décomposer comme m équations
polynomiales à m variables (dans Fq ).

4/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].
Pour tout x ∈ F8 , on a x = x0 + x1 ω + x2 ω 2 , avec xi ∈ F2 , donc on obtient :

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].
Pour tout x ∈ F8 , on a x = x0 + x1 ω + x2 ω 2 , avec xi ∈ F2 , donc on obtient :

f (x) = (x0 + x1 ω + x2 ω 2 )5 + (x0 + x1 ω + x2 ω 2 )2 + 1

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].
Pour tout x ∈ F8 , on a x = x0 + x1 ω + x2 ω 2 , avec xi ∈ F2 , donc on obtient :

f (x) = (x0 + x1 ω + x2 ω 2 )5 + (x0 + x1 ω + x2 ω 2 )2 + 1

= (x0 + x1 ω 4 + x2 ω 8 )(x0 + x1 ω + x2 ω 2 ) + (x0 + x1 ω 2 + x2 ω 4 ) + 1

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].
Pour tout x ∈ F8 , on a x = x0 + x1 ω + x2 ω 2 , avec xi ∈ F2 , donc on obtient :

f (x) = (x0 + x1 ω + x2 ω 2 )5 + (x0 + x1 ω + x2 ω 2 )2 + 1

= (x0 + x1 ω 4 + x2 ω 8 )(x0 + x1 ω + x2 ω 2 ) + (x0 + x1 ω 2 + x2 ω 4 ) + 1
= ... (des calculs) ...

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].
Pour tout x ∈ F8 , on a x = x0 + x1 ω + x2 ω 2 , avec xi ∈ F2 , donc on obtient :

f (x) = (x0 + x1 ω + x2 ω 2 )5 + (x0 + x1 ω + x2 ω 2 )2 + 1

= (x0 + x1 ω 4 + x2 ω 8 )(x0 + x1 ω + x2 ω 2 ) + (x0 + x1 ω 2 + x2 ω 4 ) + 1
= ... (des calculs) ...
= (x2 x1 + x1 + x2 + 1) + (x0 x2 + x1 )ω + (x0 x2 + x0 x1 + x2 )ω 2

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations : exemple

Exemple : soit q = 2 et m = 3. Le corps fini F8 = F2 [ω ] avec ω 3 = ω + 1.

On considère f (X) = X5 + X2 + 1 ∈ F8 [X].
Pour tout x ∈ F8 , on a x = x0 + x1 ω + x2 ω 2 , avec xi ∈ F2 , donc on obtient :

f (x) = (x0 + x1 ω + x2 ω 2 )5 + (x0 + x1 ω + x2 ω 2 )2 + 1

= (x0 + x1 ω 4 + x2 ω 8 )(x0 + x1 ω + x2 ω 2 ) + (x0 + x1 ω 2 + x2 ω 4 ) + 1
= ... (des calculs) ...
= (x2 x1 + x1 + x2 + 1) + (x0 x2 + x1 )ω + (x0 x2 + x0 x1 + x2 )ω 2

Ainsi, dans la base (1, ω, ω 2 ) de F8 /F2 , l’équation f (x) = 0 correspond à 3 équations :


 f0 (x) = x2 x1 + x1 + x2 + 1 = 0
f (x) = x0 x2 + x1 =0
 1
f2 (x) = x0 x2 + x0 x1 + x2 =0

5/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Remarque 1. Pour obtenir un système d’équations quadratiques sur Fq , on va choisir f sous une forme particulière :

6/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Remarque 1. Pour obtenir un système d’équations quadratiques sur Fq , on va choisir f sous une forme particulière :

m−1 m−1 m−1

i j i
f (x) = ∑ ∑ aij Xq +q + ∑ bi X q + c .
i=0 j=0 i=0

6/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Remarque 1. Pour obtenir un système d’équations quadratiques sur Fq , on va choisir f sous une forme particulière :

m−1 m−1 m−1

i j i
f (x) = ∑ ∑ aij Xq +q + ∑ bi X q + c .
i=0 j=0 i=0

i
En effet, comme x 7→ xq est Fq -linéaire, et vaut l’identité sur Fq , en décomposant sur une base Fqm /Fq , on obtient des
polynômes dont les termes sont de degré au plus 2.

6/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Remarque 1. Pour obtenir un système d’équations quadratiques sur Fq , on va choisir f sous une forme particulière :

m−1 m−1 m−1

i j i
f (x) = ∑ ∑ aij Xq +q + ∑ bi X q + c .
i=0 j=0 i=0

i
En effet, comme x 7→ xq est Fq -linéaire, et vaut l’identité sur Fq , en décomposant sur une base Fqm /Fq , on obtient des
polynômes dont les termes sont de degré au plus 2.

Remarque 2. Si l’on connaît la base Fqm /Fq qui a été choisie, on peut aisément appliquer la transformation

f (x) = 0 ←→ { fi ( x ) = 0 } 1 ≤ i ≤ m

6/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Déguiser des équations

Remarque 1. Pour obtenir un système d’équations quadratiques sur Fq , on va choisir f sous une forme particulière :

m−1 m−1 m−1

i j i
f (x) = ∑ ∑ aij Xq +q + ∑ bi X q + c .
i=0 j=0 i=0

i
En effet, comme x 7→ xq est Fq -linéaire, et vaut l’identité sur Fq , en décomposant sur une base Fqm /Fq , on obtient des
polynômes dont les termes sont de degré au plus 2.

Remarque 2. Si l’on connaît la base Fqm /Fq qui a été choisie, on peut aisément appliquer la transformation

f (x) = 0 ←→ { fi ( x ) = 0 } 1 ≤ i ≤ m

Idée pour la crypto : on va cacher cette base en appliquant des transformations affines sur les variables x et sur le
système final.

6/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Plan

1. Cryptographie fondée sur les systèmes polynomiaux

2. Chiffrement HFE

3. Signature UOV

6/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le système de chiffrement HFE : génération de clefs

J. Patarin introduit en 1996 le système de chiffrement HFE (hidden field equations).

7/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le système de chiffrement HFE : génération de clefs

J. Patarin introduit en 1996 le système de chiffrement HFE (hidden field equations).

Paramètres du système : une extension de corps fini Fqm /Fq et sa base associée.
HFE : GÉNÉRATION DE CLEFS

7/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le système de chiffrement HFE : génération de clefs

J. Patarin introduit en 1996 le système de chiffrement HFE (hidden field equations).

Paramètres du système : une extension de corps fini Fqm /Fq et sa base associée.
HFE : GÉNÉRATION DE CLEFS
1. Alice choisit aléatoirement un polynôme f (X) ∈ Fqm [X] de la forme
m−1 m−1 m−1
i j i
f (X ) = ∑ ∑ aij Xq +q + ∑ bi Xq + c .
i=0 j=0 i=0
et calcule les polynômes f1 (x1 , . . . , xm ), . . . , fm (x1 , . . . , xm ) ∈ Fq [x1 , . . . , xm ] associés.

7/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le système de chiffrement HFE : génération de clefs

J. Patarin introduit en 1996 le système de chiffrement HFE (hidden field equations).

Paramètres du système : une extension de corps fini Fqm /Fq et sa base associée.
HFE : GÉNÉRATION DE CLEFS
1. Alice choisit aléatoirement un polynôme f (X) ∈ Fqm [X] de la forme
m−1 m−1 m−1
i j i
f (X ) = ∑ ∑ aij Xq +q + ∑ bi Xq + c .
i=0 j=0 i=0
et calcule les polynômes f1 (x1 , . . . , xm ), . . . , fm (x1 , . . . , xm ) ∈ Fq [x1 , . . . , xm ] associés.
q → Fq
2. Alice choisit deux transformations affines inversibles R, S : Fm m

7/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le système de chiffrement HFE : génération de clefs

J. Patarin introduit en 1996 le système de chiffrement HFE (hidden field equations).

Paramètres du système : une extension de corps fini Fqm /Fq et sa base associée.
HFE : GÉNÉRATION DE CLEFS
1. Alice choisit aléatoirement un polynôme f (X) ∈ Fqm [X] de la forme
m−1 m−1 m−1
i j i
f (X ) = ∑ ∑ aij Xq +q + ∑ bi Xq + c .
i=0 j=0 i=0
et calcule les polynômes f1 (x1 , . . . , xm ), . . . , fm (x1 , . . . , xm ) ∈ Fq [x1 , . . . , xm ] associés.
q → Fq
2. Alice choisit deux transformations affines inversibles R, S : Fm m

3. Alice calcule
g1 (x) f1 (S · x)
   
 g2 (x)   f2 (S · x) 
 . = R· ..
   
 .. 

 . 
gm (x) fm ( S · x )

7/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Le système de chiffrement HFE : génération de clefs

J. Patarin introduit en 1996 le système de chiffrement HFE (hidden field equations).

Paramètres du système : une extension de corps fini Fqm /Fq et sa base associée.
HFE : GÉNÉRATION DE CLEFS
1. Alice choisit aléatoirement un polynôme f (X) ∈ Fqm [X] de la forme
m−1 m−1 m−1
i j i
f (X ) = ∑ ∑ aij Xq +q + ∑ bi Xq + c .
i=0 j=0 i=0
et calcule les polynômes f1 (x1 , . . . , xm ), . . . , fm (x1 , . . . , xm ) ∈ Fq [x1 , . . . , xm ] associés.
q → Fq
2. Alice choisit deux transformations affines inversibles R, S : Fm m

3. Alice calcule
g1 (x) f1 (S · x)
   
 g2 (x)   f2 (S · x) 
 . = R· ..
   
 .. 

 . 
gm (x) fm ( S · x )
4. Les clefs sont :
– clé privée : les transformations R et S et le polynôme f ∈ Fqm [x]
– clé publique : les polynômes gi (x) ∈ Fq [x1 , . . . , xm ].

7/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Chiffrement HFE : chiffrement et déchiffrement

L’espace des clairs est Fm

q , l’espace des chiffrés est aussi Fq .
m

8/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Chiffrement HFE : chiffrement et déchiffrement

L’espace des clairs est Fm

q , l’espace des chiffrés est aussi Fq .
m

HFE : CHIFFREMENT
Pour chiffrer un message a = (a1 , . . . , am ) ∈ Fm
q :
1. calculer y = (g1 (a), g2 (a), . . . , gm (a)),
2. retourner y.

8/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Chiffrement HFE : chiffrement et déchiffrement

L’espace des clairs est Fm

q , l’espace des chiffrés est aussi Fq .
m

HFE : CHIFFREMENT
Pour chiffrer un message a = (a1 , . . . , am ) ∈ Fm
q :
1. calculer y = (g1 (a), g2 (a), . . . , gm (a)),
2. retourner y.

HFE : DÉCHIFFREMENT
1. Calculer b = R−1 (y) ∈ Fm
q.
2. Calculer Z ⊂ Fqm , l’ensemble des solutions z de l’équation f (z) = b, où b ∈ Fqm est l’élément associé à b.
3. Calculer S−1 (Z ) et reconnaître le message a.

8/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Chiffrement HFE : chiffrement et déchiffrement

L’espace des clairs est Fm

q , l’espace des chiffrés est aussi Fq .
m

HFE : CHIFFREMENT
Pour chiffrer un message a = (a1 , . . . , am ) ∈ Fm
q :
1. calculer y = (g1 (a), g2 (a), . . . , gm (a)),
2. retourner y.

HFE : DÉCHIFFREMENT
1. Calculer b = R−1 (y) ∈ Fm
q.
2. Calculer Z ⊂ Fqm , l’ensemble des solutions z de l’équation f (z) = b, où b ∈ Fqm est l’élément associé à b.
3. Calculer S−1 (Z ) et reconnaître le message a.

Remarque. Pour reconnaître le message a parmi toutes les solutions, on peut y ajouter de la redondance, un haché, ou
encore utiliser un procédé de remplissage (padding).

8/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

Soit G(x) = (g1 (x), . . . , gm (x)) : Fm

q → Fq la clé publique.
m

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

Soit G(x) = (g1 (x), . . . , gm (x)) : Fm

q → Fq la clé publique.
m

Informellement, l’idée est de remarquer que la partie quadratique de G peut être modélisée comme une forme
quadratique, dont la matrice associée a un rang particulièrement faible.

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

Soit G(x) = (g1 (x), . . . , gm (x)) : Fm

q → Fq la clé publique.
m

Informellement, l’idée est de remarquer que la partie quadratique de G peut être modélisée comme une forme
quadratique, dont la matrice associée a un rang particulièrement faible.
On se ramène alors à une version d’un problème appelé MinRank (étant données des matrices M 1 , . . . , M n , trouver
une combinaison linéaire des matrices qui a faible rang).

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

Soit G(x) = (g1 (x), . . . , gm (x)) : Fm

q → Fq la clé publique.
m

Informellement, l’idée est de remarquer que la partie quadratique de G peut être modélisée comme une forme
quadratique, dont la matrice associée a un rang particulièrement faible.
On se ramène alors à une version d’un problème appelé MinRank (étant données des matrices M 1 , . . . , M n , trouver
une combinaison linéaire des matrices qui a faible rang).
Ce problème est NP-difficile, mais il s’avère que l’instance choisie pour HFE est facile, et résoluble par des
techniques de « relinéarisation » (des attaques par calcul de bases de Gröbner fonctionnent également).

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

Soit G(x) = (g1 (x), . . . , gm (x)) : Fm

q → Fq la clé publique.
m

Informellement, l’idée est de remarquer que la partie quadratique de G peut être modélisée comme une forme
quadratique, dont la matrice associée a un rang particulièrement faible.
On se ramène alors à une version d’un problème appelé MinRank (étant données des matrices M 1 , . . . , M n , trouver
une combinaison linéaire des matrices qui a faible rang).
Ce problème est NP-difficile, mais il s’avère que l’instance choisie pour HFE est facile, et résoluble par des
techniques de « relinéarisation » (des attaques par calcul de bases de Gröbner fonctionnent également).
Remarque. Des variantes de HFE (par exemple, multi-HFE, HFE− ,...) ont également été attaquées.

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 HFE : cryptanalyse

Le chiffrement HFE a été attaqué par Kipnis et Shamir, en 1999, qui retrouvent la clef privée à partir de la clé
publique en temps polynomial.

Cryptanalysis of the HFE Public Key Cryptosystem. A. Kipnis et A. Shamir. CRYPTO. 1999.

Soit G(x) = (g1 (x), . . . , gm (x)) : Fm

q → Fq la clé publique.
m

Informellement, l’idée est de remarquer que la partie quadratique de G peut être modélisée comme une forme
quadratique, dont la matrice associée a un rang particulièrement faible.
On se ramène alors à une version d’un problème appelé MinRank (étant données des matrices M 1 , . . . , M n , trouver
une combinaison linéaire des matrices qui a faible rang).
Ce problème est NP-difficile, mais il s’avère que l’instance choisie pour HFE est facile, et résoluble par des
techniques de « relinéarisation » (des attaques par calcul de bases de Gröbner fonctionnent également).
Remarque. Des variantes de HFE (par exemple, multi-HFE, HFE− ,...) ont également été attaquées.

Conclusion partielle. En général, peu de solutions pratiques de chiffrement à clef publique basées sur des systèmes
polynomiaux multivariés. En revanche, beaucoup de signatures numériques.

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Plan

1. Cryptographie fondée sur les systèmes polynomiaux

2. Chiffrement HFE

3. Signature UOV

9/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

On appelle
– x1 , . . . , xv les variables de type « vinaigre » (vinegar), et on note V := {1, . . . , v} ;
– xv+1 , . . . , xn les variables de type « huile » (oil), et on note O := {v + 1, . . . , n}.

10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

On appelle
– x1 , . . . , xv les variables de type « vinaigre » (vinegar), et on note V := {1, . . . , v} ;
– xv+1 , . . . , xn les variables de type « huile » (oil), et on note O := {v + 1, . . . , n}.
On note enfin x = (x1 , . . . , xv , xv+1 , . . . , xn ).

10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

On appelle
– x1 , . . . , xv les variables de type « vinaigre » (vinegar), et on note V := {1, . . . , v} ;
– xv+1 , . . . , xn les variables de type « huile » (oil), et on note O := {v + 1, . . . , n}.
On note enfin x = (x1 , . . . , xv , xv+1 , . . . , xn ).
Pour k ≥ v + 1, on définit un polynôme quadratique en les variables {xi }1≤i≤n :

∑ ∑ ∑
(k ) (k ) (k )
fk (x) = αi,j xi xj + β i,j xi xj + γi xi + η (k) .
i∈V,j∈O i,j∈V,i≤j i∈V ∪O

10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

On appelle
– x1 , . . . , xv les variables de type « vinaigre » (vinegar), et on note V := {1, . . . , v} ;
– xv+1 , . . . , xn les variables de type « huile » (oil), et on note O := {v + 1, . . . , n}.
On note enfin x = (x1 , . . . , xv , xv+1 , . . . , xn ).
Pour k ≥ v + 1, on définit un polynôme quadratique en les variables {xi }1≤i≤n :

∑ ∑ ∑
(k ) (k ) (k )
fk (x) = αi,j xi xj + β i,j xi xj + γi xi + η (k) .
i∈V,j∈O i,j∈V,i≤j i∈V ∪O

Remarque fondamentale. En temps polynomial en n, on peut calculer une application réciproque de :

F: Fnq → Foq
x = (x1 , . . . , xv , xv+1 , . . . , xn ) 7→ (fv+1 (x), . . . , fn (x))

10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

On appelle
– x1 , . . . , xv les variables de type « vinaigre » (vinegar), et on note V := {1, . . . , v} ;
– xv+1 , . . . , xn les variables de type « huile » (oil), et on note O := {v + 1, . . . , n}.
On note enfin x = (x1 , . . . , xv , xv+1 , . . . , xn ).
Pour k ≥ v + 1, on définit un polynôme quadratique en les variables {xi }1≤i≤n :

∑ ∑ ∑
(k ) (k ) (k )
fk (x) = αi,j xi xj + β i,j xi xj + γi xi + η (k) .
i∈V,j∈O i,j∈V,i≤j i∈V ∪O

Remarque fondamentale. En temps polynomial en n, on peut calculer une application réciproque de :

F: Fnq → Foq
x = (x1 , . . . , xv , xv+1 , . . . , xn ) 7→ (fv+1 (x), . . . , fn (x))

Comment ?

10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Principe oil and vinegar

Soit Fq un corps fini, q = 28 typiquement. Soit également v > o ≥ 1 avec n := v + o.

On appelle
– x1 , . . . , xv les variables de type « vinaigre » (vinegar), et on note V := {1, . . . , v} ;
– xv+1 , . . . , xn les variables de type « huile » (oil), et on note O := {v + 1, . . . , n}.
On note enfin x = (x1 , . . . , xv , xv+1 , . . . , xn ).
Pour k ≥ v + 1, on définit un polynôme quadratique en les variables {xi }1≤i≤n :

∑ ∑ ∑
(k ) (k ) (k )
fk (x) = αi,j xi xj + β i,j xi xj + γi xi + η (k) .
i∈V,j∈O i,j∈V,i≤j i∈V ∪O

Remarque fondamentale. En temps polynomial en n, on peut calculer une application réciproque de :

F: Fnq → Foq
x = (x1 , . . . , xv , xv+1 , . . . , xn ) 7→ (fv+1 (x), . . . , fn (x))

Comment ?
1. On choisit aléatoirement des valeurs x1 , x2 , . . . , xv , et en substituant dans les équations, on obtient un système
linéaire de o équations en o inconnues.
2. On essaie de l’inverser par élimination gaussienne.
3. Si cela ne fonctionne pas, on recommence.
10/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications
 La signature UOV : unbalanced oil and vinegar

La signature UOV (unbalanced oil and vinegar), par J. Patarin en 1997.

Remarque. « Unbalanced » = v > o.

11/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature UOV : unbalanced oil and vinegar

La signature UOV (unbalanced oil and vinegar), par J. Patarin en 1997.

Remarque. « Unbalanced » = v > o.
Intuition. Si on ne connaît pas quelles sont les variables « vinaigre » et « huile » (voire, si elles sont « mélangées »)
alors on ne peut pas inverser F.

11/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature UOV : unbalanced oil and vinegar

La signature UOV (unbalanced oil and vinegar), par J. Patarin en 1997.

Remarque. « Unbalanced » = v > o.
Intuition. Si on ne connaît pas quelles sont les variables « vinaigre » et « huile » (voire, si elles sont « mélangées »)
alors on ne peut pas inverser F.

UOV : GÉNÉRATION DE CLEFS

1. Alice choisit uniformément L1 : Foq → Foq et L2 : Fnq → Fnq deux applications affines inversibles.
2. Alice choisit uniformément F : Fnq → Foq comme précédemment :

∑ ∑ ∑
(k ) (k ) (k )
fk ( x ) = αi,j xi xj + β i,j xi xj + γi xi + η (k) .
i∈V,j∈O i,j∈V,i≤j i∈V ∪O

et
F: Fnq → Foq
x 7→ (fv+1 (x), . . . , fn (x))
3. La clé publique est P := L1 ◦ F ◦ L2 , la clé secrète est formée de L1 , L2 et F.

11/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature UOV : unbalanced oil and vinegar

On signe un message quelconque m ∈ {0, 1}∗ . La signature s est un élément de Fnq .

12/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature UOV : unbalanced oil and vinegar

On signe un message quelconque m ∈ {0, 1}∗ . La signature s est un élément de Fnq .

On se donne une fonction de hachage cryptographique H : {0, 1}∗ → Foq , connue de tous.

12/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature UOV : unbalanced oil and vinegar

On signe un message quelconque m ∈ {0, 1}∗ . La signature s est un élément de Fnq .

On se donne une fonction de hachage cryptographique H : {0, 1}∗ → Foq , connue de tous.

UOV : SIGNATURE
Alice souhaite signer m ∈ {0, 1}∗ .
1. Elle hache son message : h = H (m).
2. Elle calcule successivement z = L1−1 (h), z′ = F−1 (z) et , s = L2−1 (z′ ).
3. Elle retourne la signature s.

12/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature UOV : unbalanced oil and vinegar

On signe un message quelconque m ∈ {0, 1}∗ . La signature s est un élément de Fnq .

On se donne une fonction de hachage cryptographique H : {0, 1}∗ → Foq , connue de tous.

UOV : SIGNATURE
Alice souhaite signer m ∈ {0, 1}∗ .
1. Elle hache son message : h = H (m).
2. Elle calcule successivement z = L1−1 (h), z′ = F−1 (z) et , s = L2−1 (z′ ).
3. Elle retourne la signature s.

UOV : VÉRIFICATION
Bob souhaite vérifier si la signature s correspond au message m.
1. Bob calcule h = H (m)
2. Bob calcule P(s) (P est la clé publique), et compare le résultat avec h.
3. S’il y a égalité, la signature est acceptée. Sinon elle est rejetée.

12/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.
Notons par exemple :

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.
Notons par exemple :
– La résolution directe du problème MQ sous-jacent. Pour cela on utilise un calcul de bases de Gröbner par les
algorithmes F4 ou F5 de Faugère.

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.
Notons par exemple :
– La résolution directe du problème MQ sous-jacent. Pour cela on utilise un calcul de bases de Gröbner par les
algorithmes F4 ou F5 de Faugère.
– La recherche d’une combinaison linéaire de faible rang (sur Fq ) des applications coordonnées de P (clé publique).
C’est une version du problème MinRank, lui aussi résoluble par calcul de bases de Gröbner en temps
exponentiel.

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.
Notons par exemple :
– La résolution directe du problème MQ sous-jacent. Pour cela on utilise un calcul de bases de Gröbner par les
algorithmes F4 ou F5 de Faugère.
– La recherche d’une combinaison linéaire de faible rang (sur Fq ) des applications coordonnées de P (clé publique).
C’est une version du problème MinRank, lui aussi résoluble par calcul de bases de Gröbner en temps
exponentiel.
– Recherche brute des variables « huile ».

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.
Notons par exemple :
– La résolution directe du problème MQ sous-jacent. Pour cela on utilise un calcul de bases de Gröbner par les
algorithmes F4 ou F5 de Faugère.
– La recherche d’une combinaison linéaire de faible rang (sur Fq ) des applications coordonnées de P (clé publique).
C’est une version du problème MinRank, lui aussi résoluble par calcul de bases de Gröbner en temps
exponentiel.
– Recherche brute des variables « huile ».
– D’autres : réduction à des sous-corps, recherche de sous-espaces particuliers, etc.

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Sécurité de UOV

Informellement, la sécurité de UOV repose sur :

– le problème MQ,
– l’impossibilité de retrouver la décomposition P = L1 ◦ F ◦ L2 .

Des attaques exponentielles (mais efficaces pour les paramètres proposés) existent, ce qui implique de choisir des clés
très grandes.
Notons par exemple :
– La résolution directe du problème MQ sous-jacent. Pour cela on utilise un calcul de bases de Gröbner par les
algorithmes F4 ou F5 de Faugère.
– La recherche d’une combinaison linéaire de faible rang (sur Fq ) des applications coordonnées de P (clé publique).
C’est une version du problème MinRank, lui aussi résoluble par calcul de bases de Gröbner en temps
exponentiel.
– Recherche brute des variables « huile ».
– D’autres : réduction à des sous-corps, recherche de sous-espaces particuliers, etc.

Remarque. La version équilibrée (v = o) de UOV a été attaquée en temps polynomial par Kipnis et Shamir.

13/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature Rainbow

La signature Rainbow proposait une amélioration qui consiste à « empiler » m ≥ 2 couches de problèmes UOV.
Elle avait été proposée pour standardisation au NIST, avec le choix m = 3.
https://www.pqcrainbow.org
Tailles de clefs et signature :
sécurité (bits) 128 192 256
(q, v1 , v2 − v1 , v3 − v2 ) (16, 36, 32, 32) (256, 68, 32, 48) (256, 96, 36, 64)
clé publique 157.8 ko 861.3 ko 1.89 Mo
clé privée 101.2 ko 611.3 ko 1.38 Mo
taille de signature 66 o 164 o 204 o

14/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature Rainbow

La signature Rainbow proposait une amélioration qui consiste à « empiler » m ≥ 2 couches de problèmes UOV.
Elle avait été proposée pour standardisation au NIST, avec le choix m = 3.
https://www.pqcrainbow.org
Tailles de clefs et signature :
sécurité (bits) 128 192 256
(q, v1 , v2 − v1 , v3 − v2 ) (16, 36, 32, 32) (256, 68, 32, 48) (256, 96, 36, 64)
clé publique 157.8 ko 861.3 ko 1.89 Mo
clé privée 101.2 ko 611.3 ko 1.38 Mo
taille de signature 66 o 164 o 204 o

Attaque récente. Mais à la conférence CRYPTO en 2022, Beullens donne une attaque sur la clé d’une durée de
quelques jours.

14/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 La signature Rainbow

La signature Rainbow proposait une amélioration qui consiste à « empiler » m ≥ 2 couches de problèmes UOV.
Elle avait été proposée pour standardisation au NIST, avec le choix m = 3.
https://www.pqcrainbow.org
Tailles de clefs et signature :
sécurité (bits) 128 192 256
(q, v1 , v2 − v1 , v3 − v2 ) (16, 36, 32, 32) (256, 68, 32, 48) (256, 96, 36, 64)
clé publique 157.8 ko 861.3 ko 1.89 Mo
clé privée 101.2 ko 611.3 ko 1.38 Mo
taille de signature 66 o 164 o 204 o

Attaque récente. Mais à la conférence CRYPTO en 2022, Beullens donne une attaque sur la clé d’une durée de
quelques jours.

La signature UOV reste proposée comme candidate (dans de nombreuses versions) à la compétition du NIST.

14/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications

 Fin de la partie cours

Questions ?

15/15 J. Lavauzelle – Clé publique 9 – M1 mathématiques et applications