Modification to Fully Homomorphic Modified Rivest Scheme

Ce document présente le schéma Rivest modifié entièrement homomorphe (FHMRS), identifie une faille de sécurité le concernant, et propose une modification (mFHMRS) pour y remédier.

L'essentiel

Voici une explication simple et imagée de ce document technique, traduite en français pour un public général.

Imaginez que vous voulez faire des calculs sur des données confidentielles (comme des dossiers médicaux ou des comptes bancaires) sans jamais les déverrouiller. C'est le défi du Calcul Homomorphe. Le document que vous avez partagé parle d'une nouvelle méthode pour y parvenir, appelée mFHMRS, qui corrige une faille de sécurité d'une méthode précédente.

Voici l'histoire, racontée comme une aventure de coffre-forts et de clés magiques.

1. Le Problème de départ : Le "Vieux Coffre-Fort" (FHMRS)

Imaginez un système de sécurité inventé par des chercheurs (le schéma FHMRS).

• Le concept : Pour protéger un message secret (disons un mot de passe), on le cache dans une grande boîte. Mais cette boîte est divisée en deux parties, comme un puzzle. Chaque partie est envoyée à un gardien différent.
• La magie : On peut additionner ou multiplier ces boîtes sans les ouvrir. Les gardiens font les calculs sur les morceaux, et à la fin, on peut reconstituer le résultat final. C'est comme si vous pouviez faire une addition sur deux pièces de monnaie enfermées dans des sacs opaques, sans jamais voir les pièces.
• La faille : Les auteurs ont découvert que ce vieux système avait un défaut majeur. Si un espion voyait le message original et sa version chiffrée (ce qu'on appelle une "attaque à texte clair connu"), il pouvait utiliser un outil mathématique (le plus grand commun diviseur) pour trouver le secret ultime : la clé maîtresse $u$.
  • L'analogie : C'est comme si un voleur, en voyant un gâteau entier et une part de gâteau, pouvait déduire la recette secrète du fournil. Une fois qu'il a la recette, il peut ouvrir tous les autres gâteaux.

2. La Solution : Le "Nouveau Système de Partage" (mFHMRS)

Pour réparer cette faille, les auteurs (Sona Alex et Bian Yang) ont créé une version améliorée : le mFHMRS.

Au lieu de diviser le secret en seulement deux morceaux (comme le vieux système), ils le divisent en beaucoup plus de morceaux (disons $N+S$ morceaux).

• L'analogie du Puzzle Géant :
  Imaginez que votre secret est une image.
  • Dans l'ancien système, on ne coupait l'image qu'en 2 pièces. Si quelqu'un avait l'image originale et une pièce, il pouvait deviner comment l'autre pièce était coupée.
  • Dans le nouveau système (mFHMRS), on coupe l'image en 10, 20 ou même 50 pièces différentes. Chaque pièce est envoyée à un gardien différent.

3. Comment ça marche maintenant ?

Voici les étapes clés de ce nouveau système, expliquées simplement :

A. La Préparation (CléGen)

Au lieu de choisir deux grands nombres secrets, le système en choisit une famille entière de nombres premiers secrets ($p_1, p_2, ..., p_n$) et un nombre secret spécial ($u$).

• L'image : C'est comme avoir une armée de gardiens, chacun avec sa propre serrure unique, au lieu de seulement deux gardiens.

B. Le Chiffrement (Encrypt)

Pour cacher un message, on l'additionne à un nombre aléatoire géant (multiplié par le secret $u$). Ensuite, on divise ce résultat par tous les nombres secrets de la famille et on garde les restes.

• L'image : Vous écrivez un message sur un papier, vous le mettez dans une machine qui le hache en 50 miettes différentes. Chaque miette est envoyée à un gardien différent. Aucune miette seule ne vous dit rien.

C. Les Calculs Magiques (Homomorphie)

C'est là que la magie opère. Les gardiens peuvent additionner ou multiplier leurs miettes entre eux.

• Si le gardien 1 a la miette A et le gardien 2 a la miette B, ils peuvent calculer "A + B" sans jamais savoir ce qu'est A ou B.
• Le résultat est une nouvelle miette qui correspond au résultat du calcul sur les messages originaux.

D. Le Déchiffrement (Decrypt)

Pour lire le résultat final, on rassemble toutes les miettes. Grâce à une astuce mathématique ancienne (le théorème des restes chinois), on peut reconstruire le message original à partir de toutes ces miettes.

• La sécurité : Même si un espion a quelques miettes et connaît le message original, il ne peut pas reconstituer les clés secrètes ($p$ et $u$) car il manque trop de pièces du puzzle. Les mathématiques deviennent trop complexes pour être résolues par un ordinateur classique.

4. Pourquoi c'est plus sûr ? (L'Analyse de Sécurité)

Les auteurs ont testé leur nouveau système contre trois types d'attaques :

1. L'attaque par force brute (Essayer toutes les clés) :
   Avec autant de gardiens et de clés secrètes, le nombre de combinaisons possibles est si énorme (plus que le nombre d'atomes dans l'univers) que même les superordinateurs mettraient des milliards d'années à trouver la bonne clé.

2. L'attaque par grille (Lattice Attack) :
   C'est une attaque mathématique très sophistiquée qui essaie de trouver des motifs cachés. Les auteurs ont prouvé que la taille des nombres qu'ils utilisent rend cette attaque impossible. C'est comme essayer de trouver une aiguille dans une botte de foin, sauf que la botte de foin est en feu et que l'aiguille change de forme à chaque seconde.

3. L'attaque par équations linéaires :
   Dans l'ancien système, un espion pouvait résoudre un système d'équations simples pour trouver la clé. Dans le nouveau système, les "bruits" (les nombres aléatoires ajoutés) sont si importants et les équations si complexes que l'espion ne peut pas distinguer le signal du bruit.

En résumé

Ce papier présente une réparation intelligente d'un système de cryptographie.

• Avant : On utilisait un système simple (2 clés) qui se faisait pirater facilement si on voyait un exemple de message.
• Après (mFHMRS) : On utilise un système complexe (beaucoup de clés, beaucoup de morceaux) qui rend le piratage mathématiquement impossible, même si l'espion voit des exemples de messages.

C'est comme passer d'une maison avec une seule serrure facile à crocheter, à une forteresse avec des centaines de portes, chacune nécessitant une clé différente, et où les clés changent de forme à chaque fois qu'on les touche.

Le but final ? Permettre aux hôpitaux, aux banques et aux gouvernements de faire des statistiques et des calculs sur des données sensibles sans jamais avoir à les dévoiler, garantissant ainsi une confidentialité totale.

Résumé technique

Voici un résumé technique détaillé du document « Modification to Fully Homomorphic Modified Rivest Scheme » (FHMRS), rédigé en français.

Titre de l'article

Modification du Schéma Rivest Modifié Fully Homomorphic (FHMRS) pour atténuer les failles de sécurité

1. Problématique

Le document aborde une vulnérabilité critique dans le schéma de chiffrement homomorphe complet (FHE) basé sur la clé symétrique, appelé FHMRS (Fully Homomorphic Modified Rivest Scheme), tel que présenté dans une publication antérieure [1].

• La faille : Le schéma FHMRS original est susceptible d'une attaque par texte clair connu (KPA - Known Plaintext Attack) lorsqu'il prend en charge l'homomorphisme multiplicatif.
• Mécanisme de l'attaque : Dans le schéma original, si l'attaquant possède des paires (texte clair, texte chiffré), il peut exploiter la structure du chiffrement. Le texte chiffré est calculé comme $c = (m + g \cdot u) \pmod p$ et $(m + g \cdot u) \pmod q$. Lorsque les paramètres de sécurité (taille des nombres premiers $p$ et $q$) sont mal dimensionnés par rapport à la taille du terme $g \cdot u$, la réduction modulaire n'affecte pas la valeur. L'attaquant peut alors calculer le PGCD (Plus Grand Commun Diviseur) de $(c_1 - m_1)$ et $(c_2 - m_2)$ pour révéler directement le paramètre secret $u$, compromettant ainsi tout le système.
• Conséquence : Une fois $u$ découvert, la sécurité du schéma est totalement brisée.

2. Méthodologie : Le Schéma mFHMRS

Pour résoudre ce problème, les auteurs proposent une version modifiée appelée mFHMRS (Modified FHMRS). La méthodologie repose sur trois piliers principaux :

A. Génération de Clés et Paramètres (KeyGen)

Au lieu d'utiliser deux nombres premiers ($p, q$), le schéma modifié utilise un ensemble de $N+S$ nombres premiers ($p_1, p_2, ..., p_{N+S}$) et un nombre premier secret $u$.

• Paramètres :
  • $N$ : Nombre de multiplications consécutives supportées.
  • $A$ : Nombre d'additions consécutives supportées.
  • $S$ : Un paramètre d'ajustement (nombre de parts supplémentaires) choisi pour garantir que la taille des bits de chaque $p_i$ ($l_{p_i}$) soit suffisamment grande pour résister aux attaques, tout en restant inférieure à la taille de $u$.
• Contraintes de taille : Les tailles des clés sont rigoureusement définies pour équilibrer la sécurité et la correction du déchiffrement. Par exemple, $l_{p_i}$ doit être supérieur à une fraction de la taille totale des données après opérations homomorphes, mais inférieur à $l_u$.

B. Chiffrement (Encrypt)

Le message $m_i$ est chiffré en utilisant le Théorème des Restes Chinois (CRT) sur plusieurs modules.

• Un nombre aléatoire $g_i$ est généré.
• Le texte chiffré est une tuple de $N+S$ parts : $c_i = (c_{i1}, c_{i2}, ..., c_{i(N+S)})$.
• Chaque part est calculée comme : $c_{ij} = (m_i + g_i \cdot u) \pmod{p_j}$.
• Différence clé : Contrairement au schéma original, la taille des $p_j$ est choisie de manière à ce que la réduction modulaire soit effective et que la valeur $(m_i + g_i \cdot u)$ ne soit pas directement récupérable via un PGCD simple, même avec des textes clairs connus.

C. Opérations Homomorphes

Le schéma conserve les propriétés homomorphes :

• Addition : Addition composante par composante des tuples de chiffrés.
• Multiplication : Multiplication composante par composante.
• Opérations constantes : Ajout ou multiplication par une constante scalaire sur chaque part.
• Aucune opération modulaire n'est effectuée lors des calculs homomorphes ; elle est reportée au moment du déchiffrement.

D. Déchiffrement (Decrypt)

Le déchiffrement utilise le CRT pour reconstruire la valeur entière $(m_i + g_i \cdot u)$ à partir des parts, puis applique une réduction modulaire par $u$ pour récupérer le message original $m_i$.

3. Contributions Clés

1. Identification de la faille KPA : Analyse formelle montrant comment le schéma FHMRS original échoue face à une attaque par texte clair connu en raison d'un mauvais dimensionnement des paramètres de réduction modulaire.
2. Conception du mFHMRS : Introduction d'un schéma à multiples parts (basé sur $N+S$ nombres premiers) qui empêche la récupération de $u$ via le PGCD, même si l'attaquant connaît les textes clairs et chiffrés.
3. Analyse de Sécurité Rigoureuse :
   • Attaques par force brute : Démonstration que la complexité est exponentielle par rapport à la taille des clés.
   • Attaques par réseau (Lattice-based) : Preuve que l'algorithme LLL (Lenstra-Lenstra-Lovász) ne peut pas trouver les vecteurs courts nécessaires pour révéler $u$ ou les $p_i$, grâce au choix spécifique des tailles de bits ($l_p, l_u, l_g$).
   • Attaques par équations linéaires : Démonstration que la résolution de systèmes d'équations linéaires pour retrouver $u$ et les $p_i$ est impossible car les termes d'erreur ($k_{ij}$) sont imprévisibles et dépendent de nombres aléatoires cryptographiques ($g_i$).
4. Conditions de Correction : Établissement de bornes mathématiques précises pour les tailles des paramètres ($l_p, l_u, l_g$) afin de garantir que le résultat des opérations homomorphes reste inférieur à $n$ (le produit des $p_i$) pour un déchiffrement correct.

4. Résultats

• Résistance aux attaques connues : Le schéma mFHMRS résiste aux attaques KPA, aux attaques par réseau (LLL) et aux attaques par résolution d'équations linéaires, à condition que les paramètres soient choisis selon les formules fournies (ex: $l_g \ge \lambda/4$, $l_u > l_p$).
• Complexité : Pour un paramètre de sécurité $\lambda = 128$ bits, avec $N=1$ multiplication et $A=20$ additions, la complexité d'une attaque par force brute est estimée à environ $2^{490}$ opérations, rendant l'attaque irréalisable.
• Taille des clés : Le schéma introduit une surcharge de taille (ciphertext expansion) due à l'utilisation de multiples parts ($N+S$), mais cela est nécessaire pour la sécurité. Par exemple, pour 14 multiplications, la taille du chiffré peut atteindre ~3420 bits.

5. Signification

Ce travail est significatif car il sauvegarde une approche de chiffrement homomorphe basé sur la clé symétrique (plus efficace que les schémas à clé publique pour certaines applications) qui était initialement considérée comme vulnérable.

• Il fournit un cadre théorique solide pour dimensionner les paramètres dans les schémas basés sur le CRT et les approximations de diviseurs communs.
• Il démontre que la sécurité des schémas FHE légers ne repose pas seulement sur la complexité des opérations, mais sur un équilibre précis entre la taille des modules de réduction et la taille des termes aléatoires.
• Le schéma mFHMRS offre une alternative viable pour des applications nécessitant des calculs sur données chiffrées avec une gestion de la complexité maîtrisée, tout en garantissant la confidentialité contre des adversaires disposant de paires texte clair/chiffré.