Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Ressources d'apprentissage:
Cryptage entièrement homomorphe I : théorie et fondement (enseignant Yu Yu de l'université Jiao Tong de Shanghai)
Cryptage entièrement homomorphe II : Théorie et construction du cryptage entièrement homomorphe (Professeur Xiang Xie)

---

Désormais, les schémas de chiffrement entièrement homomorphes de deuxième génération (tels que BGV et BFV) et de troisième génération sont tous basés sur LWE. Désormais, les schémas entièrement homomorphes avancés sont également basés sur LWE, cet article résume donc les connaissances de base de LWE.
Considérons d’abord que nous voulons chiffrer un nombre$m$, utilisant désormais une série de${un}_{je}$droite$m$Chiffrez et obtenez${un}_{je}m$, en fait, il peut être résolu en résolvant le plus grand diviseur commun GCD$m$ .Cependant, si un bruit aléatoire est ajouté${etttttttt}_{je}$,obtenir${un}_{je}m+{etttttttt}_{je}$, alors ce sera difficile à résoudre$m$ valeur. Ce processus est ma simple compréhension de LWE. La soi-disant erreur est un bruit.

Le processus de calcul du chiffrement entièrement homomorphe est divisé en trois étapes : génération de clé KeyGen, chiffrement Enc, calcul homomorphe Eval et décryptage Dec. ,

Générateur de clés :

Construisez d’abord l’équation ci-dessus,$m\cdot UN+etttttttt=mUN+etttttttt$, puis récupérez la clé publique pk ($-UN$et$mUN+etttttttt$épissage), et la clé privée sk ($m$ et 1). On obtient donc que le résultat de la multiplication entre pk et sk est un bruit aléatoire e (proche de 0).

Enc：

La clé publique pk utilisée pour le chiffrement, r est un vecteur aléatoire contenant uniquement 0 ou 1, et m est l'information à chiffrer (mise dans le bit le plus bas du vecteur).

Déc:

Après avoir calculé le produit interne de la clé privée sk utilisée pour le décryptage et ct, recherchez le mod 2 pour obtenir le résultat du décryptage.

Preuve d'exactitude :

Multipliez sk et pk pour obtenir 2e (la condition remplie par KeyGen), puis faites le produit interne avec r pour obtenir un petit bruit pair, le résultat final est m+ un petit bruit pair, donc le bruit peut être éliminé par le mod 2. Obtenez le résultat du décryptage m. C'est pourquoi le bruit construit est 2e, pas e. Je crois comprendre qu'en construisant un bruit aléatoire pair, il est pratique d'utiliser le mod 2 pour éliminer le bruit pendant le décryptage.

Preuve de sécurité :

Lorsque pk est pseudo-aléatoire et que r a une entropie suffisamment élevée (c'est-à-dire que le caractère aléatoire est fort ?), pk et pk fois r sont pseudo-aléatoires. Après avoir ajouté les naturels et les vecteurs avec m, le résultat du cryptage est également pseudo-aléatoire.

Voici la description classique du professeur Xiang Xie :
Formule de cryptage : texte chiffré c = clé publique pk ✖️ r aléatoire + texte en clair m
Formule de décryptage : texte en clair m = <texte chiffré sk, clé privée sk> mod q mod 2

Sur cette base, le mod 2 peut être utilisé pour décrypter la valeur du texte en clair m. Tant que le bruit est suffisamment faible, la précision peut être garantie.
Il y a quelque chose qu'il faut distinguer ici : ce qui précède$PK=(UN,b=UN{m}^{\prime }+2etttttttt)$est la solution BGV, et BFV est$PK=(UN,b=UN{m}^{\prime }+etttttttt)$, la différence est que BGV code les informations en bits faibles, tandis que BFV code les messages en bits forts (cela sera expliqué lors de l'apprentissage de BFV).

Eval (homomorphisme additif et homomorphisme multiplicatif) :

Notez que l'addition ou la multiplication homomorphe entraînera une accumulation significative de bruit et que la multiplication a une tendance de croissance quadratique.
Parlons ensuite de la façon de déchiffrer le résultat de la multiplication homomorphe. Vous pouvez voir la formule suivante : La multiplication de deux textes chiffrés équivaut à faire le produit tensoriel du texte chiffré et de la clé privée respectivement, puis à faire le produit interne. Il est donc évident que le texte chiffré et la clé privée ont doublé de taille. L'exemple est une preuve d'équivalence.

La question est donc de savoir comment restaurer la taille du texte chiffré et la taille de la clé privée après une multiplication homomorphe ? C’est le problème que résout la commutation par clé.

Voici la description du professeur Xiang Xie :

Changement de clé

L’objectif est de restaurer la taille du texte chiffré et de la clé privée à une taille linéaire.

Trouvez maintenant la multiplication des textes chiffrés c1 et c2 :

Le processus ci-dessus est basé sur le concept de décomposition de bits :

Voici la description du professeur Xiang Xie :

Le but du Key Switching : convertir la clé privée$\tilde{m}$vers le bas$\tilde{c}$ Convertir en clé privée$m$vers le bas$c$,et$\tilde{c}$et$c$Ils sont tous chiffrés avec le même texte en clair.
Un concept central ici est Key Switching Key (KSK), ce qui signifie utiliser une clé privée$m$chiffrer$\tilde{m}$。

Grâce au processus de changement de clé, la clé privée peut être dérivée de$m\otimes m$est devenu linéaire$m$, en même temps, le texte chiffré passe de$\tilde{c}$est devenu linéaire$c$ .Et on peut voir sur la dernière ligne de formule qu'après le changement de clé$⟨c,m⟩$et l'original$⟨\tilde{c},m\otimes m⟩$Il y a une différence de bruit entre$2{\tilde{c}}^T\widetilde{etttttttt}$ , cette partie peut être très volumineuse ! Il n’y a donc toujours aucun moyen d’implémenter le Key Switching ici.

Une matrice Gadget G est introduite ici :

Par conséquent, le processus de changement de clé devient le suivant :

À ce stade, l’erreur ajoutée est très faible.
Pour résumer, via Key Switching, la clé privée d'origine$\tilde{m}=m\otimes m$vers le bas$\tilde{c}=c\otimes c$, est converti en clé privée$m$vers le bas$c$, faites attention à la clé après le changement de clé$m,c$Ce ne sont pas les valeurs d'origine (vérification).

Pour BGV, le bruit d'addition augmente linéairement et le bruit de multiplication augmente carrément. Bien que la commutation par clé puisse prendre en charge la multiplication (limitant sk à devenir extrêmement grand), le bruit est en fait un très petit bruit ajouté au bruit de multiplication d'origine. est également très grand. Ce bruit doit donc être encore réduit.

Réduction du module

À ce stade, les calculs de multiplication et d'addition homomorphes avec une faible profondeur ont été implémentés via LWE. La commutation de clé utilise une nouvelle clé pour chaque couche. Cependant, à mesure que la profondeur de calcul s'approfondit, l'expansion du bruit est explosive, elle n'est donc pas encore nivelée. . FHE (peut calculer FHE à une profondeur spécifiée).
Nous espérons maintenant implémenter un FHE capable de calculer une certaine profondeur sans utiliser le bootstrapping, ce qui nécessite une conversion modulo.

Je ne comprends pas très bien le processus au milieu. En bref, il s'agit de transformer le texte chiffré c du domaine modulo q au domaine modulo p (p<
Voici un exemple précis :
Si la réduction du module n'est pas effectuée, le bruit augmentera selon une tendance double exponentielle à mesure que la profondeur s'approfondit, et des erreurs de décryptage se produiront après le niveau >= 3.

Si la réduction du module est effectuée à chaque niveau, le bruit sera également maintenu dans une plage de valeurs absolues, au détriment d'une réduction continue du module.

Donc, si vous souhaitez mettre en œuvre un FHE nivelé, vous pouvez définir un module$B^d$, alors vous pouvez calculer une profondeur de$d$circuit (où$B$ est la limite supérieure du bruit du texte chiffré actualisé).Calculé$d$Après la profondeur, le module doit être réduit à$B$ , pour s'assurer qu'il n'y a pas d'erreur de décryptage pour le moment. BGV est un FHE nivelé.