Brevet FR3048102A1 — publié le 20170825

MÉTHODE D'EXÉCUTION CONFIDENTIELLE D'UN PROGRAMME OPÉRANT SUR DES DONNÉES CHIFFRÉES PAR UN CHIFFREMENT HOMOMORPHE DESCRIPTION DOMAINE TECHNIQUE L'objet de la présente invention concerne le domaine des processeurs sécurisés et plus particulièrement du calcul sécurisé par chiffrement homomorphe. ÉTAT DE LA TECHNIQUE ANTÉRIEURE Le calcul sécurisé a fait récemment l'objet d'importantes recherches, fondées, notamment, sur des techniques de chiffrement homomorphe. On rappelle qu'un chiffrement homomorphe permet d'effectuer des opérations 15 (en pratique des opérations arithmétiques d'addition ou de multiplication et des opérations logiques équivalentes) sur des données sans jamais les dévoiler. Plus précisément, un chiffrement homomorphe est un chiffrement à clé asymétrique EncPk (de clé publique pk ) vérifiant la propriété suivante : 20 Encpk : X Y Dec e[Enc pk (a) G Encpk (b )1= a + b (1) où X est l'espace des messages clairs (dit plus simplement espace des clairs) et Y est 25 l'espace des messages chiffrés (dit plus simplement espace des chiffrés), + une opération additive dans l'espace des clairs conférant à X une structure de groupe, CI une opération dans l'espace des chiffrés conférant à Y une structure de groupe. On comprend ainsi que l'application de (X,+) dans ( Y, CI ) est un homomorphisme de groupes. Dec sk est la 10 3048102 2 fonction de déchiffrement correspondant à EncPk (où sk est la clé secrète de l'utilisateur). Il résulte de l'expression (1) qu'il est possible d'effectuer une opération additive entre deux clairs (a,b) à partir d'une opération correspondante entre leurs chiffrés ( EncPk (a), EncPk (b)). 5 Plus généralement, un chiffrement homomorphe peut être considéré comme un morphisme d'anneau entre l'espace des clairs (muni des opérations +,x) et l'espace des chiffrés (muni des opérations correspondantes CI , 0 ). On a alors les propriétés suivantes : Dec sk (EncPk (a + b)) = Dec sk (EncPk (a) O+ EncPk (b))= a + b (2-1) Dec sk (EncPk (axb))= Dec sk (EncPk (a) 0 EncPk (b))= axb (2-2) A l'aide des expressions (2-1) et (2-2), il est donc possible d'évaluer une fonction F quelconque, décomposable en opérations élémentaires d'addition et de multiplication, dans l'espace des chiffrés puis de déchiffrer le résultat. De la même façon, on peut évaluer une fonction logique F quelconque décomposable en opérations logiques élémentaires AND, OR et NOT dans l'espace des chiffrés. On convertit pour ce faire ces opérations logiques en opérations arithmétiques : AND(x, y) = xy (3-1) NOT (x) =1- x (3-2) OR(x, y) = NOT (AND (NOT (x),NOT (y)) =1- (1- x) (1- y) (3-3) et l'on calcule les membres de droite des équations (3-1) à (3-3) dans l'espace des chiffrés. Lorsqu'une fonction F est définie dans l'espace des clairs, on notera dans la suite F la fonction équivalente dans l'espace des chiffrés. Autrement dit : F (mi,..,mm) = Dec sk (F (Enc pk (mi) ,.., EncPk (mm))) (4) 3048102 3 où mi,..,mm sont les données en clair. Le terme de gauche correspond à une évaluation dans le domaine des clairs et i(Encpk (mi),..,Encpk (mm )) à une évaluation dans le domaine des chiffrés, dite aussi évaluation homomorphe. A une évaluation de F en clair on fait ainsi correspondre une évaluation homomorphe H.Evalpk(F). 5 Les méthodes de chiffrement homomorphes ont vu le jour avec la thèse de Craig Gentry intitulée « A fully homomorphic encryption scheme ». Les cryptosystèmes homomorphes actuels sont largement basés sur des chiffrements dérivés du problème LWE (Learning With Errors) ou RLWE (Ring Learning With 10 Errors). Dans ces cryptosystèmes, le chiffrement consiste à masquer avec du bruit un message. Réciproquement, le déchiffrement consiste à retirer ce bruit, ce qui est faisable si l'on connaît la clef privée du cryptosystème mais en revanche extrêmement difficile si celle-ci est inconnue. Les opérations homomorphes maintiennent naturellement ce masquage voire l'amplifie. Plus précisément, si l'on représente la fonction F précitée 15 selon une décomposition arborescente, chaque noeud de l'arbre correspondant à une opération arithmétique (ou logique) élémentaire, un bruit est ajouté à chaque niveau de l'arbre. On conçoit donc que si la fonction F (et donc F) présente une profondeur de calcul importante (c'est-à-dire un grand nombre de niveaux dans la représentation arborescente), le niveau de bruit dans le résultat d'évaluation de la fonction F puisse 20 devenir élevé. Lorsque le bruit dépasse un seuil (dépendant du schéma de chiffrement utilisé), il n'est plus garanti que le résultat soit encore déchiffrable. Lorsqu'un cryptosystème homomorphe permet d'effectuer n'importe quelle profondeur de calcul, il est dénommé entièrement homomorphe ou FHE (Fully 25 Homomorphic Encryption). A défaut, il est dit relativement homomorphe ou SHE (Somewhat Homomorphic). Le cryptosystème cité plus haut est entièrement homomorphe. L'idée de base de Gentry est d'utiliser une méthode de chiffrement possédant une certaine propriété de récursivité (bootstrappability) à savoir celle de pouvoir évaluer sa propre fonction de 3048102 4 déchiffrement en sus des opérations arithmétiques (ou logiques) de base. On peut alors construire une méthode de chiffrement FHE comprenant une série d'étapes de chiffrement élémentaires entrecoupées par des étapes de déchiffrement, chaque étape de déchiffrement permettant de faire repasser le niveau de bruit sous un seuil acceptable et 5 donc d'en éviter la divergence. A ce jour, les méthodes de chiffrement les plus efficaces sont la méthode BGV (Brakerski, Gentry, Vaikuntanathan) les schémas dérivés de ATV (Alt-Lôpez, Tromer, Vaikuntanathan) et de GHW (Gentry Halevi Waters). Leur sécurité théorique est basée sur le problème LWE ou RLWE. 10 On trouvera une description d'un schéma de chiffrement, dérivé du schéma ATV, dénommé YASHE, dans l'article de J.W. Bos et al. intitulé « Improved security for a ringbased fully homomorphic encryption scheme » publié dans Cryptology ePrint Archive, Report 2013/075, 2013. De même, on trouvera une description d'un schéma de chiffrement dérivé du schéma BGV, dénommé FV) dans l'article de Jungfen Fan et al. 15 intitulé « Somewhat practical fully homomorphic encryption », publié dans Cryptology ePrint Archive, Report 2012/144, 2012. On rappellera ici succinctement le principe du schéma de chiffrement YASHE. On considère un entier non nul (qE Z* ) et on note [x]q la valeur de x modulo q , autrement dit l'entier unique de l'intervalle 1-q12,q12] tel qu'il existe qe Z, avec 20 x=kq-r[x], ([x] ,e Z / qZ ). On définit l'anneau R =Z[X]/ (P(X)) comme l'anneau quotient des polynômes à coefficients dans Z et (P(X)) l'idéal engendré par le polynôme P(X) . Le polynôme P(X) est choisi irréductible (par exemple P(X) = Xd +1 avec d = 2n ) et donc R est un corps. On note Rq l'anneau des polynômes de R dont les coefficients appartiennent à Z / qZ . On note xe, et %key deux distributions distinctes 25 sur Rq, par exemple deux distributions gaussiennes de variances différentes et u (Rq) la distribution uniforme sur Rq. On considère enfin un entier t REVENDICATIONS1. Méthode d'exécution d'un programme opérant sur des données chiffrées au moyen d'un chiffrement homomorphe, ledit programme comprenant une pluralité d'instructions, chaque instruction pouvant être représentée par une fonction desdites données, l'exécution de ladite instruction comprenant une évaluation homomorphe (320) par un processeur de ladite fonction à partir desdites données chiffrées, caractérisée en ce que : (a) le résultat de ladite évaluation est masqué par une première opération sommation (350) avec une séquence aléatoire préalablement chiffrée (340) par ledit chiffrement homomorphe, ladite première opération de sommation dans le domaine des chiffrés correspondant à une opération de sommation modulo 2 dans le domaine des données en clair ; (b) le résultat de ladite évaluation ainsi masqué est d'abord déchiffré (360), puis rechiffré (370) au moyen dudit chiffrement homomorphe ; (c) le résultat obtenu à l'étape (b) est démasqué par une seconde opération de sommation (380) avec ladite séquence aléatoire préalablement chiffrée par ledit chiffrement homomorphe, ladite seconde opération de sommation dans le domaine des chiffrés correspondant à une opération de sommation modulo 2 dans le domaine des données en clair, le résultat de la seconde opération de sommation étant stocké dans une zone mémoire. 2. Méthode d'exécution d'un programme selon la revendication 1, caractérisée en ce que les étapes (a), (b) et (c) sont effectuées par un coprocesseur distinct dudit processeur. 3. Méthode d'exécution d'un programme selon la revendication 1 ou 2, caractérisée en ce que lesdites instructions sont stockées sous la forme de fonctions 3048102 14 exprimées dans le domaine des données en clair, lesdites instructions étant traduites lors du démarrage (boot) en exprimant lesdites fonctions dans le domaine des données chiffrées, avant d'être stockées dans une mémoire programme (315). 5 4. Méthode d'exécution d'un programme selon la revendication 1 ou 2, caractérisée en ce que lesdites instructions sont stockées dans une mémoire programme sous la forme de fonctions exprimées dans le domaine des données en clair, lesdites instructions étant traduites à la volée, au fur et à mesure de leur exécution, en exprimant lesdites fonctions dans le domaine des données chiffrées. 10 5. Méthode d'exécution d'un programme selon l'une des revendications précédentes, caractérisée en ce que le chiffrement est un chiffrement entièrement homomorphe. 15 6. Méthode d'exécution d'un programme selon l'une des revendications précédentes, caractérisée en ce que le chiffrement est un chiffrement relativement homomorphe. 7. Méthode d'exécution d'un programme selon la revendication 6, caractérisée 20 en ce que le chiffrement est un chiffrement BGV. 8. Méthode d'exécution d'un programme selon la revendication 6, caractérisée en ce que le chiffrement est un chiffrement AN. 25 9. Méthode d'exécution d'un programme selon la revendication 6, caractérisée en ce que le chiffrement est un chiffrement YASHE.