Les réseaux euclidiens

Un réseau euclidien est un objet mathématique qui a été utilisé premièrement pour la cryptanalyse. C'est Miklos Ajtai qui a démontré que les réseaux euclidiens peuvent servir de base solide pour la cryptologie. Certains caractéristiques remarquables des problèmes de réseaux sont qu'il n'y a pas d'instances faibles, ce qui ne va pas être le cas de RSA où avec certains nombres premiers la factorisation sera trop simple. De plus ces problèmes sont reconnu comme étant difficile. Il est donc pas possible de les résoudre efficacement. Et pour finir, on ne connaît pas d'attaque même avec un ordinateurs quantiques. Les cryptosystèmes qui se basent sur cet objet mathématique sont donc actuellement source de nombreuse études. En particularité pour la caractéristique homomorphe de ce chiffrement, c'est à dire qu'on peut effectuer des calculs directement sur le chiffré. Cela peut garantir la sécurité dans de nombreuses applications comme par exemple lors de calculs effectués sur les services cloud.

Les principes de base du réseau euclidien

Un réseau euclidien est "ensemble de points régulièrement répartis sur une dimension n" ou avec des termes plus mathématique il s'agit d'un sous-groupe discret d'un espace vectoriel euclidien.

Voici la représentation d'un réseau euclidien de dimension 2. Comme le nombre de points est infini il serait difficile de faire la liste de ces points. Ils sont donc représentés par une base, ici (O, u, v). Les points ont donc des coordonnées correspondant à la base de notre réseau euclidien.

Base différentes Un réseau euclidien peut être représenté par plusieurs bases (image ci-contre). Les différence avec le système de coordonnées du plan (0,x,y) c'est que dans un réseau euclidien les coordonnées sont toujours des entiers et la base n'est pas nécessairement rectangulaire.

Bonne ou mauvaise base ? Certaines bases vont être plus qualitative que d'autres. Une bonne base (base bleue) est presque rectangulaire alors qu'une mauvaise base (base rouge) est de forme quelconque. Ces typologies s'expliquent par la différence que l'on peut observer au niveau que de la couverture de l'espace autour de chaque point du réseau. //images

Application en cryptologie

Les réseaux euclidiens sont depuis peu appliqués en cryptologie, remarqués par la difficulté de ces problèmes à être résolus efficacement. Nous allons utiliser une bonne base comme clé privée et une mauvaise base comme clé publique. Pour représenter un message sur le réseau euclidien, il suffit de coder notre message en ternaire, les valeurs possibles sont 0,1,-1. Dans une dimension 8 le message OK correspondrait à m = 0 -1 -1 1 -1 0 -1 1.

	Caractère à coder	Code ternaire
	0	0	0	0
Titre ligne 2	Donnée 2A	Donnée 2B	Donnée 2C
Titre ligne 3	Donnée 3A	Donnée 3B	Donnée 3C

Caractère à coder	Code ternaire
	0 0 0 0
0	1 0 0 0
1	-1 0 0 0
2	0 1 0 0
3	1 1 0 0
4	-1 1 0 0
5	0 -1 0 0
6	1 -1 0 0
7	-1 -1 0 0
8	0 0 1 0
9	1 0 1 0
Etc ...

Le chiffrement

Pour le chiffrement nous utilisons la mauvaise base pour tirer un point aléatoire sur le réseau.

  def chiffre(Pub, m):
  d = tirage_reseau(Pub)
  m_chiffré = d + m
  return m_chiffré

Le déchiffrement

  def dechiffre(Secret, m_chiffré):
  d = Algorithme_de_Babai(Secret, m_chiffré)
  m = m_chiffré - d
  return m

Algorithme de Babai

C'est un mathématicien du nom de László Babai qui a inventé la meilleure solution pour retrouver le centre du pavé associé au message chiffré :

  Algorithme_de_Babai(B, m_chiffré){
     B_inv = inverse(B)
     v = m_chiffré * B_inv 
     w = vector([round(x) for x in v])
     d = B * w
     return d
  }

Dans cette exemple je partirai du principe que le message chiffré est sur 2 digits. De ce fait, les réseaux euclidiens seront de dimension 2, plus simple pour illustrer.

L'algorithme marche ainsi :

On renseigne la base sous forme de matrice où chaque colonne représente un vecteur de dimension. Cette base sera plus ou moins bonne en fonction de la clé (privée ou publique). On renseigne le message chiffré également sous forme de matrice à une colonne.

Bonne base (clé privée) :   ${\begin{pmatrix}3&-1\\-1&3\end{pmatrix}}$        Message chiffré :   ${\begin{pmatrix}13\\7\end{pmatrix}}$

Ensuite il s'agit de calculer l'inverse de la matrice B en appliquant la formule classique :

Formule :   $1/(ad-bc){\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}$        Résultat :   ${\begin{pmatrix}0.375&0.125\\0.125&0.375\end{pmatrix}}$

Il faut alors effectuer une multiplication matricielle avec B_inv et le message chiffré m_chiffre que l'on va arrondir ensuite:

Opération :   ${\begin{pmatrix}0.375&0.125\\0.125&0.375\end{pmatrix}}$ * ${\begin{pmatrix}13\\7\end{pmatrix}}$        Résultat arrondi :   ${\begin{pmatrix}6\\4\end{pmatrix}}$

Enfin, on rééffectue une multiplication matricielle avec B et notre resultat w:

Opération :   ${\begin{pmatrix}3&-1\\-1&3\end{pmatrix}}$ * ${\begin{pmatrix}6\\4\end{pmatrix}}$        Résultat arrondi :   ${\begin{pmatrix}14\\6\end{pmatrix}}$

Chiffrement homomorphe

Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans nécessité de d'accéder aux données sensibles en les déchiffrant. Pour toute opération Op et pour tout message m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite déchiffrer par D est équivalent au résultat de l'opération sur les deux messages clairs :

$D(Op(C(m1),C(m2))=Op(m1,m2)$

Prenons l'exemple d'Alice. Alice souhaite pouvoir effectuer des opérations sur deux données sensibles mais elle ne possède pas la puissance de calcul nécessaire pour l'effectuer. Elle souhaite donc demander à un organisme tiers de procéder aux calculs sur ses données. Cependant, les données à traiter sont sensibles et Alice ne fait pas confiance en cet organisme. Elle va donc une utiliser un chiffrement homomorphe et envoyer des données chiffrés à l'organisme qui pourra ainsi calculer et renvoyer le résultat, encore chiffré, à Alice. Alice pourra alors déchiffrer le message pour obtenir le résultat de l'opération sur ses données sensibles grâce aux propriétés du chiffrement homomorphe.

Chiffrement homomorphe et Cryptographie

Le chiffrement RSA, actuellement très utilisé, est considéré comme partiellement homomorphe. En effet, le chiffrement permet d'effectuer certaines opérations de manière homomorphe mais n'offre pas la possibilité d'effectuer l'ensemble des opérations existantes. Plus particulièrement, ce genre de chiffrement autorise soit la multiplication homomorphe soit l'addition homomorphe :

Multiplication homomorphe : $D(C(m1)*C(m2))=m1*m2$

En revanche, le chiffrement par réseaux euclidiens est dit complètement homomorphe et permet donc d'effectuer l'ensemble des opérations de manière homomorphe. Pour qu'un chiffrement soit complètement homomorphe, il faut pouvoir appliquer les opérations d'addition et de multiplication sur les données chiffrées :

Multiplication homomorphe : $D(C(m1)*C(m2))=m1*m2$ Addition homomorphe : $D(C(m1)+C(m2))=m1+m2$

On peut voir le XOR comme une addition modulo 2 et la propriété logique AND comme la multiplication modulo 2. Grace à ces deux portes logiques, il est possible d'exprimer tous les programmes et calculs existant. L'ensemble de ces deux opérations permettrai alors de pouvoir effectuer l'ensemble des opérations existantes avec un homomorphisme complet. C'st pourquoi le chiffrement par réseaux euclidiens est d'autant plus intéressant pour l'avenir de la cyber-sécurité.