J'ai suivi le cours CS355 (Advanced Cryptography) à Stanford il y a quelque temps. Nous avons été formés par trois doctorants de Dan, Dima Kogan, Florian Tramer et Saba Eskandarian. Les trois enseignants-chercheurs ont chacun leurs caractéristiques propres et leurs orientations de recherche sont également très différentes. Dima se concentre sur la technologie de protection de la vie privée PIR (Private Information Retri), Florian se concentre sur la recherche sur le ML et la blockchain, et Saba se concentre sur la preuve de connaissance nulle.
Le cours CS355 couvre presque tout le contenu dans le domaine de la cryptographie de l'Antiquité à nos jours. De la première fonction unidirectionnelle (fonction unidirectionnelle), à l'équation elliptique (ECC) et au couplage, et enfin à certains MPC populaires, connaissance nulle, récupération d'informations privées (PIR), algorithme entièrement homomorphe, etc. . Comme le cours vient de se terminer il y a deux jours, j'ai organisé une série de notes alors que le contenu des connaissances était encore dans ma mémoire superficielle. Le contenu du cours est très intéressant, je partagerai le reste du contenu avec vous plus tard quand j'aurai le temps~
Dans ce numéro, nous parlerons du cryptage entièrement homomorphe (FHE) récemment populaire et de la technologie de cryptage basée sur treillis qui l'accompagne.
Qu'est-ce que le chiffrement entièrement homomorphe ?
Je pense que de nombreux amis ont entendu parler du nom de chiffrement entièrement homomorphe (FHE). Ces dernières années, de plus en plus de sujets ont été abordés concernant la protection de la vie privée, et une série de technologies d'application de cryptographie, notamment le cryptage homomorphe, ont également été largement popularisées.
Afin de mieux comprendre ce sujet, je voudrais présenter brièvement la définition du cryptage entièrement homomorphe.
Examen du système de cryptage
Avant de commencer, passons en revue le système de cryptage le plus traditionnel.
Nous savons tous que si vous souhaitez construire un système de cryptage, vous avez souvent besoin d’une clé. Grâce à cette clé, nous pouvons chiffrer les informations en clair en texte chiffré à une extrémité, puis utiliser la clé pour rétablir le texte chiffré dans son apparence d'origine à l'autre extrémité. Sans cette clé, il serait difficile pour d'autres personnes de savoir quelles informations nous avons transmises.
L’illustration ci-dessus montre essentiellement une vue d’ensemble de tous les systèmes de cryptage courants. Tous les systèmes de cryptage, si l’on utilise une méthode de description plus formelle, font sans aucun doute trois choses :
Les amis qui connaissent quelque chose sur les algorithmes de cryptage connaîtront certainement les plus courants. Certains algorithmes de cryptage, tels que AES, RSA, etc. Chacun doit également savoir que de manière générale, les systèmes de chiffrement se divisent en deux types : les systèmes de chiffrement symétriques et les systèmes de chiffrement asymétriques. Les trois étapes que nous décrivons ici sont en réalité applicables à n’importe quel système de cryptage. S'il est symétrique, alors la clé utilisée pour le chiffrement et le déchiffrement est la même. S'il s'agit d'un système asymétrique, la clé publique est utilisée pour le chiffrement et une clé privée différente est utilisée pour le déchiffrement.
Dans la recherche en cryptographie, chaque fois que nous voyons la définition d’un nouveau système, nous devons souvent énoncer les propriétés que le système devrait avoir.
La principale signification de la sécurité sémantique est qu’un observateur ne peut pas faire la distinction entre deux messages cryptés. Ainsi, si un intrus écoute le réseau et voit les informations cryptées que j'envoie, tant que le système de cryptage que j'utilise est sémantiquement sécurisé, je peux être sûr que l'intrus ne peut obtenir aucune information sur le contenu crypté à partir du texte chiffré.
Après avoir satisfait aux deux propriétés ci-dessus, un système de cryptage devient fiable.
Après avoir compris en quoi consiste le système de cryptage, nous pouvons prêter attention à ce texte chiffré qui ressemble à un code tronqué généré aléatoirement. Nous savons tous que nous n’obtiendrons aucune information simplement en regardant le texte chiffré lui-même. Mais cela signifie-t-il que s’il n’y a pas de clé et seulement un texte chiffré, nous ne pouvons rien faire ?
Nous connaissons tous la réponse : pas vraiment.
Pour cette propriété, nous l’appelons homomorphisme additif. Cela signifie que le texte chiffré entretient une relation algébrique subtile avec le texte original précédent. Si nous additionnons le texte chiffré, nous pouvons obtenir le nouveau texte chiffré en additionnant le texte original. De la même manière, on peut conclure qu’il existe également des algorithmes de chiffrement homomorphes additifs. Nous pouvons multiplier le texte chiffré généré par un algorithme homomorphique multiplicatif, puis obtenir le texte chiffré correspondant au résultat de la multiplication des textes originaux. Dans l'ensemble du processus, nous n'avons besoin de connaître aucune information relative à la clé, nous combinons simplement le texte chiffré qui ressemble à un code tronqué aléatoire.
Par exemple : Système de vote anonyme
Donnons ensuite un exemple pour décrire de manière vivante l’aspect pratique du cryptage homomorphe.
Nous savons tous à quoi ressemble le vote en ligne : si le patron d'une entreprise souhaite lancer une vague de vote, il doit choisir si l'entreprise doit adopter le système 996. Le patron peut ensuite demander au service informatique de configurer un serveur et de laisser les employés soumettre leurs choix : votez 0 pour signifier qu'ils ne veulent pas, et votez 1 pour signifier qu'ils veulent. Après la période de vote finale, le patron peut additionner tous les votes. Si le total final de tous les votes dépasse la moitié du nombre d’employés, l’entreprise en démarrera 996.
Ce mécanisme de vote semble très simple, mais il y a un gros problème de confidentialité : si le patron veut que tous les employés soient au nombre de 996, mais qu'il initie délibérément ce vote pour pêcher les forces de l'ordre pour voir quel employé ne veut pas faire d'heures supplémentaires, alors le patron peut tranquillement Il a confié à son jeune frère d'écouter Internet, d'enregistrer les choix soumis par chaque employé et enfin de voir qui a voté 0. Résultat : les salariés ont très peur et n’osent pas exprimer leurs sentiments.
Si nous pouvons utiliser un algorithme de chiffrement homomorphe additif, ce problème peut être facilement résolu.
Bien entendu, ce système est encore très incomplet : le service informatique peut par exemple aider directement le patron à décrypter les votes de chacun et à les enregistrer dans un document. Il existe d'autres outils cryptographiques qui peuvent nous aider à résoudre ce problème. Pour des raisons de place, aucune autre explication ne sera donnée ici.
Mais à ce stade, nous devrions pouvoir ressentir la puissance de l’algorithme de chiffrement homomorphe. Nous pouvons le comprendre ainsi : grâce à l'algorithme de chiffrement homomorphique, les utilisateurs peuvent effectuer une sorte de calcul proxy sécurisé (Secure Delegated Computation) avec un serveur distant (cloud) non fiable. Les utilisateurs peuvent utiliser la technologie de cryptage homomorphe pour crypter leurs entrées privées sensibles et les confier au cloud. Le cloud peut ensuite effectuer un certain degré de calcul sur les données cryptées, et enfin obtenir le résultat crypté souhaité par l'utilisateur et le renvoyer au utilisateur. Enfin, l'utilisateur peut utiliser la clé de déchiffrement pour ouvrir le résultat. Pendant toute la durée de l'accord, le délégataire (le cloud) n'est jamais en mesure de voir aucune information utile liée aux entrées privées.
### Classification des systèmes de chiffrement homomorphes
Après avoir compris grossièrement les deux propriétés homomorphes les plus fondamentales, d’autres concepts deviennent très faciles à comprendre. D'un point de vue systématique, les systèmes de chiffrement homomorphes sont grossièrement divisés en quatre catégories : l'homomorphisme partiel, l'homomorphisme approximatif, l'homomorphisme complet en séries finies et l'homomorphisme complet.
Examinons ensuite tour à tour les définitions spécifiques de chaque catégorie.
Cryptage partiellement homomorphe
L'étape la plus élémentaire du chiffrement homomorphe est appelée chiffrement partiellement homomorphe, défini comme le texte chiffré n'ayant qu'une seule propriété homomorphe. Cette étape comprend les deux modes d'homomorphisme additif et d'homomorphisme multiplicatif que nous avons décrits ci-dessus.
On obtient le texte chiffré correspondant à la multiplication de ces deux messages ! C'est la propriété d'homomorphisme multiplicatif. Nous pouvons continuer à superposer de nouveaux textes chiffrés sur ce texte chiffré, afin d'obtenir n'importe quelle multiplication entre textes chiffrés.
Cryptage homomorphe approximatif (cryptage quelque peu homomorphe)
Comme nous l'avons dit dans le paragraphe précédent, si l'on veut multiplier les entrées privées et obtenir une combinaison linéaire entre elles, un simple algorithme de chiffrement partiellement homomorphe (RSA, ElGamal) ne peut pas être complété. Il nous faut donc passer à l'étape suivante.
La prochaine étape du chiffrement partiellement homomorphe est le chiffrement approximativement homomorphique, qui est un pas de plus vers le chiffrement entièrement homomorphe que nous souhaitons atteindre. Si nous disposons d’un algorithme de chiffrement approximativement homomorphe, nous pouvons alors calculer simultanément l’addition et la multiplication sur le texte chiffré. Cependant, il convient de noter que cette étape étant approximativement homomorphe (quelque peu homomorphe), le nombre d'additions et de multiplications pouvant être effectuées est très limité et la fonction F pouvant être calculée se situe également dans une plage limitée.
Il n'existe pas beaucoup d'exemples courants de chiffrement approximativement homomorphe à ce stade. Si l'on dit l'exemple le mieux compris, il devrait s'agir de l'algorithme de chiffrement de groupe cyclique basé sur l'appariement.
Ci-dessus, nous avons brièvement discuté de l'algorithme de chiffrement ElGamal basé sur des groupes cycliques ordinaires. Nous savons tous que cet algorithme est additivement homomorphe, ce qui signifie qu’il peut obtenir des combinaisons linéaires entre des textes chiffrés arbitraires. En fait, dans certains groupes cycliques spéciaux, nous pouvons également trouver de faibles propriétés d’homomorphisme multiplicatif.
Cette limitation prouve que le système est approximativement homomorphe, puisque nous ne pouvons pas calculer la fonction F de logique et de profondeur arbitraires.
Cryptage homomorphe entièrement nivelé
Après avoir atteint l’étape suivante, nous nous rapprochons de l’objectif de l’homomorphisme complet.
Cette étape est appelée chiffrement entièrement homomorphe en séries finies. A ce stade, nous pouvons déjà effectuer n'importe quelle combinaison d'addition et de multiplication sur le texte chiffré sans aucune limitation quant au nombre de fois.
Cryptage entièrement homomorphe (FHE)
Après de nombreux appels, nous arrivons enfin au cryptage entièrement homomorphe (FHE) que nous attendons de voir.
Comme son nom l'indique, un système de cryptage entièrement homomorphe n'a aucune restriction sur les méthodes de calcul. Nous pouvons arbitrairement combiner des textes chiffrés pour former de nouveaux textes chiffrés sans clé, et le nouveau texte chiffré, quelle que soit la complexité informatique, peut être parfaitement restauré au texte original.
Lorsque nous atteignons ce stade, le calcul d’agent sûr mentionné précédemment devient réalisable. Si nous pouvons trouver un système de cryptage entièrement homomorphique plus efficace, nous pouvons transférer en toute sécurité tous les calculs locaux vers le cloud sans fuite de données !
Définition d'un système de chiffrement entièrement homomorphe
Avant de commencer la discussion sur l’histoire des systèmes entièrement homomorphes ci-dessous, nous pouvons définir systématiquement la définition formelle des systèmes entièrement homomorphes. Un système de chiffrement entièrement homomorphe comporte un total de quatre algorithmes :
## Revue historique du chiffrement entièrement homomorphe
Avant de commencer à apprendre comment l’algorithme de chiffrement entièrement homomorphe est implémenté, autant examiner comment est né le concept de chiffrement entièrement homomorphe.
Le concept de FHE (entièrement homomorphique) a été proposé à la fin des années 1970. En 1978, Rivest, Adleman et Dertouzos, plusieurs grands noms de la cryptographie, évoquent pour la première fois dans leur article On Data Banks and Privacy Homomorphisms l'idée d'un système capable d'effectuer certains calculs sur le texte chiffré et d'opérer indirectement sur le texte original. Plus tard, cette idée a été résumée à nouveau et nommée chiffrement entièrement homomorphe.
On constate que le concept de chiffrement totalement homomorphe est proposé depuis longtemps. Étonnamment, en 1976, deux ans avant la publication de l’article, le protocole d’échange de clés Diffle-Hellman venait d’être proposé ! Cela montre que l’imagination des experts en cryptographie est encore très riche.
Lorsque le concept de FHE a été proposé, l’ensemble de la communauté universitaire a été ému et a entamé une recherche de plusieurs décennies pour tenter de trouver un algorithme parfait doté de propriétés entièrement homomorphes. Mais au cours des dernières décennies, les gens ont essayé toutes les options imaginables, mais ils n’ont pas trouvé une option qui satisfasse à toutes les conditions pour être pleinement homomorphe et dont la sécurité puisse être facilement prouvée.
Jusqu'en 2009, le docteur Craig Gentry, qui étudiait à Stanford, a soudainement eu une idée et a surmonté les difficultés de l'algorithme FHE. Dans sa thèse de doctorat, il a présenté pour la première fois un système de cryptage entièrement homomorphe raisonnable et sécurisé ! Ce système est basé sur l’hypothèse d’un réseau idéal. Le système entièrement homomorphe proposé par Gentry09 est souvent appelé système de cryptage entièrement homomorphe de première génération.
Dans l'article de Gentry, il mentionne également un concept crucial appelé Bootstrapping. Le bootstrapping est une technique de traitement spéciale pour le texte chiffré. Après traitement, il peut « rafraîchir » un texte chiffré avec un bruit proche de la valeur critique en un nouveau texte chiffré avec un bruit très faible. Grâce au Bootstrapping, le bruit d'un système en série finie ne peut jamais dépasser la valeur critique, devenant ainsi un système entièrement homomorphe. De cette façon, nous pouvons calculer homomorphiquement F de n’importe quelle taille.
Après la percée majeure de Gentry, l'ensemble du cercle de la cryptographie est retombé dans la folie et tout le monde a commencé à se démener pour trouver un système entièrement homomorphe plus efficace et polyvalent basé sur les idées proposées par Gentry.
En 2011, deux grands noms, Brakerski et Vaikuntanathan, ont proposé un nouveau système de chiffrement entièrement homomorphe, basé sur l'apprentissage avec erreurs (LWE), une autre hypothèse du chiffrement sur réseau. La même année, Brakerski, Gentry et Vaikuntanathan complètent le système et le publient officiellement. Le système entièrement homomorphe qu’ils ont inventé est appelé en abrégé le système BGV. Le système BGV est un système de chiffrement homomorphe de niveau limité, mais il peut être transformé en un système entièrement homomorphe grâce au Bootstrapping. Comparé au système proposé par Gentry09, le système BGV utilise une hypothèse LWE plus réaliste. De manière générale, nous appelons le système BGV le système de cryptage entièrement homomorphe de deuxième génération.
En 2013, Gentry fait son grand retour. Gentry, Sahai et Waters ont lancé un nouveau système de cryptage GSW entièrement homomorphe. Le système GSW est similaire au BGV dans la mesure où il possède des propriétés entièrement homomorphes en séries finies. Il est basé sur l'hypothèse LWE plus simple et peut être entièrement homomorphe grâce au bootstrapping. Nous désignons généralement le système GSW comme le système de cryptage entièrement homomorphe de troisième génération.
Après 2013, la cryptosphère a pratiquement prospéré. Basés sur le système original entièrement homomorphe de trois générations, diverses nouvelles conceptions ont vu le jour, dédiées à l'optimisation et à l'accélération de l'efficacité opérationnelle des systèmes BGV et GSW. IBM a développé une bibliothèque informatique open source entièrement homomorphe HElib basée sur le système BGV et l'a transplantée avec succès sur les principales plates-formes mobiles. Parallèlement, il existe un autre projet open source TFHE qui mérite également d'être noté. TFHE est basé sur le système GSW, avec diverses optimisations et accélérations ajoutées, et il est désormais très célèbre.
En plus de développer des bibliothèques traditionnelles entièrement homomorphes, de nombreuses équipes étudient également comment mieux accélérer le calcul d'algorithmes de chiffrement entièrement homomorphes via du matériel hétérogène tel que GPU, FPGA et ASIC. Par exemple, cuFHE est un système de chiffrement entièrement homomorphe accéléré par GPU basé sur CUDA.
Du point de vue actuel, cela fait 11 ans que Gentry a frappé à la porte du système entièrement homomorphe. De nos jours, la recherche sur le FHE est en plein essor dans l'industrie, et de nombreuses personnes étudient les systèmes entièrement homomorphes sous différents angles et exigences d'application. Jusqu'à aujourd'hui, nous disposons déjà d'une variété de méthodes réalisables de mise en œuvre du FHE, mais ce que tout le monde recherche toujours, c'est l'efficacité du fonctionnement du système FHE. En prenant comme exemple la bibliothèque FHE de pointe actuelle, le calcul homomorphique d'une logique relativement simple sur une plate-forme mobile peut prendre aussi peu que des dizaines de millisecondes et jusqu'à des dizaines de secondes. Ces unités de temps sont extrêmement lentes pour les systèmes informatiques.
Comment rendre le système FHE plus efficace sur des plates-formes hétérogènes reste un mystère non résolu. Si ce problème est une fois résolu, la conversion de tous les calculs informatiques en calculs entièrement homomorphes et le fait que des agents effectuent des calculs sur des cloud tiers seront un avenir facile.
La relation entre FHE et MPC
Avant de terminer l'article, je voudrais ajouter quelques mots sur la relation entre FHE et MPC. MPC signifie Secure Multi-Party Computation, qui est un calcul multipartite fiable. Cela signifie généralement que plusieurs parties ont leurs propres entrées privées et ne souhaitent pas les divulguer à d'autres, mais qu'elles souhaitent utiliser leurs propres entrées pour calculer ensemble une fonction F et partager les résultats du calcul.
Le MPC est en fait un domaine très connu et étudié depuis longtemps. Depuis que le cryptographe Yao Qizhi a lancé ses circuits garbled au siècle dernier, le domaine du MPC a acquis une large reconnaissance et de nombreuses percées ont été réalisées. Nous disposons désormais déjà de nombreuses bibliothèques MPC pouvant être utilisées, et elles ont également une certaine efficacité de fonctionnement.
Les amis qui connaissent MPC peuvent avoir de nombreuses questions après avoir vu l'histoire difficile des systèmes de chiffrement entièrement homomorphes : Pourquoi le chiffrement entièrement homomorphe ne peut-il pas être remplacé directement par un protocole MPC ?
En effet, un protocole MPC peut remplacer complètement un protocole FHE. Il suffit d'utiliser l'utilisateur et l'entrée privée en tant que partie dans un protocole, puis d'utiliser le serveur informatique proxy distant comme autre partie, qui remplit les conditions d'exécution du protocole MPC. Ce n'est que par certaines interactions que l'informatique proxy peut être réalisé. Et le serveur ne peut pas voir les entrées privées.
Mais il y a un point très important que nous avons négligé : puisque MPC est interactif, l'utilisateur et le serveur doivent calculer et communiquer ensemble pour compléter le protocole. Cela entre en conflit avec l’exigence la plus fondamentale du calcul des agents FHE. Si l'utilisateur doit rester en ligne tout le temps pour conclure l'accord et également payer une partie de la puissance de calcul, alors en fait le calcul n'est pas du tout « proxy » et les deux parties ne font que plus de calculs pour des raisons de sécurité des informations. . Cela explique également pourquoi le domaine du MPC a réalisé des avancées majeures, mais le domaine du FHE est encore inconnu, car les deux systèmes résolvent des problèmes complètement différents.
## Prochain arrêt : système de chiffrement GSW entièrement homomorphe
Voyant cela, chacun doit avoir une compréhension très approfondie du système de cryptage entièrement homomorphe.
Prochain arrêt, nous pourrons en apprendre davantage sur le système de cryptage entièrement homomorphe GSW mentionné ci-dessus. Bien qu'il s'agisse de la troisième génération de systèmes entièrement homomorphes, je pense que parmi les trois systèmes Gentry09, BGV et GSW, GSW est celui avec le moins d'hypothèses, la structure la plus simple et le plus facile à comprendre. Et il existe désormais de nombreuses bibliothèques open source (telles que TFHE) construites sur la base du système GSW.
Pour des raisons de place, nous terminerons cet article ici. Dans le prochain article, nous pourrons d’abord apprendre les bases du système GSW : le système de chiffrement basé sur réseau et le problème LWE. Une fois le problème LWE compris, le problème résolu par GSW devient très clair.
Voir l'original
Cette page peut inclure du contenu de tiers fourni à des fins d'information uniquement. Gate ne garantit ni l'exactitude ni la validité de ces contenus, n’endosse pas les opinions exprimées, et ne fournit aucun conseil financier ou professionnel à travers ces informations. Voir la section Avertissement pour plus de détails.
Une exploration préliminaire du chiffrement entièrement homomorphe : la définition et la revue historique de FHE
Auteur : Steven Yue
J'ai suivi le cours CS355 (Advanced Cryptography) à Stanford il y a quelque temps. Nous avons été formés par trois doctorants de Dan, Dima Kogan, Florian Tramer et Saba Eskandarian. Les trois enseignants-chercheurs ont chacun leurs caractéristiques propres et leurs orientations de recherche sont également très différentes. Dima se concentre sur la technologie de protection de la vie privée PIR (Private Information Retri), Florian se concentre sur la recherche sur le ML et la blockchain, et Saba se concentre sur la preuve de connaissance nulle.
Le cours CS355 couvre presque tout le contenu dans le domaine de la cryptographie de l'Antiquité à nos jours. De la première fonction unidirectionnelle (fonction unidirectionnelle), à l'équation elliptique (ECC) et au couplage, et enfin à certains MPC populaires, connaissance nulle, récupération d'informations privées (PIR), algorithme entièrement homomorphe, etc. . Comme le cours vient de se terminer il y a deux jours, j'ai organisé une série de notes alors que le contenu des connaissances était encore dans ma mémoire superficielle. Le contenu du cours est très intéressant, je partagerai le reste du contenu avec vous plus tard quand j'aurai le temps~
Dans ce numéro, nous parlerons du cryptage entièrement homomorphe (FHE) récemment populaire et de la technologie de cryptage basée sur treillis qui l'accompagne.
Qu'est-ce que le chiffrement entièrement homomorphe ?
Je pense que de nombreux amis ont entendu parler du nom de chiffrement entièrement homomorphe (FHE). Ces dernières années, de plus en plus de sujets ont été abordés concernant la protection de la vie privée, et une série de technologies d'application de cryptographie, notamment le cryptage homomorphe, ont également été largement popularisées.
Afin de mieux comprendre ce sujet, je voudrais présenter brièvement la définition du cryptage entièrement homomorphe.
Examen du système de cryptage
Avant de commencer, passons en revue le système de cryptage le plus traditionnel.
Nous savons tous que si vous souhaitez construire un système de cryptage, vous avez souvent besoin d’une clé. Grâce à cette clé, nous pouvons chiffrer les informations en clair en texte chiffré à une extrémité, puis utiliser la clé pour rétablir le texte chiffré dans son apparence d'origine à l'autre extrémité. Sans cette clé, il serait difficile pour d'autres personnes de savoir quelles informations nous avons transmises.
Dans la recherche en cryptographie, chaque fois que nous voyons la définition d’un nouveau système, nous devons souvent énoncer les propriétés que le système devrait avoir.
La principale signification de la sécurité sémantique est qu’un observateur ne peut pas faire la distinction entre deux messages cryptés. Ainsi, si un intrus écoute le réseau et voit les informations cryptées que j'envoie, tant que le système de cryptage que j'utilise est sémantiquement sécurisé, je peux être sûr que l'intrus ne peut obtenir aucune information sur le contenu crypté à partir du texte chiffré.
Après avoir satisfait aux deux propriétés ci-dessus, un système de cryptage devient fiable.
Après avoir compris en quoi consiste le système de cryptage, nous pouvons prêter attention à ce texte chiffré qui ressemble à un code tronqué généré aléatoirement. Nous savons tous que nous n’obtiendrons aucune information simplement en regardant le texte chiffré lui-même. Mais cela signifie-t-il que s’il n’y a pas de clé et seulement un texte chiffré, nous ne pouvons rien faire ?
Nous connaissons tous la réponse : pas vraiment.
Pour cette propriété, nous l’appelons homomorphisme additif. Cela signifie que le texte chiffré entretient une relation algébrique subtile avec le texte original précédent. Si nous additionnons le texte chiffré, nous pouvons obtenir le nouveau texte chiffré en additionnant le texte original. De la même manière, on peut conclure qu’il existe également des algorithmes de chiffrement homomorphes additifs. Nous pouvons multiplier le texte chiffré généré par un algorithme homomorphique multiplicatif, puis obtenir le texte chiffré correspondant au résultat de la multiplication des textes originaux. Dans l'ensemble du processus, nous n'avons besoin de connaître aucune information relative à la clé, nous combinons simplement le texte chiffré qui ressemble à un code tronqué aléatoire.
Par exemple : Système de vote anonyme
Donnons ensuite un exemple pour décrire de manière vivante l’aspect pratique du cryptage homomorphe.
Nous savons tous à quoi ressemble le vote en ligne : si le patron d'une entreprise souhaite lancer une vague de vote, il doit choisir si l'entreprise doit adopter le système 996. Le patron peut ensuite demander au service informatique de configurer un serveur et de laisser les employés soumettre leurs choix : votez 0 pour signifier qu'ils ne veulent pas, et votez 1 pour signifier qu'ils veulent. Après la période de vote finale, le patron peut additionner tous les votes. Si le total final de tous les votes dépasse la moitié du nombre d’employés, l’entreprise en démarrera 996.
Ce mécanisme de vote semble très simple, mais il y a un gros problème de confidentialité : si le patron veut que tous les employés soient au nombre de 996, mais qu'il initie délibérément ce vote pour pêcher les forces de l'ordre pour voir quel employé ne veut pas faire d'heures supplémentaires, alors le patron peut tranquillement Il a confié à son jeune frère d'écouter Internet, d'enregistrer les choix soumis par chaque employé et enfin de voir qui a voté 0. Résultat : les salariés ont très peur et n’osent pas exprimer leurs sentiments.
Si nous pouvons utiliser un algorithme de chiffrement homomorphe additif, ce problème peut être facilement résolu.
Bien entendu, ce système est encore très incomplet : le service informatique peut par exemple aider directement le patron à décrypter les votes de chacun et à les enregistrer dans un document. Il existe d'autres outils cryptographiques qui peuvent nous aider à résoudre ce problème. Pour des raisons de place, aucune autre explication ne sera donnée ici.
Mais à ce stade, nous devrions pouvoir ressentir la puissance de l’algorithme de chiffrement homomorphe. Nous pouvons le comprendre ainsi : grâce à l'algorithme de chiffrement homomorphique, les utilisateurs peuvent effectuer une sorte de calcul proxy sécurisé (Secure Delegated Computation) avec un serveur distant (cloud) non fiable. Les utilisateurs peuvent utiliser la technologie de cryptage homomorphe pour crypter leurs entrées privées sensibles et les confier au cloud. Le cloud peut ensuite effectuer un certain degré de calcul sur les données cryptées, et enfin obtenir le résultat crypté souhaité par l'utilisateur et le renvoyer au utilisateur. Enfin, l'utilisateur peut utiliser la clé de déchiffrement pour ouvrir le résultat. Pendant toute la durée de l'accord, le délégataire (le cloud) n'est jamais en mesure de voir aucune information utile liée aux entrées privées.
Après avoir compris grossièrement les deux propriétés homomorphes les plus fondamentales, d’autres concepts deviennent très faciles à comprendre. D'un point de vue systématique, les systèmes de chiffrement homomorphes sont grossièrement divisés en quatre catégories : l'homomorphisme partiel, l'homomorphisme approximatif, l'homomorphisme complet en séries finies et l'homomorphisme complet.
Examinons ensuite tour à tour les définitions spécifiques de chaque catégorie.
Cryptage partiellement homomorphe
L'étape la plus élémentaire du chiffrement homomorphe est appelée chiffrement partiellement homomorphe, défini comme le texte chiffré n'ayant qu'une seule propriété homomorphe. Cette étape comprend les deux modes d'homomorphisme additif et d'homomorphisme multiplicatif que nous avons décrits ci-dessus.
On obtient le texte chiffré correspondant à la multiplication de ces deux messages ! C'est la propriété d'homomorphisme multiplicatif. Nous pouvons continuer à superposer de nouveaux textes chiffrés sur ce texte chiffré, afin d'obtenir n'importe quelle multiplication entre textes chiffrés.
Cryptage homomorphe approximatif (cryptage quelque peu homomorphe)
Comme nous l'avons dit dans le paragraphe précédent, si l'on veut multiplier les entrées privées et obtenir une combinaison linéaire entre elles, un simple algorithme de chiffrement partiellement homomorphe (RSA, ElGamal) ne peut pas être complété. Il nous faut donc passer à l'étape suivante.
La prochaine étape du chiffrement partiellement homomorphe est le chiffrement approximativement homomorphique, qui est un pas de plus vers le chiffrement entièrement homomorphe que nous souhaitons atteindre. Si nous disposons d’un algorithme de chiffrement approximativement homomorphe, nous pouvons alors calculer simultanément l’addition et la multiplication sur le texte chiffré. Cependant, il convient de noter que cette étape étant approximativement homomorphe (quelque peu homomorphe), le nombre d'additions et de multiplications pouvant être effectuées est très limité et la fonction F pouvant être calculée se situe également dans une plage limitée.
Il n'existe pas beaucoup d'exemples courants de chiffrement approximativement homomorphe à ce stade. Si l'on dit l'exemple le mieux compris, il devrait s'agir de l'algorithme de chiffrement de groupe cyclique basé sur l'appariement.
Ci-dessus, nous avons brièvement discuté de l'algorithme de chiffrement ElGamal basé sur des groupes cycliques ordinaires. Nous savons tous que cet algorithme est additivement homomorphe, ce qui signifie qu’il peut obtenir des combinaisons linéaires entre des textes chiffrés arbitraires. En fait, dans certains groupes cycliques spéciaux, nous pouvons également trouver de faibles propriétés d’homomorphisme multiplicatif.
Cette limitation prouve que le système est approximativement homomorphe, puisque nous ne pouvons pas calculer la fonction F de logique et de profondeur arbitraires.
Cryptage homomorphe entièrement nivelé
Après avoir atteint l’étape suivante, nous nous rapprochons de l’objectif de l’homomorphisme complet.
Cette étape est appelée chiffrement entièrement homomorphe en séries finies. A ce stade, nous pouvons déjà effectuer n'importe quelle combinaison d'addition et de multiplication sur le texte chiffré sans aucune limitation quant au nombre de fois.
Cryptage entièrement homomorphe (FHE)
Après de nombreux appels, nous arrivons enfin au cryptage entièrement homomorphe (FHE) que nous attendons de voir.
Comme son nom l'indique, un système de cryptage entièrement homomorphe n'a aucune restriction sur les méthodes de calcul. Nous pouvons arbitrairement combiner des textes chiffrés pour former de nouveaux textes chiffrés sans clé, et le nouveau texte chiffré, quelle que soit la complexité informatique, peut être parfaitement restauré au texte original.
Lorsque nous atteignons ce stade, le calcul d’agent sûr mentionné précédemment devient réalisable. Si nous pouvons trouver un système de cryptage entièrement homomorphique plus efficace, nous pouvons transférer en toute sécurité tous les calculs locaux vers le cloud sans fuite de données !
Définition d'un système de chiffrement entièrement homomorphe
Avant de commencer la discussion sur l’histoire des systèmes entièrement homomorphes ci-dessous, nous pouvons définir systématiquement la définition formelle des systèmes entièrement homomorphes. Un système de chiffrement entièrement homomorphe comporte un total de quatre algorithmes :
Avant de commencer à apprendre comment l’algorithme de chiffrement entièrement homomorphe est implémenté, autant examiner comment est né le concept de chiffrement entièrement homomorphe.
Le concept de FHE (entièrement homomorphique) a été proposé à la fin des années 1970. En 1978, Rivest, Adleman et Dertouzos, plusieurs grands noms de la cryptographie, évoquent pour la première fois dans leur article On Data Banks and Privacy Homomorphisms l'idée d'un système capable d'effectuer certains calculs sur le texte chiffré et d'opérer indirectement sur le texte original. Plus tard, cette idée a été résumée à nouveau et nommée chiffrement entièrement homomorphe.
On constate que le concept de chiffrement totalement homomorphe est proposé depuis longtemps. Étonnamment, en 1976, deux ans avant la publication de l’article, le protocole d’échange de clés Diffle-Hellman venait d’être proposé ! Cela montre que l’imagination des experts en cryptographie est encore très riche.
Lorsque le concept de FHE a été proposé, l’ensemble de la communauté universitaire a été ému et a entamé une recherche de plusieurs décennies pour tenter de trouver un algorithme parfait doté de propriétés entièrement homomorphes. Mais au cours des dernières décennies, les gens ont essayé toutes les options imaginables, mais ils n’ont pas trouvé une option qui satisfasse à toutes les conditions pour être pleinement homomorphe et dont la sécurité puisse être facilement prouvée.
Jusqu'en 2009, le docteur Craig Gentry, qui étudiait à Stanford, a soudainement eu une idée et a surmonté les difficultés de l'algorithme FHE. Dans sa thèse de doctorat, il a présenté pour la première fois un système de cryptage entièrement homomorphe raisonnable et sécurisé ! Ce système est basé sur l’hypothèse d’un réseau idéal. Le système entièrement homomorphe proposé par Gentry09 est souvent appelé système de cryptage entièrement homomorphe de première génération.
Dans l'article de Gentry, il mentionne également un concept crucial appelé Bootstrapping. Le bootstrapping est une technique de traitement spéciale pour le texte chiffré. Après traitement, il peut « rafraîchir » un texte chiffré avec un bruit proche de la valeur critique en un nouveau texte chiffré avec un bruit très faible. Grâce au Bootstrapping, le bruit d'un système en série finie ne peut jamais dépasser la valeur critique, devenant ainsi un système entièrement homomorphe. De cette façon, nous pouvons calculer homomorphiquement F de n’importe quelle taille.
Après la percée majeure de Gentry, l'ensemble du cercle de la cryptographie est retombé dans la folie et tout le monde a commencé à se démener pour trouver un système entièrement homomorphe plus efficace et polyvalent basé sur les idées proposées par Gentry.
En 2011, deux grands noms, Brakerski et Vaikuntanathan, ont proposé un nouveau système de chiffrement entièrement homomorphe, basé sur l'apprentissage avec erreurs (LWE), une autre hypothèse du chiffrement sur réseau. La même année, Brakerski, Gentry et Vaikuntanathan complètent le système et le publient officiellement. Le système entièrement homomorphe qu’ils ont inventé est appelé en abrégé le système BGV. Le système BGV est un système de chiffrement homomorphe de niveau limité, mais il peut être transformé en un système entièrement homomorphe grâce au Bootstrapping. Comparé au système proposé par Gentry09, le système BGV utilise une hypothèse LWE plus réaliste. De manière générale, nous appelons le système BGV le système de cryptage entièrement homomorphe de deuxième génération.
En 2013, Gentry fait son grand retour. Gentry, Sahai et Waters ont lancé un nouveau système de cryptage GSW entièrement homomorphe. Le système GSW est similaire au BGV dans la mesure où il possède des propriétés entièrement homomorphes en séries finies. Il est basé sur l'hypothèse LWE plus simple et peut être entièrement homomorphe grâce au bootstrapping. Nous désignons généralement le système GSW comme le système de cryptage entièrement homomorphe de troisième génération.
Après 2013, la cryptosphère a pratiquement prospéré. Basés sur le système original entièrement homomorphe de trois générations, diverses nouvelles conceptions ont vu le jour, dédiées à l'optimisation et à l'accélération de l'efficacité opérationnelle des systèmes BGV et GSW. IBM a développé une bibliothèque informatique open source entièrement homomorphe HElib basée sur le système BGV et l'a transplantée avec succès sur les principales plates-formes mobiles. Parallèlement, il existe un autre projet open source TFHE qui mérite également d'être noté. TFHE est basé sur le système GSW, avec diverses optimisations et accélérations ajoutées, et il est désormais très célèbre.
En plus de développer des bibliothèques traditionnelles entièrement homomorphes, de nombreuses équipes étudient également comment mieux accélérer le calcul d'algorithmes de chiffrement entièrement homomorphes via du matériel hétérogène tel que GPU, FPGA et ASIC. Par exemple, cuFHE est un système de chiffrement entièrement homomorphe accéléré par GPU basé sur CUDA.
Du point de vue actuel, cela fait 11 ans que Gentry a frappé à la porte du système entièrement homomorphe. De nos jours, la recherche sur le FHE est en plein essor dans l'industrie, et de nombreuses personnes étudient les systèmes entièrement homomorphes sous différents angles et exigences d'application. Jusqu'à aujourd'hui, nous disposons déjà d'une variété de méthodes réalisables de mise en œuvre du FHE, mais ce que tout le monde recherche toujours, c'est l'efficacité du fonctionnement du système FHE. En prenant comme exemple la bibliothèque FHE de pointe actuelle, le calcul homomorphique d'une logique relativement simple sur une plate-forme mobile peut prendre aussi peu que des dizaines de millisecondes et jusqu'à des dizaines de secondes. Ces unités de temps sont extrêmement lentes pour les systèmes informatiques.
Comment rendre le système FHE plus efficace sur des plates-formes hétérogènes reste un mystère non résolu. Si ce problème est une fois résolu, la conversion de tous les calculs informatiques en calculs entièrement homomorphes et le fait que des agents effectuent des calculs sur des cloud tiers seront un avenir facile.
La relation entre FHE et MPC
Avant de terminer l'article, je voudrais ajouter quelques mots sur la relation entre FHE et MPC. MPC signifie Secure Multi-Party Computation, qui est un calcul multipartite fiable. Cela signifie généralement que plusieurs parties ont leurs propres entrées privées et ne souhaitent pas les divulguer à d'autres, mais qu'elles souhaitent utiliser leurs propres entrées pour calculer ensemble une fonction F et partager les résultats du calcul.
Le MPC est en fait un domaine très connu et étudié depuis longtemps. Depuis que le cryptographe Yao Qizhi a lancé ses circuits garbled au siècle dernier, le domaine du MPC a acquis une large reconnaissance et de nombreuses percées ont été réalisées. Nous disposons désormais déjà de nombreuses bibliothèques MPC pouvant être utilisées, et elles ont également une certaine efficacité de fonctionnement.
Les amis qui connaissent MPC peuvent avoir de nombreuses questions après avoir vu l'histoire difficile des systèmes de chiffrement entièrement homomorphes : Pourquoi le chiffrement entièrement homomorphe ne peut-il pas être remplacé directement par un protocole MPC ?
En effet, un protocole MPC peut remplacer complètement un protocole FHE. Il suffit d'utiliser l'utilisateur et l'entrée privée en tant que partie dans un protocole, puis d'utiliser le serveur informatique proxy distant comme autre partie, qui remplit les conditions d'exécution du protocole MPC. Ce n'est que par certaines interactions que l'informatique proxy peut être réalisé. Et le serveur ne peut pas voir les entrées privées.
Mais il y a un point très important que nous avons négligé : puisque MPC est interactif, l'utilisateur et le serveur doivent calculer et communiquer ensemble pour compléter le protocole. Cela entre en conflit avec l’exigence la plus fondamentale du calcul des agents FHE. Si l'utilisateur doit rester en ligne tout le temps pour conclure l'accord et également payer une partie de la puissance de calcul, alors en fait le calcul n'est pas du tout « proxy » et les deux parties ne font que plus de calculs pour des raisons de sécurité des informations. . Cela explique également pourquoi le domaine du MPC a réalisé des avancées majeures, mais le domaine du FHE est encore inconnu, car les deux systèmes résolvent des problèmes complètement différents.
Voyant cela, chacun doit avoir une compréhension très approfondie du système de cryptage entièrement homomorphe.
Prochain arrêt, nous pourrons en apprendre davantage sur le système de cryptage entièrement homomorphe GSW mentionné ci-dessus. Bien qu'il s'agisse de la troisième génération de systèmes entièrement homomorphes, je pense que parmi les trois systèmes Gentry09, BGV et GSW, GSW est celui avec le moins d'hypothèses, la structure la plus simple et le plus facile à comprendre. Et il existe désormais de nombreuses bibliothèques open source (telles que TFHE) construites sur la base du système GSW.
Pour des raisons de place, nous terminerons cet article ici. Dans le prochain article, nous pourrons d’abord apprendre les bases du système GSW : le système de chiffrement basé sur réseau et le problème LWE. Une fois le problème LWE compris, le problème résolu par GSW devient très clair.