Lorsque l'on pense à la cryptographie, les premières utilisations qui viennent à l'esprit sont le chiffrement au repos et le chiffrement pendant le transport. Le premier permet de stocker des données sur des disques durs chiffrés, des périphériques amovibles ou même des bases de données cloud et offre la garantie que seul le propriétaire légitime peut voir ou modifier le contenu en texte clair. Le chiffrement pendant le transport garantit que les données transmises sur Internet ne sont accessibles que par les destinataires désignés, même si elles transitent par des routeurs ou des canaux publics. Les deux scénarios reposent sur le chiffrement, avec la garantie supplémentaire d'intégrité que les données n'ont pas été altérées par un attaquant malveillant entre les deux. C'est ce qu'on appelle le chiffrement authentifié : une fois que les données sont chiffrées, personne dans la chaîne ne peut déduire un seul bit de données (confidentialité) et personne ne peut modifier le texte chiffré sans que cela soit détecté (intégrité/authenticité).

Certains cas d'utilisation collaboratifs nécessitent qu'un traitement non trivial soit autorisé même sur les textes chiffrés. C'est le domaine des techniques de préservation de la confidentialité ou du chiffrement en cours d'utilisation, dont le chiffrement homomorphe complet (FHE) en fait partie. Un exemple est le vote électronique dans le cloud : les électeurs peuvent, par exemple, chiffrer leur bulletin, puis une entité intermédiaire aggrégerait tous les bulletins pour compter le nombre de votes, et seul le résultat final serait publié. Malheureusement, avec le chiffrement authentifié, l'entité intermédiaire devrait déchiffrer tous les bulletins pour effectuer un tel calcul, et verrait les votes individuels en clair, ce qui est assez contraignant. En théorie, nous pourrions mélanger les bulletins (certaines procédures de vote électronique reposent en fait sur cela), mais contrairement aux bulletins papier, les mécanismes cryptographiques traditionnels qui garantissent l'intégrité rendent également beaucoup plus difficile de dissocier un bulletin chiffré de l'identité de son expéditeur. Dans un système de vote électronique, on pourrait ajouter une barrière matérielle autour de l'entité qui compte les votes. C'est, par exemple, l'objectif des enclaves d'exécution de confiance. De telles enclaves rendraient beaucoup plus difficile pour un attaquant d'interagir avec l'entité. Mais alors, une défaillance matérielle pourrait divulguer la clé de déchiffrement, et contrairement aux erreurs logicielles, les vulnérabilités de conception matérielle ne peuvent pas être corrigées facilement.

Pour répondre à ce cas d'utilisation et à d'autres cas similaires, nous pouvons utiliser le chiffrement homomorphe complet (FHE). Le FHE est une forme spéciale de chiffrement qui permet de calculer une fonction sur les textes chiffrés sans les décrypter et d'obtenir directement un chiffrement de la sortie de la fonction.

La plupart du temps, la fonction f à évaluer est publique, de sorte que la séquence des étapes de traitement pour convertir un chiffrement de f(x) est une connaissance publique et peut être effectuée dans le cloud sans impliquer aucun secret.

Cette figure représente les 3 scénarios pour le vote électronique : sur l'image la plus à gauche, une entité de confiance mélange et déchiffre les votes individuels avant de publier leur addition. Nous devons avoir confiance en l'entité effectuant le calcul afin que la confidentialité du votant soit préservée et que les votes soient correctement comptés. Sur l'image centrale, une enclave de confiance, garantissant l'intégrité et la confidentialité, est utilisée pour effectuer le même calcul. Sur l'image de droite, le chiffrement homomorphe est utilisé : les votes chiffrés peuvent être additionnés (en public) avant que le résultat ne soit déchiffré. E( ) représente l'opération de chiffrement, tandis que D( ) représente le déchiffrement.

Le FHE est également compact, ce qui signifie que la taille en bits du texte chiffré de sortie et l'effort pour le décrypter dépendent uniquement du nombre de bits du résultat en texte clair. Cela ne dépend pas de la chaîne de calculs qui a été appliquée. Cela exclut les cryptosystèmes non compacts triviaux qui se contenteraient de concaténer les textes chiffrés d'entrée de x avec le code source de f, et laisseraient le destinataire faire tout le travail en décryptant x puis en appliquant f.

L'externalisation FHE est souvent présentée comme une alternative aux enclaves sécurisées, basée sur la difficulté d'un problème mathématique plutôt que sur des barrières pratiques. FHE est donc complètement invulnérable aux attaques passives par canal latéral ou à d'autres corruptions de l'hôte cloud. Imaginez que quelqu'un doit externaliser certaines calculs, mais que les données sont vraiment sensibles. Cette personne serait probablement réticente à utiliser une VM cloud si quelqu'un d'autre peut être root sur la machine. Ils hésiteraient probablement également à l'exécuter dans une enclave comme SGX, sachant que le CPU et la mémoire des hôtes cloud sont constamment surveillés pour la charge, la puissance, la température. Peut-être que certaines informations peuvent être extraites de ces mesures. Cette personne peut être rassurée par la promesse de FHE que l'extraction de n'importe quel bit d'information nécessite la résolution d'un problème mathématique post-quantique, indépendamment de tout type de mesure que nous pourrions rassembler.

Si la confidentialité fournie par le schéma empêche un attaquant de lire un seul bit d’information sans la clé secrète, la malléabilité universelle de FHE permet, en revanche, à un attaquant de retourner n’importe quel bit calculé : dans un circuit, ce serait l’équivalent d’attaques actives par canal auxiliaire, où l’attaquant se voit accorder un rayon laser magique qui peut cibler n’importe quel bit. Cela peut sembler très effrayant au premier abord, mais dans FHE ces attaques correspondent à des exécutions malhonnêtes des opérations homomorphes. Ils peuvent être évités en ajoutant des réplications ou des redondances dans le calcul.

Le FHE est souvent présenté de manière à clé publique. Il y a:

1. Une clé de déchiffrement : Il s'agit de la clé maîtresse du cryptosystème, à partir de laquelle toutes les autres clés peuvent être dérivées. La clé de déchiffrement est généralement générée localement et jamais transmise, et la seule personne pouvant déchiffrer un texte chiffré FHE est le propriétaire de la clé de déchiffrement.
2. Une clé de chiffrement: en mode clé publique, lorsque la partie qui fournit le texte chiffré initial n'est pas le propriétaire de la clé de déchiffrement, cette clé de taille moyenne consiste généralement en des chiffrements aléatoires de zéro. Étant donné que le chiffrement homomorphe complet prend en charge les fonctions affines, cela suffit pour chiffrer n'importe quel message.
3. Une clé d'évaluation : Cette clé doit être donnée à toute partie qui évaluera une fonction sur des textes chiffrés. Cette clé peut également être publiée ou transmise comme toute clé publique. La taille de la clé d'évaluation varie de vide à très grande, selon que la fonction à évaluer est linéaire ou arbitraire.

Le propriétaire de la clé de déchiffrement est le propriétaire du secret le plus sensible du cryptosystème. Cette personne est responsable de s'assurer que la chaîne d'opérations homomorphes qui ont été exécutées est légitime et que le texte chiffré final est sûr à déchiffrer, puis de déchiffrer le résultat en clair. Si des opérations malveillantes sont introduites dans la chaîne, la clé de déchiffrement pourrait potentiellement être divulguée au moment du déchiffrement. Heureusement, les opérations homomorphes peuvent être effectuées en public et vérifiées.

Scénarios de chiffrement homomorphe complet

Dans cette section, nous décrivons quelques scénarios dans lesquels le FHE peut être utilisé, ainsi que quelques avantages et inconvénients de chaque configuration.

Mode d'externalisation

Dans cette figure, la clé orange symbolise la clé de déchiffrement (et son propriétaire). Les textes chiffrés FHE sont représentés par des verrous de la même couleur que la clé de déchiffrement. Les parties qui contribuent avec des données privées sont représentées par un cylindre : ici, seule Alice contribue avec des données privées. Du côté de Bob, la fonction d’évaluation et la clé d’évaluation sont publiques, et le calcul, représenté par une boîte verte, peut être effectué de manière déterministe. Tout le monde peut retracer le calcul et détecter si le texte chiffré de sortie revendiqué est incorrect.

C'est historiquement le premier cas d'utilisation qui a été publié pour le FHE. Il vise à transformer l'informatique en nuage en informatique privée, analogue à un enclave sécurisé, mais basé sur la sécurité cryptographique au lieu de la sécurité matérielle. Dans un tel contexte, Alice possède des données privées, mais a des capacités de calcul limitées. Bob imite une instance de cloud avec une puissance de calcul beaucoup plus grande. Bob ne contribue pas avec des données privées supplémentaires. Alice peut externaliser un calcul en chiffrant les entrées, Bob évalue ensuite la fonction (publique) désirée de manière homomorphe et envoie le résultat chiffré à Alice.

Avec les capacités matérielles actuelles, le mode d'externalisation est encore un peu lent à être utilisé dans sa pleine généralité en pratique - nous pouvons généralement compter un facteur de surcoût de temps d'exécution de 1 million et un surcoût de mémoire de 1 000 sur les cas d'utilisation non linéaires. Cependant, du matériel FHE est actuellement en cours de développement pour combler l'écart, comme le Projet DPRIVE de Darpa ou CryptoLight.

Actuellement, le mode d'externalisation est utilisé dans la pratique pour les cas d'utilisation de récupération d'informations privées (PIR), où un serveur (Bob) dispose d'une grande base de données publique, un client (Alice) émet une requête et l'index interrogé doit rester privé. De tels schémas PIR bénéficient grandement de la linéarité et de la compacité des opérations chiffrées homomorphiques, tandis que la faible profondeur multiplicatrice des circuits maintient les coûts de calcul dans des limites raisonnables.

Ce tableau résume les avantages et les inconvénients du mode d'externalisation.

Mode de calcul à deux parties

Cette figure utilise le même codage couleur que précédemment. Cette fois, Bob contribue au calcul avec certaines données privées. Le calcul du côté de Bob n'est plus publiquement vérifiable, symbolisé par une boîte rouge, ce mode devrait être restreint aux cas d'utilisation honnêtes mais curieux.

Dans cette nouvelle configuration, la seule différence est que Bob contribue au calcul avec certaines données privées. Dans ce cas, le chiffrement homomorphe complet est une bonne solution de calcul à deux parties, avec une communication minimale, et offre des garanties solides du côté du demandeur : Bob n'apprend rien sur les données d'Alice, et Alice apprend le résultat du calcul.

Une application potentielle pour ce scénario serait le problème des millionnaires, où Alice et Bob sont deux millionnaires qui veulent savoir qui est plus riche sans révéler leur richesse à l'autre partie. Les solutions à ce problème sont utilisées dans les applications de commerce électronique.

Mode d'agrégation

Ceci est un affinement du mode d'externalisation, où les données de nombreux participants peuvent être agrégées de manière compacte (dans le sens où la sortie ne grandit pas avec la quantité de participants) et vérifiable publiquement. Les utilisations typiques comprennent l'apprentissage fédéré et le vote électronique.

Mode Client-Serveur

Cette configuration est un raffinement du mode de calcul à deux parties, où la partie de calcul fournit désormais un service de calcul sécurisé à plusieurs clients, qui ont leur propre clé secrète. Le chiffrement homomorphe complet peut par exemple être utilisé comme un service de prédiction de modèle privé (par exemple, un service ML avec un modèle privé et des entrées) : le serveur possède le modèle privé (privé mais en texte clair) et chaque client possède ses propres données et souhaite exécuter une prédiction. En conséquence, chaque client récupère sa propre prédiction chiffrée, avec sa propre clé secrète.

Comment le chiffrement homomorphe garantit-il que la fonction calculée est légitime?

Il est toujours plus facile d'utiliser le chiffrement homomorphe complet dans les scénarios de collaboration où chaque participant a une incitation à suivre le protocole honnêtement. Le chiffrement homomorphe complet peut par exemple être utilisé pour calculer des statistiques entre deux entités juridiques du même groupe dans deux pays différents: des réglementations telles que le RGPD autorisent la publication de certaines statistiques, mais empêchent en général la collecte de toutes les données individuelles au même endroit. Dans ce cas, l'utilisation du chiffrement homomorphe complet est possible et tous les participants ont une incitation à suivre le protocole honnêtement. Dans un scénario non collaboratif, le moyen le plus facile de s'assurer que la fonction pertinente a été calculée est d'introduire de la redondance. Par exemple, dans les scénarios d'externalisation et d'agrégation, les calculs homomorphes sont entièrement publics et peuvent être rendus déterministes. Tant que deux entités indépendantes ou plus obtiennent le même texte chiffré de sortie exact, alors le calcul est correct et le résultat peut être déchiffré en toute sécurité. Plus il y a de redondance, plus nous pouvons avoir confiance dans le résultat, ce qui bien sûr est un compromis avec l'efficacité.

De plus, lorsque la partie informatique garantit un résultat FHE en signant numériquement les textes chiffrés d'entrée et de sortie, tout le monde peut retracer la même computation FHE et vérifier si la preuve est valide. Toute tentative de tricherie de la part de la partie de calcul FHE peut être publiquement détectée et associée à un certificat publiquement vérifiable qui expose la triche et le tricheur - nous appelons ce modèle un modèle de sécurité cachée forte.

Signatures entièrement homomorphessont un autre moyen de vérifier la justesse d'un calcul, sans nécessiter un vérificateur indépendant, mais nécessite en général beaucoup plus de ressources.

Comment le chiffrement homomorphique complet garantit-il que le destinataire final ne déchiffre que le résultat final et pas les variables intermédiaires?

Le moyen le plus simple de le faire est de veiller à ce que le propriétaire de la clé de déchiffrement n'ait pas accès à un quelconque texte chiffré intermédiaire.

Dans le scénario à deux parties, ou dans celui client-serveur, Alice chiffre l'entrée, Bob effectue le calcul sur les textes chiffrés et transmet le résultat chiffré à Alice. Il est clair qu'Alice pourra uniquement déchiffrer le résultat, elle n'a pas accès à d'autres variables.

Dans un scénario d'agrégation de cloud, comme le vote électronique où de nombreux participants envoient des bulletins de vote cryptés sur un cloud commun, une autre technique est utilisée: la clé de déchiffrement n'est généralement pas donnée à un seul destinataire mais plutôt partagée secrètement entre différents membres d'une autorité de déchiffrement. Dans ce cas, le déchiffrement ne peut être déclenché que sur un seul texte chiffré en exécutant un calcul multipartite qui implique une communication en ligne entre les membres de l'autorité. Si un membre refuse de déchiffrer un texte chiffré, le déchiffrement est impossible. Cela garantit que seuls les textes chiffrés qui sont acceptés par tous les membres de l'autorité peuvent être déchiffrés.

Les blocs de construction du chiffrement homomorphique

Il existe trois types de chiffrement homomorphique : le chiffrement homomorphe partiel (PHE), le chiffrement homomorphe de niveau (LHE) et le chiffrement homomorphe complet (FHE). Le chiffrement homomorphe partiel nous permet uniquement de calculer un ensemble restreint de fonctions (par exemple, seulement une somme, seulement des fonctions linéaires, seulement des fonctions bilinéaires), tandis que le chiffrement homomorphe de niveau et le chiffrement homomorphe complet peuvent évaluer des circuits arbitraires, ou, de manière équivalente, des fonctions dont les flux de contrôle sont indépendants des données. Pour le LHE, les paramètres cryptographiques dépendent de la fonction et augmentent avec la complexité du circuit, ce qui se traduit par des textes chiffrés et des clés plus importants. Les schémas FHE permettent, pour un ensemble de paramètres donné, et donc pour une taille de clé et de texte chiffré donnée, d'évaluer toute fonction pouvant être représentée comme un circuit avec des portes arithmétiques ou binaires. Autrement dit, contrairement au LHE, même si le circuit à évaluer devient de plus en plus grand, les paramètres du schéma (et les clés et les textes chiffrés) ne deviennent pas plus importants.

En d'autres termes, lorsque la question est posée de savoir si un circuit de texte en clair donné peut être exécuté de manière homomorphe, et à quel coût (en termes de surcharge de temps et de mémoire), PHE peut répondre non à la question. LHE répond oui, mais peut fixer un coût arbitrairement élevé pour les circuits complexes. FHE répond également oui et, en plus, il fournit les clés, les algorithmes de chiffrement et de déchiffrement, et la façon d'évaluer de manière homomorphe un ensemble universel de Gates avant même que le circuit de texte en clair soit spécifié. FHE est donc le seul mode qui garantit que la mémoire et le temps d'exécution de l'évaluation homomorphe restent proportionnels au circuit de texte en clair d'origine. Pour ce faire, tous les schémas FHE connus aujourd'hui traitent de textes chiffrés bruyants qui deviennent de plus en plus bruyants à mesure que les calculs sont effectués. Pour éviter que le bruit ne déborde dans le calcul effectué et entraîne des erreurs de déchiffrement, ces schémas effectuent régulièrement une opération assez coûteuse appelée amorçage, qui réduit le bruit à un niveau gérable. Plus de détails sur les spécificités de chaque type de schéma, sur l'amorçage et sur la façon de réduire le bruit et les autres coûts avec les compilateurs FHE, dans le deuxième billet de blog de cette série!

Avertissement :

1. Cet article est reproduit à partir de [cryptographycaffe], Tous les droits d'auteur appartiennent à l'auteur original [Nicolas Gama et Sandra Guasch]. S'il y a des objections à cette re-publication, veuillez contacter le Gate Learnéquipe, et ils s'en occuperont rapidement.
2. Clause de non-responsabilité : Les points de vue et les opinions exprimés dans cet article sont uniquement ceux de l'auteur et ne constituent en aucun cas des conseils en matière d'investissement.
3. Les traductions de l'article dans d'autres langues sont effectuées par l'équipe Gate Learn. Sauf mention contraire, la copie, la distribution ou le plagiat des articles traduits est interdite.