Cryptage homomorphe - Homomorphic encryption

Cryptage homomorphe
Général
Dérivé de	Apprentissage de l'anneau avec des erreurs
Relatif à

Le chiffrement homomorphe est une forme de chiffrement qui permet aux utilisateurs d'effectuer des calculs sur ses données chiffrées sans les déchiffrer au préalable. Ces calculs résultants sont laissés sous une forme chiffrée qui, une fois déchiffrée, aboutit à une sortie identique à celle produite si les opérations avaient été effectuées sur les données non chiffrées. Le chiffrement homomorphe peut être utilisé pour le stockage et le calcul externalisés préservant la confidentialité . Cela permet aux données d'être cryptées et externalisées vers des environnements cloud commerciaux pour traitement, tout en étant cryptées.

Pour les données sensibles, telles que les informations sur les soins de santé, le cryptage homomorphe peut être utilisé pour activer de nouveaux services en supprimant les barrières de confidentialité empêchant le partage de données ou en augmentant la sécurité des services existants. Par exemple, l'analyse prédictive dans les soins de santé peut être difficile à appliquer via un fournisseur de services tiers en raison de problèmes de confidentialité des données médicales , mais si le fournisseur de services d'analyse prédictive peut utiliser des données cryptées à la place, ces problèmes de confidentialité sont atténués. De plus, même si le système du fournisseur de services était compromis, les données resteraient sécurisées.

La description

Le cryptage homomorphe est une forme de cryptage avec une capacité d'évaluation supplémentaire pour le calcul sur des données cryptées sans accès à la clé secrète . Le résultat d'un tel calcul reste crypté. Le chiffrement homomorphe peut être considéré comme une extension de la cryptographie à clé publique . Homomorphe fait référence à l' homomorphisme en algèbre : les fonctions de chiffrement et de déchiffrement peuvent être considérées comme des homomorphismes entre les espaces en clair et en texte chiffré.

Le chiffrement homomorphe comprend plusieurs types de schémas de chiffrement qui peuvent effectuer différentes classes de calculs sur des données chiffrées. Les calculs sont représentés sous forme de circuits booléens ou arithmétiques. Certains types courants de chiffrement homomorphe sont le chiffrement partiellement homomorphe, quelque peu homomorphe, nivelé, entièrement homomorphe et entièrement homomorphe :

Le chiffrement partiellement homomorphe englobe des schémas qui prennent en charge l'évaluation de circuits constitués d'un seul type de porte, par exemple, l'addition ou la multiplication.
Des schémas de chiffrement quelque peu homomorphes peuvent évaluer deux types de portes, mais uniquement pour un sous-ensemble de circuits.
Le cryptage nivelé entièrement homomorphe prend en charge l'évaluation de circuits arbitraires composés de plusieurs types de portes de profondeur limitée (prédéterminée).
Le chiffrement entièrement homomorphe (FHE) permet l'évaluation de circuits arbitraires composés de plusieurs types de portes de profondeur illimitée, et est la notion la plus forte de chiffrement homomorphe.

Pour la majorité des schémas de cryptage homomorphes, la profondeur multiplicative des circuits est la principale limitation pratique pour effectuer des calculs sur des données cryptées. Les schémas de cryptage homomorphes sont intrinsèquement malléables . En termes de malléabilité, les schémas de chiffrement homomorphes ont des propriétés de sécurité plus faibles que les schémas non homomorphes.

Histoire

Des schémas de chiffrement homomorphes ont été développés en utilisant différentes approches. Plus précisément, les schémas de chiffrement entièrement homomorphes sont souvent regroupés en générations correspondant à l'approche sous-jacente.

Pré-FHE

Le problème de la construction d'un schéma de cryptage entièrement homomorphe a été proposé pour la première fois en 1978, moins d'un an après la publication du schéma RSA. Pendant plus de 30 ans, il était difficile de savoir si une solution existait. Au cours de cette période, les résultats partiels comprenaient les schémas suivants :

Cryptosystème RSA (nombre illimité de multiplications modulaires)
Cryptosystème ElGamal (nombre illimité de multiplications modulaires)
Cryptosystème Goldwasser-Micali (nombre illimité d' opérations exclusives ou )
Cryptosystème Benaloh (nombre illimité d'ajouts modulaires)
Cryptosystème Paillier (nombre illimité d'ajouts modulaires)
Système Sander-Young-Yung (après plus de 20 ans résolu le problème des circuits de profondeur logarithmique)
Cryptosystème Boneh-Goh-Nissim (nombre illimité d'opérations d'addition mais au plus une multiplication)
Cryptosystème Ishai-Paskin ( programmes de branchement de taille polynomiale )

FHE de première génération

Craig Gentry , en utilisant la cryptographie basée sur le réseau , a décrit la première construction plausible pour un schéma de cryptage entièrement homomorphe. Le schéma de Gentry prend en charge les opérations d'addition et de multiplication sur les textes chiffrés, à partir desquels il est possible de construire des circuits pour effectuer des calculs arbitraires. La construction part d'un schéma de chiffrement quelque peu homomorphe , qui se limite à évaluer des polynômes de faible degré sur des données chiffrées ; il est limité parce que chaque texte chiffré est bruyant dans un certain sens, et ce bruit augmente à mesure que l'on ajoute et multiplie les textes chiffrés, jusqu'à ce que finalement le bruit rende le texte chiffré résultant indéchiffrable.

Gentry montre ensuite comment modifier légèrement ce schéma pour le rendre amorçable , c'est-à-dire capable d'évaluer son propre circuit de décryptage puis au moins une opération supplémentaire. Enfin, il montre que tout schéma de chiffrement amorçable quelque peu homomorphe peut être converti en un chiffrement entièrement homomorphe grâce à un auto-encastrement récursif. Pour le schéma « bruyant » de Gentry, la procédure d'amorçage « rafraîchit » efficacement le texte chiffré en lui appliquant la procédure de déchiffrement de manière homomorphe, obtenant ainsi un nouveau texte chiffré qui chiffre la même valeur qu'auparavant mais a un bruit plus faible. En "rafraîchissant" le texte chiffré périodiquement chaque fois que le bruit devient trop important, il est possible de calculer un nombre arbitraire d'additions et de multiplications sans trop augmenter le bruit.

Gentry a basé la sécurité de son schéma sur la dureté supposée de deux problèmes : certains problèmes du pire des cas sur des réseaux idéaux et le problème de la somme des sous-ensembles clairsemés (ou de faible poids). Le doctorat de Gentry la thèse fournit des détails supplémentaires. L'implémentation Gentry-Halevi du cryptosystème d'origine de Gentry a signalé un délai d'environ 30 minutes par opération de bit de base. Des travaux de conception et de mise en œuvre approfondis au cours des années suivantes ont amélioré ces premières mises en œuvre de plusieurs ordres de grandeur en termes de performances d'exécution.

En 2010, Marten van Dijk, Craig Gentry , Shai Halevi et Vinod Vaikuntanathan ont présenté un deuxième schéma de cryptage entièrement homomorphe, qui utilise de nombreux outils de construction de Gentry, mais qui ne nécessite pas de réseaux idéaux . Au lieu de cela, ils montrent que le composant quelque peu homomorphe du schéma idéal basé sur le réseau de Gentry peut être remplacé par un schéma quelque peu homomorphe très simple qui utilise des entiers. Le schéma est donc conceptuellement plus simple que le schéma de réseau idéal de Gentry, mais a des propriétés similaires en ce qui concerne les opérations homomorphes et l'efficacité. La composante quelque peu homomorphe des travaux de Van Dijk et al. est similaire à un schéma de cryptage proposé par Levieil et Naccache en 2008, ainsi qu'à celui proposé par Bram Cohen en 1998.

Cependant, la méthode de Cohen n'est même pas additivement homomorphe. Le schéma de Levieil-Naccache ne prend en charge que les additions, mais il peut être modifié pour prendre également en charge un petit nombre de multiplications. De nombreux raffinements et optimisations du schéma de Van Dijk et al. ont été proposées dans une séquence d'œuvres de Jean-Sébastien Coron, Tancrède Lepoint, Avardip Mandal, David Naccache et Mehdi Tibouchi. Certains de ces travaux comprenaient également des implémentations des schémas résultants.

FHE de deuxième génération

Les cryptosystèmes homomorphes de cette génération sont dérivés de techniques développées à partir de 2011-2012 par Zvika Brakerski, Craig Gentry , Vinod Vaikuntanathan et d'autres. Ces innovations ont conduit au développement de cryptosystèmes beaucoup plus efficaces, quelque peu et entièrement homomorphes. Ceux-ci inclus:

Le schéma Brakerski-Gentry-Vaikuntanathan (BGV, 2011), s'appuyant sur les techniques de Brakerski-Vaikuntanathan ;
Le schéma basé sur NTRU par Lopez-Alt, Tromer et Vaikuntanathan (LTV, 2012) ;
Le schéma Brakerski/Fan-Vercauteren (BFV, 2012), s'appuyant sur le cryptosystème invariant d' échelle de Brakerski ;
Le schéma basé sur NTRU par Bos, Lauter, Loftus et Naehrig (BLLN, 2013), s'appuyant sur le système cryptographique invariant d'échelle de LTV et Brakerski ;

La sécurité de la plupart de ces schémas est basée sur la dureté du problème (Ring) Learning With Errors (RLWE), à l'exception des schémas LTV et BLLN qui reposent sur une variante trop étendue du problème de calcul NTRU . Cette variante NTRU s'est par la suite révélée vulnérable aux attaques de réseau de sous-champs, c'est pourquoi ces deux schémas ne sont plus utilisés dans la pratique.

Tous les cryptosystèmes de deuxième génération suivent toujours le modèle de base de la construction originale de Gentry, à savoir qu'ils construisent d'abord un cryptosystème quelque peu homomorphe, puis le convertissent en un cryptosystème entièrement homomorphe à l'aide de l'amorçage.

Une caractéristique distinctive des cryptosystèmes de deuxième génération est qu'ils présentent tous une croissance beaucoup plus lente du bruit pendant les calculs homomorphes. Des optimisations supplémentaires par Craig Gentry , Shai Halevi et Nigel Smart ont abouti à des cryptosystèmes avec une complexité asymptotique presque optimale : effectuer des opérations sur des données chiffrées avec un paramètre de sécurité a une complexité de seulement . Ces optimisations s'appuient sur les techniques Smart-Vercauteren qui permettent de regrouper de nombreuses valeurs de texte en clair dans un seul texte chiffré et d'opérer sur toutes ces valeurs de texte en clair de manière SIMD . De nombreuses avancées dans ces cryptosystèmes de deuxième génération ont également été portées sur le cryptosystème sur les entiers. ${\style d'affichage T}$ ${\style d'affichage k}$ $T\cdot \mathrm {polylog} (k)$

Une autre caractéristique distinctive des schémas de deuxième génération est qu'ils sont suffisamment efficaces pour de nombreuses applications même sans invoquer l'amorçage, fonctionnant plutôt en mode FHE nivelé.

FHE de troisième génération

En 2013, Craig Gentry , Amit Sahai et Brent Waters (GSW) ont proposé une nouvelle technique pour construire des schémas FHE qui évite une étape coûteuse de « relinéarisation » dans la multiplication homomorphe. Zvika Brakerski et Vinod Vaikuntanathan ont observé que pour certains types de circuits, le cryptosystème GSW présente un taux de croissance du bruit encore plus lent, et donc une meilleure efficacité et une sécurité renforcée. Jacob Alperin-Sheriff et Chris Peikert ont ensuite décrit une technique d'amorçage très efficace basée sur cette observation.

Ces techniques ont été encore améliorées pour développer des variantes en anneau efficaces du cryptosystème GSW : FHEW (2014) et TFHE (2016). Le schéma FHEW a été le premier à montrer qu'en actualisant les textes chiffrés après chaque opération, il est possible de réduire le temps d'amorçage à une fraction de seconde. FHEW a introduit une nouvelle méthode pour calculer les portes booléennes sur des données cryptées qui simplifie grandement l'amorçage, et a mis en œuvre une variante de la procédure d'amorçage. L'efficacité de FHEW a été encore améliorée par le schéma TFHE, qui implémente une variante en anneau de la procédure d'amorçage en utilisant une méthode similaire à celle de FHEW.

FHE de quatrième génération

Le schéma CKKS prend en charge les opérations d'arrondi efficaces dans l'état crypté. L'opération d'arrondi contrôle l'augmentation du bruit dans la multiplication cryptée, ce qui réduit le nombre d'amorçages dans un circuit. Dans Crypto2018, CKKS se concentre sur une solution d'apprentissage automatique crypté. Cela est dû à une caractéristique du schéma CKKS qui crypte les valeurs approximatives plutôt que les valeurs exactes. Lorsque les ordinateurs stockent des données à valeur réelle, ils se souviennent des valeurs approximatives avec de longs bits significatifs, et non des valeurs réelles exactement. Le schéma CKKS est conçu pour traiter efficacement les erreurs résultant des approximations. Le schéma est familier à l'apprentissage automatique qui a des bruits inhérents dans sa structure.

Un article de 2020 de Baiyu Li et Daniele Micciancio traite des attaques passives contre CKKS, suggérant que la définition standard IND-CPA peut ne pas être suffisante dans les scénarios où les résultats du décryptage sont partagés. Les auteurs appliquent l'attaque à quatre bibliothèques de chiffrement homomorphes modernes (HEAAN, SEAL, HElib et PALISADE) et signalent qu'il est possible de récupérer la clé secrète à partir des résultats du déchiffrement dans plusieurs configurations de paramètres. Les auteurs proposent également des stratégies d'atténuation pour ces attaques et incluent une divulgation responsable dans l'article suggérant que les bibliothèques de chiffrement homomorphes ont déjà mis en œuvre des atténuations pour les attaques avant que l'article ne soit rendu public. De plus amples informations sur les stratégies d'atténuation mises en œuvre dans les bibliothèques de chiffrement homomorphes ont également été publiées.

Cryptosystèmes partiellement homomorphes

Dans les exemples suivants, la notation est utilisée pour désigner le cryptage du message . ${\mathcal {E}}(x)$ ${\style d'affichage x}$

RSA non rembourré

Si la clé publique RSA a un module et un exposant de chiffrement , alors le chiffrement d'un message est donné par . La propriété homomorphe est alors ${\style d'affichage n}$ ${\style d'affichage e}$ ${\style d'affichage m}$ ${\mathcal {E}}(m)=m^{e}\;{\bmod {\;}}n$

{\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=m_{1}^{e}m_{2 }^{e}\;{\bmod {\;}}n\\[6pt]&=(m_{1}m_{2})^{e}\;{\bmod {\;}}n\\ [6pt]&={\mathcal {E}}(m_{1}\cdot m_{2})\end{aligned}}

ElGamal

Dans le cryptosystème ElGamal , dans un groupe d'ordre cyclique avec générateur , si la clé publique est , où , et est la clé secrète, alors le cryptage d'un message est , pour certains, aléatoire . La propriété homomorphe est alors ${\style d'affichage G}$ ${\style d'affichage q}$ ${\style d'affichage g}$ ${\style d'affichage (G,q,g,h)}$ $h=g^{x}$ ${\style d'affichage x}$ ${\style d'affichage m}$ ${\mathcal {E}}(m)=(g^{r},m\cdot h^{r})$ $r\in \{0,\ldots ,q-1\}$

{\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=(g^{r_{1}},m_ {1}\cdot h^{r_{1}})(g^{r_{2}},m_{2}\cdot h^{r_{2}})\\[6pt]&=(g^{ r_{1}+r_{2}},(m_{1}\cdot m_{2})h^{r_{1}+r_{2}})\\[6pt]&={\mathcal {E} }(m_{1}\cdot m_{2}).\end{aligned}}

Goldwasser–Micali

Dans le cryptosystème Goldwasser-Micali , si la clé publique est le module et le non-résidu quadratique , alors le cryptage d'un bit est , pour certains, aléatoire . La propriété homomorphe est alors ${\style d'affichage n}$ ${\style d'affichage x}$ ${\style d'affichage b}$ ${\mathcal {E}}(b)=x^{b}r^{2}\;{\bmod {\;}}n$ $r\in \{0,\ldots ,n-1\}$

{\begin{aligned}{\mathcal {E}}(b_{1})\cdot {\mathcal {E}}(b_{2})&=x^{b_{1}}r_{1 }^{2}x^{b_{2}}r_{2}^{2}\;{\bmod {\;}}n\\[6pt]&=x^{b_{1}+b_{2 }}(r_{1}r_{2})^{2}\;{\bmod {\;}}n\\[6pt]&={\mathcal {E}}(b_{1}\oplus b_{ 2}).\end{aligned}}

où désigne l'addition modulo 2, (c'est -à- dire ou exclusif ). ${\style d'affichage \oplus }$

Benaloh

Dans le cryptosystème Benaloh , si la clé publique est le module et la base avec une taille de bloc de , alors le cryptage d'un message est , pour certains, aléatoire . La propriété homomorphe est alors ${\style d'affichage n}$ ${\style d'affichage g}$ ${\style d'affichage c}$ ${\style d'affichage m}$ ${\mathcal {E}}(m)=g^{m}r^{c}\;{\bmod {\;}}n$ $r\in \{0,\ldots ,n-1\}$

{\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=(g^{m_{1}}r_{ 1}^{c})(g^{m_{2}}r_{2}^{c})\;{\bmod {\;}}n\\[6pt]&=g^{m_{1} +m_{2}}(r_{1}r_{2})^{c}\;{\bmod {\;}}n\\[6pt]&={\mathcal {E}}(m_{1} +m_{2}\;{\bmod {\;}}c).\end{aligned}}

Paillier

Dans le cryptosystème Paillier , si la clé publique est le module et la base , alors le cryptage d'un message est , pour certains, aléatoire . La propriété homomorphe est alors ${\style d'affichage n}$ ${\style d'affichage g}$ ${\style d'affichage m}$ ${\mathcal {E}}(m)=g^{m}r^{n}\;{\bmod {\;}}n^{2}$ $r\in \{0,\ldots ,n-1\}$

{\begin{aligned}{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})&=(g^{m_{1}}r_{ 1}^{n})(g^{m_{2}}r_{2}^{n})\;{\bmod {\;}}n^{2}\\[6pt]&=g^{ m_{1}+m_{2}}(r_{1}r_{2})^{n}\;{\bmod {\;}}n^{2}\\[6pt]&={\mathcal { E}}(m_{1}+m_{2}).\end{aligned}}

Autres cryptosystèmes partiellement homomorphes

Cryptosystème Okamoto-Uchiyama
Système cryptographique Naccache-Stern
Système cryptographique Damgård-Jurik
Schéma de cryptage Sander-Young-Yung
Système cryptographique Boneh-Goh-Nissim
Cryptosystème Ishai-Paskin
Cryptosystème Castagnos–Laguillaumie

Cryptage entièrement homomorphe

Un cryptosystème qui prend en charge le calcul arbitraire sur les textes chiffrés est connu sous le nom de chiffrement entièrement homomorphe (FHE). Un tel schéma permet la construction de programmes pour toute fonctionnalité souhaitable, qui peuvent être exécutés sur des entrées cryptées pour produire un cryptage du résultat. Puisqu'un tel programme n'a jamais besoin de déchiffrer ses entrées, il peut être exécuté par une partie non fiable sans révéler ses entrées et son état interne. Les cryptosystèmes entièrement homomorphes ont de grandes implications pratiques dans l'externalisation des calculs privés, par exemple, dans le contexte du cloud computing .

Implémentations

Une liste des bibliothèques FHE open source mettant en œuvre des schémas FHE de deuxième génération et/ou de troisième génération est fournie ci-dessous. Une liste à jour des implémentations de chiffrement homomorphes est également maintenue par la communauté sur GitHub .

Il existe plusieurs implémentations open source de schémas de cryptage entièrement homomorphes de deuxième et troisième génération. Les implémentations du schéma FHE de deuxième génération fonctionnent généralement en mode FHE nivelé (bien que l'amorçage soit toujours disponible dans certaines bibliothèques) et prennent en charge un emballage efficace des données de type SIMD ; ils sont généralement utilisés pour calculer sur des nombres entiers cryptés ou des nombres réels/complexes. Les implémentations du schéma FHE de troisième génération s'amorcent souvent après chaque opération de porte booléenne, mais ont une prise en charge limitée de l'emballage et des calculs arithmétiques efficaces ; ils sont généralement utilisés pour calculer des circuits booléens sur des bits cryptés. Le choix d'utiliser un schéma de deuxième génération ou de troisième génération dépend des types de données d'entrée et du calcul souhaité.

Bibliothèques FHE
Nom	Développeur	BGV	CKKS	BFV	FHEW	Amorçage CKKS	TFHE	La description
HElib	IBM	Oui	Oui	Non	Non	Non	Non	Schéma BGV avec les optimisations GHS.
SCEAU Microsoft	Microsoft	Non	Oui	Oui	Non	Non	Non
PALISSADE	Consortium d'entrepreneurs et d'universitaires de la défense financés par la DARPA : New Jersey Institute of Technology , Duality Technologies , Raytheon BBN Technologies , MIT , Université de Californie, San Diego et autres.	Oui	Oui	Oui	Oui	Non	Oui	Bibliothèque de cryptographie sur réseau à usage général.
HEAAN	Université Nationale de Seoul	Non	Oui	Non	Non	Oui	Non
FHEW	Léo Ducas et Daniele Micciancio	Non	Non	Non	Oui	Non	Non
TFHE	Ilaria Chillotti, Nicolas Gama, Mariya Georgieva et Malika Izabachene	Non	Non	Non	Non	Non	Oui
FV-NFLlib	CryptoExperts	Non	Non	Oui	Non	Non	Non
NuFHE	NuCypher	Non	Non	Non	Non	Non	Oui	Fournit une implémentation GPU de TFHE.
Lattigo	EPFL-LDS	Non	Oui	Oui	Non	Oui	Non	Implémentation en Go avec leurs variantes distribuées permettant un calcul multi-parties sécurisé .

Cadres FHE
Nom	Développeur	FHEW	TFHE	Hélib	SCELLER	PALISSADE
E3	MoMA Lab à NYU Abu Dhabi	Oui	Oui	Oui	Oui	Oui
LE MOUTON	Institut Alan Turing	Non	Oui	Oui	Oui	Oui

Standardisation

Une norme communautaire pour le chiffrement homomorphe est maintenue par le groupe HomomorphicEncryption.org , un consortium ouvert industrie/gouvernement/université cofondé en 2017 par Microsoft , IBM et Duality Technologies . Le document standard actuel comprend des spécifications de paramètres sécurisés pour RLWE.

Voir également

Les références

Liens externes

Les références FHE de Daniele Micciancio
Les références FHE de Vinod Vaikuntanathan
"Alice et Bob dans l'espace chiffré" . Scientifique américain . Septembre 2012 . Récupéré le 08-05-2018 .
HElib , Microsoft SEAL , PALISADE , HEAAN , FHEW et TFHE (bibliothèques de chiffrement homomorphes open source)

Languages

In other projects