Chiffrement homomorphe

En cryptographie, un algorithme de chiffrement homomorphe est un système possédant des caractéristiques algébriques qui lui permettent de commuter avec certaines opérations mathématiques, c'est-à-dire qu'il permet d'effectuer lesdites opérations sur des données chiffrées sans avoir à les déchiffrer d'abord.

Le déchiffrement du résultat desdites opérations sur des données chiffrées donnera ainsi le même résultat qu'en ayant effectué ces opérations sur les données non chiffrées ; cette propriété permet de confier des calculs à un agent externe, sans que les données ni les résultats soient accessibles à cet agent.

Un exemple d'application d’un chiffrement homomorphe pour la délégation de calculs pourrait être le cas de figure où un utilisateur souhaiterait faire un calcul coûteux − dont il ne dispose pas nécessairement des ressources nécessaires pour l’exécuter − et aimerait faire appel à un service de cloud computing auquel il ne fait pas nécessairement confiance pour effectuer ses calculs.

Le chiffrement homomorphe est un domaine de recherche actif.

Définition

Étant donné $C$ l’espace des chiffrés, $M$ l'espace des messages, et $F$ l’espace des fonctions évaluables, on définit un chiffrement homomorphe sur $F$ le quadruplet d'algorithmes $({\mathcal {K}},{\mathcal {E}},{\mathcal {D}},{\mathsf {Eval}})$ tel que :

• ${\mathcal {K}}:\mathbb {N} \to PK\times SK$ : la fonction de génération des clefs ;
• ${\mathcal {E}}:{\mathcal {M}}\to {\mathcal {C}}$ est la fonction de chiffrement ;
• ${\mathcal {D}}:{\mathcal {C}}\to {\mathcal {M}}$ est la fonction de déchiffrement ;
• ${\mathsf {Eval}}:F\times {\mathcal {C}}\times {\mathcal {C}}\to {\mathcal {C}}$ est la fonction d'évaluation.

On souhaite avoir les propriétés suivantes :

• La correction : ${\mathcal {D}}({\mathcal {E}}(m))=m$ ;
• L’homomorphisme : $\forall f\in F,~{\mathcal {D}}({\mathsf {Eval}}(f,C_{1},C_{2}))={\mathsf {Eval}}(f,{\mathcal {D}}(C_{1}),{\mathcal {D}}(C_{2})))$.

Pour des raisons de simplicité de lecture, on a décrit $f$ comme une fonction d'arité 2, mais $F$ peut décrire un espace de fonctions d'arité quelconque.

Systèmes partiellement homomorphes

On dira d’un cryptosystème qu’il est partiellement homomorphe lorsque son espace de fonctions évaluables est une restriction de l’espace des fonctions calculables.

Par exemple, le cryptosystème à clé publique RSA est partiellement homomorphe vis-à-vis de la multiplication. En effet, si $(x,y)$ est un couple d'entiers, on a alors l’égalité suivante :

${\begin{aligned}{\mathcal {E}}(x)\cdot {\mathcal {E}}(y)&=x^{e}\cdot y^{e}{\bmod {N}}\\&=(x\cdot y)^{e}{\bmod {N}}\\&={\mathcal {E}}(x\cdot y)\end{aligned}}$

On peut donc dire que le cryptosystème RSA commute avec l’opération de multiplication des entiers dans l’anneau modulaire ℤ/Nℤ, où N est un semi-premier.

Systèmes totalement homomorphes

Dans la section précédente, les cryptosystèmes décrits ne permettent de réaliser qu’un seul type d'opération homomorphiquement, par exemple pour RSA il s'agit de la multiplication. Dans le cas où l’espace des fonctions évaluables est l’espace des fonctions calculables (définies par exemple sous la forme d’un circuit), on dit alors que le chiffrement est totalement homomorphe (Fully Homomorphic Encryption ou FHE en anglais).

Il existe aussi des constructions dites « presque homomorphes » (somewhat homomorphic en anglais) où les opérations d'additions et de multiplications sont possibles, mais pas nécessairement pour un nombre arbitraire d'opérations. Par exemple le système de Boneh-Goh-Nissim, à base de couplages, qui permet d'évaluer au plus une multiplication (pour un nombre arbitraire d'additions).

En 2017, les seuls cryptosystèmes qui supportent les évaluations homomorphes pour tous les circuits reposent sur les réseaux euclidiens. Ces constructions ont d'abord été des systèmes presque homomorphes (la profondeur multiplicative du circuit était bornée) avant que ce problème ne soit résolu par Craig Gentry à l'aide du réamorçage (bootstrap en anglais). Cette méthode repose sur l'idée suivante : puisque la qualité du chiffré se dégrade au fil des multiplications, si l'on est capable de déchiffrer homomorphiquement le chiffré, alors on obtient un nouveau chiffré nettoyé à l'évaluation homomorphe près. Un inconvénient de cette méthode est qu'elle reste encore coûteuse. Une partie de la recherche sur le chiffrement homomorphe en 2017 consiste à limiter l'impact de cette phase de réamorçage, soit en essayant de l'éviter au maximum, soit en en améliorant les performances pour le rendre moins rédhibitoire.

Applications

L'un des intérêts du chiffrement homomorphe est qu'un tiers peut faire des calculs sur les messages chiffrés sans les déchiffrer et que le résultat est utilisable, c'est-à-dire peut être décodé.

Histoire

L'un des acteurs majeurs du développement des chiffrements homomorphe est Craig Gentry.

Annexes

Articles connexes

• Calcul multipartite sécurisé
• Morphisme
• Malléabilité (cryptographie)

Bibliographie

• [Benhamouda et al. 2017] (en) Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu et Hang Zhou, « Optimization of Bootstrapping in Circuits », SODA,‎ 2017.
• [Delahaye 2015] Jean-Paul Delahaye, « Déléguer un calcul sans divulguer ses données », Pour la Science,‎ octobre 2015.
• [Ducas et Micciancio 2015] (en) Léo Ducas et Daniele Micciancio, « FHEW: Bootstrapping Homomorphic Encryption in less than a second », Eurocrypt,‎ 2015.
• [Gentry 2009] (en) Craig Gentry, Fully homomorphic encryption using ideal lattices (Thèse de doctorat), 2009, 196 p. (lire en ligne [PDF]).
• [Gentry, Sahai et Waters 2013] (en) Craig Gentry, Amit Sahai et Brent Waters, « Homomorphic Encryption from Learning with Errors : Conceptually-Simpler, Asymptotically-Faster, Attribute-Based », Crypto,‎ 2013 (lire en ligne).
• [Yi et al. 2014] (en) X. Yi et al., Homomorphic Encryption and Applications, Springer, 2014.
• [Boneh, Goh et Nissim 2005] (en) Dan Boneh, Eu-Jin Goh et Kobbi Nissim, « Evaluating 2-DNF Formulas on Ciphertexts », TCC,‎ 2005.