FR 3150381 A1 20241227 FR 2306359 A 20230621 Procédé d’extraction d’un élément chiffré homomorphe d’une liste chiffrée homomorphe et procédé d’insertion d’un élément chiffré homomorphe dans une liste chiffré homomorphe Procédé d’obtention (100) d’un élément chiffré homomorphe d’une liste chiffrée homomorphe , les éléments de la liste appartenant à un tore T, le procédé comprenant les étapes suivantes : Obtenir un chiffré homomorphe (101) d’un polynôme Q(X), Q(X) étant une agrégation des éléments de la liste ; Obtenir un chiffré homomorphe (102) d’un monôme , étant une fonction de l’indice associé à l’élément à obtenir ; Déterminer un polynôme chiffré homomorphe (103) en tant que produit modulaire homomorphe entre et ; Extraire le coefficient k (104) du polynôme chiffré homomorphe , k étant déterminé sur la base du polynôme Q(X) et de la fonction utilisée dans le monôme P(X), le coefficient k du polynôme chiffré homomorphe correspondant à l’élément chiffré homomorphe à obtenir. Figure à publier avec l’abrégé : Figure 1 Procédé d’extraction d’un élément chiffré homomorphe d’une liste chiffrée homomorphe et procédé d’insertion d’un élément chiffré homomorphe dans une liste chiffré homomorphe Le domaine technique est celui des méthodes, dispositifs et systèmes de cryptographie homomorphe. Plus particulièrement, le domaine de l’invention est celui de la manipulation de listes chiffrées homomorphes. ARRIERE-PLAN TECHNOLOGIQUE La cryptographie homomorphe, qui permet d'effectuer des calculs ou des traitements de données sur des données chiffrées, sans les déchiffrer au préalable, a suscité beaucoup d'attention dernièrement. En effet, le traitement numérique de données personnelles est devenu omniprésent dans notre vie quotidienne. La protection de la confidentialité de ces données, et de la vie privée des individus concernés est donc devenue critique, car ces données personnelles ont tendance à circuler de plus en plus dans les environnements en systèmes digitaux que nous utilisons au quotidien. Dans ce contexte, les techniques de chiffrement et traitement homomorphe apparaissent comme une solution très prometteuse, car elles permettent de traiter des données tout en préservant de manière particulièrement sûre l'anonymat et le caractère privé de ces données, ces dernières n'étant pas déchiffrées pendant leur traitement. La cryptographie homomorphe peut être basée sur le schéma de cryptage dit "apprentissage avec erreur" (« learning with errors » ou LWE, en anglais), dans lequel le message crypté est dérivé du message non crypté μ selon la formule suivante : b=μ+e+a.s, où : s est une clé secrète, a est un vecteur choisi au hasard, pour projeter la clé secrète s, et e est une composante de bruit aléatoire, ajoutée à μ+a.s. Pour décrypter le message, une personne possédant la clé secrète s peut calculer la quantité b-a.s (égale à μ+e), puis arrondir le résultat pour supprimer la composante de bruit e et retrouver le message μ. Bien entendu, le terme de bruit e doit être et rester suffisamment petit si l'on veut pouvoir récupérer le message μ. Les méthodes de cryptographie homomorphe répondent donc, entre autres, à l’enjeu technique qui consiste à permettre : à un serveur de services et traitements, externe, généralement distant, d’effectuer des opérations « en aveugle » sur des données chiffrées, sans les déchiffrer, ce serveur ne disposant d’ailleurs pas de la clef nécessaire pour déchiffrer les données, les données, chiffrées, étant fournies par une autre entité, distincte (un client, au sens informatique), qui, elle, dispose de la clef de chiffrement. Ces opérations de traitement de données peuvent consister à effectuer des opérations individuelles, donnée par donnée, pour les mettre en forme ou les filtrer par exemple. Elles peuvent aussi concerner des opérations de comparaison entre données, de tri ou de regroupement. La manipulation d’éléments chiffrés homomorphes peut être complexe et requiert le développement de méthodes permettant de réaliser les opérations mathématiques dans l’espace des chiffrés. Parmi les méthodes connues, également appelées primitives cryptographiques, nous pouvons citer les techniques suivantes (les symboles bra et ket indiquent un chiffré homomorphe de la quantité entre les symboles) : Addition homomorphe : si et sont deux chiffrés homomorphes de deux éléments et appartenant au tore T , il est possible d’obtenir la somme des chiffrés en utilisant l’addition homomorphe = Soustraction homomorphe : si et sont deux chiffrés homomorphes de deux éléments et appartenant au tore T , il est possible d’obtenir la différence des chiffrés en utilisant la soustraction homomorphe = Addition homomorphe de polynômes : si et sont deux chiffrés homomorphes de deux éléments et appartenant à l’anneau de polynômes de degré N, il est possible d’obtenir le polynôme somme dans l’espace des chiffrés en utilisant l’addition homomorphe des polynômes = Soustraction homomorphe de polynômes : si et sont deux chiffrés homomorphes de deux éléments et appartenant à l’anneau de polynômes de degré N, avec par exemple N une puissance de 2 , il est possible d’obtenir le polynôme différence dans l’espace des chiffrés en utilisant la soustraction homomorphe des polynômes : = Produit modulaire homomorphe : Si et sont deux chiffrés homomorphes de deux éléments et appartenant à l’anneau de polynômes de degré N, il est possible d’obtenir le polynôme produit dans l’espace des chiffrés en utilisant le produit modulaire homomorphe : Ces primitives cryptographiques permettent donc de réaliser plusieurs opérations mathématiques dans l’espace des chiffrés homomorphes, en reproduisant les opérations mathématiques standard effectuées dans l’espace en clair. Cependant, la cryptographie homomorphe a été très peu appliquée à la manipulation de listes ou ensembles chiffrées. Certaines méthodes de chiffrement homomorphe des éléments d’une liste ont été récemment proposées, par exemple dans l’article « Faster Amortized FHEW bootstrapping using Ring » de G. De Micheli et al., https://eprint.iacr.org/2023/112, 2023). Toutefois, ces techniques portent sur le chiffrement homomorphe d’éléments individuels d’une liste, sans donner des indications concernant par exemple des manipulations complètes de listes homomorphes. Il existe donc un besoin de développer des techniques permettant de réaliser des opérations complexes sur les listes chiffrée homomorphe, par exemple en extrayant un élément chiffré homomorphe d’une liste chiffrée homomorphe ou encore en modifiant une liste chiffrée homomorphe par suppression ou ajout d’un élément chiffré homomorphe. Par ailleurs, il est nécessaire de développer des méthodes de manipulations de listes chiffrées homomorphes qui soient fiables, rapides et peu coûteuses en termes de ressources de calcul. Pour résoudre au moins partiellement les problèmes évoqués précédemment, un premier aspect de l’invention concerne un procédé d’extraction d’un élément chiffré homomorphe , d’une liste chiffrée homomorphe , l’élément chiffré homomorphe étant associé à un indice , étant compris entre 0 et N-1, les éléments de la liste appartenant à un tore T , la liste et l’indice étant chiffrés à l’aide d’une même clé, ledit procédé comprenant les étapes suivantes : Obtenir un chiffré homomorphe d’un polynôme Q(X), Q(X) étant une agrégation des éléments de la liste , j étant compris entre 0 et N-1, chaque coefficient du polynôme étant une combinaison linéaire d’éléments de la liste , appartenant à un espace quotient , étant un espace des polynômes de degré N-1 avec coefficients à valeurs dans le tore T et étant un polynôme cyclotomique d’ordre M ; Obtenir un chiffré homomorphe d’un monôme , étant une fonction de l’indice associé à l’élément à obtenir, appartenant à un espace quotient , étant un ensemble de polynômes à coefficients dans les nombres entiers ; Déterminer un polynôme chiffré homomorphe en tant que produit modulaire homomorphe entre et ; Extraire le coefficient k du polynôme chiffré homomorphe , k étant déterminé sur la base du polynôme Q(X) et de la fonction utilisée dans le monôme P(X), le coefficient k du polynôme chiffré homomorphe correspondant à l’élément chiffré homomorphe à obtenir. Les symboles bra et ket indiquent un chiffré homomorphe d’une quantité. Par exemple, le symbole indique un chiffré homomorphe d’un entier . Par produit modulaire homomorphe, également indiqué par le symbole , il est entendu une opération entre deux chiffrés homomorphes, et , telle que = . En d’autres termes, le produit modulaire homomorphe reproduit, dans l’espace des chiffrés, le résultat d’un produit de deux éléments en clair. Par chiffré homomorphe de , il est entendu un chiffré homomorphe de la quantité , étant compris entre 0 et M-1. Par polynôme cyclotomique d’ordre M, il est entendu, de façon connue, le polynôme unitaire dont les racines complexes sont exactement les racines primitives M-ièmes de l’unité. L’ordre M est défini par M = t α avec t premier quelconque et α un nombre entier quelconque. Par agrégation, ou « packing » selon la terminologie anglaise, il est entendu une représentation de la liste L sous la forme d’un polynôme. Dans le cas du procédé selon un aspect de l’invention chaque coefficient du polynôme Q(X) représentant la liste L comprend une combinaison linéaire d’éléments de la liste L. Chaque combinaison linéaire peut comprendre un ou plusieurs éléments de la liste L. Le procédé selon le premier aspect de l’invention est une méthode générale pour extraire un élément chiffré homomorphe d’une liste chiffré homomorphe à partir du chiffré homomorphe de l’indice correspondant à l’élément d’intérêt . L’extraction de l’élément chiffré homomorphe est réalisée de façon complétement homomorphe, à savoir sans besoin de déchiffrer les éléments de la liste ou l’indice. En d’autres termes, le procédé selon le premier aspect de l’invention réalise une fonction de type extracteur homomorphe, ou « homomorphic getter » selon la terminologie anglaise. Il est important de noter que le procédé selon le premier aspect de l’invention est une méthode générale qui peut être mise en œuvre pour n’importe quelle liste d’éléments appartenant au tore T et indexés selon un entier . Le procédé d’extraction selon un aspect de l’invention permet donc d’extraire un élément chiffré homomorphe d’une liste chiffrée homomorphe sans besoins de déchiffrer l’élément ou la liste. Cela est possible grâce à la préparation préalable du polynôme Q(x) en tant qu’agrégation d’éléments de la liste L et du monôme P(X) représentant l’indice i correspondant à l’élément à extraire. En d’autres termes, le polynôme chiffré est une représentation chiffrée de la liste L et le monôme chiffré est une représentation chiffrée de l’indice i. Il est important de noter que et peuvent être obtenus de façon homomorphe à partir des éléments chiffrés de la liste et de l’indice chiffré sans besoin de déchiffrement préalable. En effet, un des avantages du procédé selon le premier aspect de l’invention est de pouvoir extraire un élément chiffré de la liste chiffrée sans besoin de déchiffrement de la liste ou de l’indice associé à l’élément à extraire. Le polynôme produit contient alors l’élément chiffré à extraire sous la forme de son k-ième coefficient. Le coefficient k est déterminé à partir de l’agrégation utilisée pour obtenir le polynôme Q et de la fonction γ utilisée dans le monôme P(X). En d’autres termes, la construction préalable de P(X) et Q(X) identifie univoquement le coefficient k de contenant l’élément de la liste chiffrée homomorphe à extraire. Les inventeurs ont donc mis au point une technique pour l’extraction d’un élément d’une liste chiffré homomorphe qui est à la fois simple et rapide à mettre en œuvre et qui repose sur la préparation préalable de l’agrégation Q(X) et du monôme P(X) représentant respectivement la liste L et l’indice i associé à l’élément chiffré homomorphe à extraire de la liste. Dans un ou plusieurs modes de réalisation : chaque coefficient du polynôme Q(X) est une combinaison linéaire obtenue selon la formule suivante avec , , et le coefficient du polynôme correspondant à l’élément chiffré homomorphe à extraire est le coefficient k = 0, γ étant égale à . Cette construction du polynôme Q(X) permet de positionner l’élément de la liste à extraire en correspondance du coefficient k = 0 du polynôme produit . Par ailleurs, ce choix pour les coefficients du polynôme Q(X) permet d’extraire efficacement le chiffré homomorphe de l’élément de la liste souhaité pour une large gamme de valeurs des paramètres t, M et γ. En effet, les inventeurs ont réussi à trouver des constructions du polynôme Q(X) et du monôme P(X) qui sont particulièrement adaptées pour l’extraction de l’élément . Des telles constructions sont non évidentes pour l’homme du métier, d’autant plus que si l’agrégation Q(X) et le polynôme P(X) ne sont pas opportunément choisis, il y a une forte probabilité de tomber sur une combinaison linéaire d’éléments de la liste et non pas sur l’élément d’intérêt . Dans un ou plusieurs modes de réalisation, le procédé d’extraction selon le premier aspect de l’invention peut en outre comprendre une étape de recevoir l’indice et la liste , et étant obtenus à partir des chiffrés et . Dans un ou plusieurs modes de réalisation : Le polynôme chiffré homomorphe est obtenu à partir de la liste comprenant les éléments , étant un entier compris entre 0 et , le polynôme chiffré homomorphe étant sous la forme d’un chiffré homomorphe de , étant une fonction à valeurs dans l’ensemble des nombres entiers compris entre 0 et N-1 et M = 2 α ; Le monôme chiffré homomorphe est obtenu à partir de l’indice , étant sous la forme d’un chiffré homomorphe de , étant une fonction à valeurs dans l’ensemble des nombres entiers compris entre 0 et N-1 ; Le polynôme chiffré homomorphe est obtenu selon la formule ; Le coefficient k du polynôme à extraire est donné par . Par chiffré homomorphe de , il est entendu un chiffré homomorphe de la quantité . Ce mode de réalisation illustre un exemple de coopération entre l’agrégation d’éléments de la liste sous forme de polynôme Q(X) et le chiffrement du monôme P(X). Cela est possible grâce au fait que les éléments de la liste sont chiffrés en tant que coefficients d’un polynôme de degré N-1, la liste étant un chiffré homomorphe de . Dans ce cas les coefficients du polynôme Q(X) sont simplement les éléments de la liste L (les combinaisons linéaires comprennent chacune un seul élément). La fonction est une fonction de l’entier j à valeurs dans les nombres entiers compris entre 0 et N-1. La fonction est par exemple une fonction de type , avec un entier. Un autre exemple de fonction est avec impair. Par ailleurs, l’indice i est le chiffré homomorphe de . La fonction est une fonction de l’entier i à valeurs dans les nombres entiers compris entre 0 et N-1. La fonction est par exemple une fonction de type , avec un entier. Un autre exemple de fonction est avec impair. En combinant ces deux techniques de chiffrement homomorphe, les inventeurs ont découvert qu’il est possible d’extraire l’élément recherché en calculant le produit modulaire homomorphe . Avantageusement, ce produit modulaire homomorphe résulte en une rotation des coefficients du polynôme Q(X) de départ. Le coefficient d’intérêt, à savoir l’élément de la liste à extraire, devient alors le coefficient d’ordre du polynôme déterminé à l’aide du produit modulaire homomorphe. Il est donc possible d’extraire l’élément de la liste chiffrée homomorphe en calculant le coefficient d’ordre du polynôme . Selon un ou plusieurs modes de réalisation, les fonctions et sont choisies comme étant la fonction identité, à savoir et . Le coefficient à extraire est alors simplement le coefficient d’ordre zéro du polynôme . L’extraction d’un coefficient d’ordre donné d’un polynôme chiffré est une primitive connue en cryptographie homomorphe. De plus, l’extraction du coefficient zéro d’un chiffré homomorphe d’un polynôme est particulièrement simple à mettre en œuvre. L’avoir associé d’une part le chiffrement des éléments de la liste en tant que coefficients d’un polynôme de degré N-1 et d’autre part le chiffrement de l’exposant i en tant qu’exposant d’un monôme est loin d’être évident. La combinaison de ces caractéristiques n’a jamais été utilisée en cryptographie homomorphe et permet d’obtenir une méthode générale pour l’extraction d’un élément chiffré homomorphe d’une liste chiffrée homomorphe. Avantageusement, l’utilisation de ces deux chiffrements homomorphes différents pour les éléments de la liste et l’indice permet de simplifier l’extraction de l’élément recherché, qui peut être effectuée en tant que calcul du coefficient zéro d’un polynôme obtenu par produit modulaire homomorphe. L’extraction d’un élément d’une liste chiffrée homomorphe grâce au procédé selon le premier aspect de l’invention est donc générale, fiable et rapide. Selon un mode de réalisation du procédé selon le premier aspect de l’invention : La polynôme chiffré homomorphe est obtenu selon la formule suivante ; Le monôme chiffré homomorphe est déterminé selon la formule suivante Définition de chiffrement T LWE Par chiffrement TLWE, « Torus Learning with Errors » selon la terminologie anglaise, on entend une méthode connue de chiffrement homomorphe d’un élément t appartenant au tore T . Le chiffré est déterminé selon la formule suivante : Avec Le vecteur s est la clé de chiffrement, le vecteur a est un vecteur de projection de la clé s, ou masque, et la quantité e est un bruit aléatoire. Définition de chiffrement TRLWE Par chiffrement TRLWE, « Torus Ring Learning With Errors » selon la terminologie anglaise, on entend une méthode connue de chiffrement homomorphe d’un polynôme appartenant à l’anneau de polynômes , où C est un polynôme cyclotomique et par exemple avec N étant une puissance de 2. On entend ici par anneau de polynômes l’espace des polynômes de degré N à coefficients dans le tore T .. La clé de chiffrement s et son vecteur de projection a sont des vecteurs appartenant à l’ensemble . Le chiffré est déterminé selon la formule suivante : Avec Le polynôme est un polynôme du même degré que dont les coefficients représentent le bruit aléatoire ajouté au chiffré du message . Par exemple les coefficients de e(X) peuvent avoir une distribution gaussienne centrée autour de zéro avec une variance σ 2 . Définition de chiffrement TR GSW Par chiffrement TRGSW, “Gentry, Sahai, Waters Torus Ring encryption” selon la terminologie anglaise, on entend une méthode connue de chiffrement homomorphe d’un polynôme m(X) appartenant à l’anneau de polynômes avec une clé s, s étant un vecteur appartenant à l’ensemble . Le chiffré TRGSW de m est alors déterminé de la façon suivante : avec , où z j , j=1…l(K+1), sont l(K+1) version chiffrées de 0, la valeur nulle 0 étant chiffrée avec s’, l étant un nombre entier positif donné; et est une matrice dont la dimension est et dont les coefficients appartiennent au tore T , étant égale à : avec B étant un nombre entier supérieur ou égal à 2. Définition de produit modulaire homomorphe entre un TR G SW et un TRLW E On entend par produit modulaire homomorphe une opération entre deux chiffrés homomorphes, et , telle que = . En d’autres termes, le produit modulaire homomorphe reproduit, dans l’espace des chiffré, le résultat d’un produit entre éléments en clair. La méthode de calcul du produit modulaire homomorphe dépend des propriétés des éléments chiffrés à multiplier. Par exemple dans le cas d’un produit entre et on obtient : L’avantage de ce mode de réalisation et que le calcul du produit modulaire homomorphe peut être réalisé de façon connue, en utilisant la technique pour le produit d’une quantité chiffrée TRLWE et d’une quantité chiffrée TRGSW. Le polynôme produit est alors un chiffré TRLWE dont le coefficient d’ordre zéro est l’élément de la liste à extraire. Un autre aspect de l’invention porte sur un programme d’ordinateur comprenant des instructions exécutables par un processeur et conçues pour mettre en œuvre un procédé selon le premier aspect de l’invention lorsque ces instructions sont exécutées par ledit processeur. Un deuxième aspect de l’invention porte sur un procédé d’insertion d’un élément chiffré homomorphe dans une liste chiffrée homomorphe de sorte à obtenir une liste chiffrée homomorphe modifiée , dans lequel : L’élément chiffré homomorphe est obtenu par chiffrement homomorphe d’un élément en clair appartenant à un tore T ; La liste chiffrée homomorphe est obtenue à partir d’une liste en clair comprenant les éléments , étant un entier compris entre 0 et , N étant un nombre entier supérieur ou égal à 1, les éléments appartenant au tore T , la liste chiffrée homomorphe étant sous la forme d’un chiffré homomorphe de ; La liste chiffrée homomorphe modifiée est un chiffré homomorphe d’une liste en clair comprenant les éléments pour et pour , étant un entier compris entre 0 et N-1 ; Ledit procédé comprenant les étapes suivantes : Recevoir l’élément chiffré homomorphe , la liste chiffrée homomorphe et un chiffré homomorphe sous la forme d’un chiffré homomorphe de , , et étant chiffrés à l’aide d’une même clé s ; Extraire, conformément au procédé selon le premier aspect de l’invention, l’élément de la liste chiffrée homomorphe ; Calculer de façon homomorphe la différence ; Obtenir un chiffré homomorphe de la quantité ; Obtenir la liste chiffrée homomorphe modifiée en calculant de façon homomorphe l’addition . Les opérations soustraction homomorphe, notée par le symbole , et addition homomorphe, notée par le symbole , sont des primitives cryptographiques connues. Dans le cas de la différence , le symbole indique la différence entre deux éléments appartenant au tore T . Dans le cas de la somme , le symbole indique la somme entre deux polynômes dont les coefficients sont à valeur dans le tore T ou à l’espace . Le procédé selon le deuxième aspect de l’invention permet d’introduire un chiffré homomorphe dans une liste chiffrée homomorphe . Ce procédé, en combinaison avec le procédé selon le premier aspect de l’invention, fournit une technique complète de manipulation de listes chiffrées homomorphes. En d’autres termes grâce aux procédés selon le premier et le deuxième aspect de l’invention, la lecture d’une liste, à savoir l’extraction d’un des ses éléments, ainsi que sa modification, à savoir le remplacement d’un de ses éléments, sont possibles. Dans un ou plusieurs modes de réalisation du procédé selon le deuxième aspect de l’invention, l’étape d’extraire l’élément de la liste chiffrée homomorphe est réalisée à l’aide du procédé selon le premier aspect de l’invention. Dans un ou plusieurs modes de réalisation du procédé selon le deuxième aspect de l’invention : La liste chiffrée homomorphe est un chiffré homomorphe calculé selon la formule ; L’élément chiffré homomorphe est calculé selon la formule ; Le chiffré homomorphe est calculé selon la formule . Dans un ou plusieurs modes de réalisation du procédé selon le quatrième aspect de l’invention, l’étape d’obtenir un chiffré homomorphe de la quantité comprend : Calculer un chiffré homomorphe de la quantité selon la formule ; Calculer le produit modulaire homomorphe selon la formule ; Obtenir, à partir de la quantité , un chiffré homomorphe de la quantité sous la forme de . Si la fonction est du type et , et étant premiers avec M, l’étape d’obtenir la quantité est réalisée en appliquant un automorphisme. Dans un ou plusieurs modes de réalisation du procédé d’insertion selon le deuxième aspect de l’invention, les fonctions et sont la fonction identité de sorte à avoir et . Un autre aspect de l’invention porte sur un programme d’ordinateur comprenant des instructions exécutables par un processeur et conçues pour mettre en œuvre un procédé selon le deuxième aspect de l’invention lorsque ces instructions sont exécutées par ledit processeur. Un troisième aspect de l’invention comprend un serveur de traitement cryptographique pour le traitement d’une liste chiffrée homomorphe comprenant un module de communication et un module de calcul : Le module de communication étant configuré pour recevoir, de la part d’une entité externe au serveur, un indice chiffré homomorphe ou ; Le module de calcul étant configuré pour extraire, d’une liste chiffrée homomorphe , un élément chiffré homomorphe associé à l’indice chiffré homomorphe conformément au procédé selon le premier aspect de l’invention. Selon un mode de réalisation, le module de calcul du serveur de traitement selon le premier aspect de l’invention détermine le produit modulaire homomorphe et en extrait opportunément choisi de sorte à obtenir un chiffré de l’élément de la liste recherché. Selon un mode de réalisation, le module de communication est en outre configuré pour recevoir, de la part d’une entité externe au serveur, un élément chiffré homomorphe . Selon un mode de réalisation, le module de calcul est programmé pour introduire l’élément chiffré homomorphe dans une liste chiffrée homomorphe conformément au procédé selon le deuxième aspect de l’invention. Un quatrième aspect de l’invention porte sur un client configuré pour chiffrer l’indice sous la forme d’indice chiffré homomorphe ou et/ou le message sous la forme d’un message chiffré homomorphe et pour communiquer l’indice chiffré homomorphe ou et/ou le message chiffré homomorphe au serveur selon le troisième aspect de l’invention via un canal de communication. L’indice chiffré est par exemple sous la forme d’un monôme chiffré . Un cinquième aspect de l’invention porte sur un système cryptographique comprenant : Un serveur de traitement cryptographique selon le troisième aspect de l’invention ; Un client selon le quatrième aspect de l’invention. Grâce au système cryptographique selon le cinquième aspect de l’invention le serveur de traitement cryptographique ne reçoit que des quantités chiffrées homomorphes et réalise l’extraction d’un élément de la liste sans besoin d’effectuer un déchiffrement. La présente technologie et ses différentes applications seront mieux comprises à la lecture de la description qui suit et à l’examen des figures qui l’accompagnent. BREVE DESCRIPTION DES FIGURES Les figures sont présentées à titre indicatif et nullement limitatif. illustre un ordinogramme d’un mode de réalisation du procédé d’extraction d’un élément chiffré homomorphe d’une liste chiffrée homomorphe selon le premier aspect de l’invention. illustre schématiquement l’agrégation d’une liste selon un mode de réalisation le premier aspect de l’invention. illustre schématiquement l’extraction d’un élément chiffré homomorphe d’une liste chiffrée homomorphe selon un mode de réalisation du premier aspect de l’invention. illustre un ordinogramme d’un mode de réalisation du procédé d’insertion d’un élément chiffré homomorphe dans une liste chiffrée homomorphe selon le deuxième aspect de l’invention. illustre schématiquement certaines étapes d’un mode de réalisation du procédé selon le deuxième aspect de l’invention. illustre schématiquement l’insertion d’un élément chiffré homomorphe dans une liste chiffrée homomorphe selon un mode de réalisation du procédé selon le deuxième aspect de l’invention. illustre un mode de réalisation d’un système cryptographique pour le traitement d’une liste chiffrée homomorphe selon un aspect de l’invention. DESCRIPTION DETAILLEE La figure 1 [Fig. 1] représente schématiquement un mode de réalisation du procédé 100 d’extraction d’un élément chiffré homomorphe d’une liste chiffré homomorphe . Le procédé 100 selon le mode de réalisation illustré à la figure 1 comprend une étape 101 d’obtenir un chiffré homomorphe d’un polynôme Q(X). Le polynôme Q(X) appartient à l’ensemble . est un espace des polynômes de degré N-1 avec coefficients à valeurs dans le tore T . est un polynôme cyclotomique d’ordre M et degré N. Chaque coefficient du polynôme Q(X) est une combinaison linéaire d’éléments de la liste L. Le procédé 100 tel qu’illustré à la figure 1 comprend en outre une étape 102 d’obtenir un chiffré homomorphe d’un monôme , étant une fonction de l’indice associé à l’élément à obtenir. Le monôme P(X) appartient à , étant un ensemble de polynômes à coefficients dans les nombres entiers. Lors de l’étape 103, le polynôme chiffré homomorphe est déterminé en tant que produit modulaire homomorphe entre et . L’étape d’extraction 104 du coefficient k de permet d’obtenir l’élément à extraire de la liste . Le monôme chiffré homomorphe est obtenu à partir d’un indice en clair , étant un entier compris entre 0 et . Selon un mode de réalisation, le monôme chiffré homomorphe est obtenu en tant que chiffré homomorphe de la quantité . Selon un mode de réalisation, le polynôme chiffré homomorphe est obtenue à partir de la liste en clair comprenant les éléments , étant un entier compris entre 0 et . Les éléments appartiennent au tore T . Dans ce mode de réalisation le polynôme chiffré homomorphe est obtenu en tant que chiffré homomorphe de la quantité . En d’autres termes, les éléments de la liste en clair sont encodés en tant que coefficients d’un polynôme qui est ensuite chiffré de façon homomorphe. Dans ce mode de réalisation, le produit modulaire homomorphe calculé lors de l’étape 103 est calculé selon la formule suivante . La quantité est un polynôme de degré N avec coefficients à valeur dans le tore T . Il est donc possible d’obtenir un chiffré homomorphe de l’élément , à savoir , lors d’une étape 104 d’extraction du coefficient d’ordre du polynôme . Les figures 2a et 2b illustrent plus en détail certaines étapes d’un mode de réalisation du procédé 100 selon le premier aspect de l’invention. Selon le mode de réalisation illustré à la figure 2a, la liste en clair est un ensemble trié d’éléments , j étant compris entre 0 et N-1. Dans ce cas, l’élément encadré correspond à l’élément que l’on veut extraire de la liste. Le polynôme chiffré homomorphe est obtenu en tant que : = ( + X + + … ) Le monôme chiffré homomorphe de l’indice est obtenu selon la formule . Dans ce cas la fonction est la fonction identité, . La fonction est elle aussi choisie comme étant égale à la fonction identité, . Le choix d’un chiffrement TRLWE pour le polynôme Q encodant les éléments de la liste et d’un chiffrement TRGSW pour le monôme P encodant l’indice permet de calculer le produit modulaire homomorphe en tant que : ( + + … ( + + … ) Comme il est illustré à la figure 2b, le terme d’intérêt devient, dans le polynôme produit C, le coefficient zéro. Il est donc possible d’extraire un chiffré homomorphe de l’élément d’intérêt en tant que coefficient zéro du polynôme résultant du produit modulaire homomorphe. La figure 3 illustre un ordinogramme d’un mode de réalisation du procédé 400 d’insertion d’un élément chiffré homomorphe dans une liste chiffrée homomorphe de sorte à obtenir une liste chiffrée homomorphe modifiée . L’élément chiffré homomorphe est obtenu par chiffrement homomorphe d’un élément en clair appartenant à un tore T . La liste chiffrée homomorphe est obtenue à partir d’une liste en clair comprenant les éléments , étant un entier compris entre 0 et , N étant un nombre entier supérieur ou égal à 1. Selon l’exemple illustré à la figure 3, les éléments appartiennent au tore T et la liste chiffrée homomorphe est sous la forme d’un chiffré homomorphe de L’objectif du procédé d’insertion 400 est d’obtenir une nouvelle liste chiffrée homomorphe qui est le chiffré homomorphe d’une liste en clair La liste en clair est identique à la liste de départ à l’exception de l’élément qui a été remplacé par l’élément . Pour ce faire, le mode de réalisation du procédé 400 selon le deuxième aspect de l’invention comprend : Recevoir 401 l’élément chiffré homomorphe , la liste chiffrée homomorphe et un chiffré homomorphe sous la forme d’un chiffré homomorphe de , , et étant chiffrés à l’aide d’une même clé s ; Extraire, à l’aide du procédé 100 selon le premier aspect de l’invention, l’élément 402 de la liste chiffrée homomorphe ; Calculer 403 de façon homomorphe la différence ; Obtenir 404 un chiffré homomorphe de la quantité ; Obtenir la liste chiffrée homomorphe modifiée 405 en calculant de façon homomorphe la somme . L’étape 402 d’extraire l’élément de la liste chiffrée homomorphe comprend donc la mise en œuvre du procédé 100 selon le premier aspect de l’invention. La figure 4a illustre en détail certaines étapes d’un mode de réalisation du procédé 400 selon le quatrième aspect de l’invention, les fonctions étant dans ce cas les fonctions identité. Selon le mode de réalisation illustré à la figure 4a, la liste de départ est obtenue à partir de la liste en clair en calculant un chiffré homomorphe de type = ( + X + + … ). L’élément chiffré homomorphe est calculé selon la formule et l’indice chiffré homomorphe selon la formule . Ces deux derniers éléments ne sont pas représentés à la figure 4a. Dans le cas illustré à la figure 4a, la fonction est choisie comme étant égale à . Ce choix de techniques de chiffrement permet de calculer le produit modulaire homomorphe en tant que chiffré d’un polynôme : = ( + + … ) = ( + + … ) L’élément à remplacer dans la liste L peut par exemple être extrait en tant que coefficient zéro du polynôme chiffré homomorphe obtenu en calculant le produit modulaire homomorphe . L’étape 405 d’obtenir la liste chiffrée homomorphe est realisée, selon le mode de réalisation illustré à la figure 4b, en calculant le chiffré homomorphe qui peut être exprimé de la façon suivante : = ( + X + + … ) La dernière équation montre que l’élément a été remplacé dans le nouveau chiffré homomorphe par l’élément . Selon ce mode de réalisation, l’étape 405 comprend la conversion de en . En effet et appartenant au tore T , le chiffré homomorphe de leur différence est un chiffré de type TLWE. La conversion d’un chiffré de type TLWE en TRLWE est réalisé à l’aide de primitives connues en cryptographie homomorphe. Il est important de noter que lors de l’étape 405 du procédé 400 selon le deuxième aspect de l’invention, la quantité doit être évaluée, alors que le chiffré homomorphe de l’indice est sous la forme d’un chiffré homomorphe de , Selon un mode de réalisation du procédé 400, la quantité peut alors être obtenue da la façon suivante : Calculer un chiffré homomorphe de la quantité selon la formule ; Calculer le produit modulaire homomorphe selon la formule et Obtenir, à partir de la quantité , la quantité sous la forme de . Si la fonction est du type , étant premier avec M, M étant l’ordre du polynôme cyclotomique, l’étape d’obtenir la quantité est réalisée en appliquant un automorphisme. On entend ici par automorphisme une primitive connue en cryptographie homomorphe dont la définition est la suivante : Si et u est un entier premier avec N, l’automorphisme effectue l’opération suivante ) = La illustre un mode de réalisation d’un système cryptographique 500 pour la manipulation d’une liste chiffrée homomorphe selon un aspect de l’invention. Le système cryptographique 500 comprend un serveur de traitement cryptographique pour l’extraction d’un élément chiffré homomorphe d’une liste chiffrée homomorphe 501. Le serveur cryptographique 501 comprend un module de communication 502 et un module de calcul 503. Le module de calcul 502 est configuré pour recevoir, de la part d’une entité externe au serveur, un indice chiffré homomorphe . Le module de calcul 503 est configuré pour extraire, d’une liste chiffrée homomorphe, un élément chiffré homomorphe associé à l’indice chiffré homomorphe conformément au procédé 100 selon le premier aspect de l’invention. Le système cryptographique 500 comprend en outre un client 504 configuré pour chiffrer l’indice sous la forme d’indice chiffré homomorphe , par exemple sous forme d’un monôme chiffré homomorphe et pour communiquer l’indice chiffré homomorphe au serveur via un canal de communication 504c. Selon un mode de réalisation du système cryptographique 500, le client 504 est configuré pour calculer le chiffré de l’indice sous la forme . Selon un mode de réalisation du système cryptographique 500, le serveur 501 est configuré pour mettre un œuvre le procédé 400 d’insertion d’un élément chiffré homomorphe dans une liste chiffrée homomorphe. Le client 504 est alors configuré pour chiffrer l’élément µ de sorte à obtenir un élément chiffré homomorphe . Le client 504 est en outre configuré pour transmettre l’élément chiffré homomorphe au serveur 501 via un canal de communication 504c. Description de la procédure de rafraichissement d’un chiffré homomorphe Lorsque l'on additionne deux messages cryptés, on obtient un message crypté, qui est une version cryptée de la somme des deux messages initiaux non cryptés, dont la composante de bruit est plus élevée que pour les deux messages cryptés initiaux. Ainsi, pour empêcher le terme de bruit d'augmenter et de croître au cours du traitement des données, une procédure de rafraîchissement, généralement appelée "bootstrapping", est exécutée de manière répétée. Cette procédure produit une version rafraîchie de c, c'est-à-dire un message crypté c' qui est décrypté lui aussi en tant μ (lorsqu'il est décrypté en utilisant s), mais dont la composante de bruit est plus petite que celle de c. La procédure de "bootstrapping" comprend habituellement une évaluation homomorphe de la quantité avec : est un polynôme de rafraîchissement fonctionnel de degré inférieur ou égal à N-1 dont les coefficients sont choisis en fonction des caractéristiques de l’espace des messages et d’une fonction cible ; et α est l’entier le plus proche de 2N(b-a.s) : On entend ici par évaluation homomorphe, un calcul réalisé en utilisant des quantités chiffrées, sans déchiffrement préalable (sans connaitre la clef s). On entend ici par fonction cible une fonction mathématique appliquée au message chiffré en même temps que le rafraîchissement. Dans le cas d’un simple rafraîchissement, la fonction cible est la fonction identité. Pour un polynôme opportunément choisi, le terme constant de , à savoir , est une version rafraichie de c, c’est-à-dire une version chiffrée de µ avec une composante de bruit e’ limitée (généralement plus petite que la composante de bruit de c, lorsque c est issu d’opérations de traitement de données – homomorphe – précédentes ; quoiqu’il en soit, e’ est suffisamment petit pour permettre un déchiffrement de c’, avec un taux d’erreur faible). De façon connue, le calcul homomorphique de la quantité peut être décomposé en un calcul d’une séquence de produits modulaires donnés par : Où , et . Où les s k sont les n composantes du vecteur s. Dans l’équation ci-dessus, lorsque calculée de manière homomorphe, chaque produit “.” est un produit modulaire : le terme à gauche, par exemple ou appartient à , le terme à droite, par exemple ou , appartient à T N [X]. Ici on définit T N [X] = T [X]/(X N +1). Un tel produit est similaire au produit y.µ i , y étant un entier et µ appartenant à T (si ce n’est que l’on travaille sur des corps de polynômes, au lieu de corps de nombres). Le calcul homomorphique de est non immédiat à cause de la présence de la clé secrète s, qui n’est pas connue. Toutefois, il est connu qu’un produit modulaire tel que y.µ i ou X j .v(X) peut être calculé de façon homomorphe en définissant le produit extérieur . La quantité est la version chiffrée du message µ i . La quantité est le chiffrement “TRGSW“ de z (l’acronyme TRGSW vient de l’anglais “Gentry, Sahai, Waters Torus Ring encryption”, adaptée d’une méthode de chiffrement qui a été proposée dans l’article “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based”, by C. Gentry, A. Sahai, and B. Waters, InCrypto’13, 2013). En outre, de façon connue, il est possible de calculer le produit sans connaître les composantes s k , k = 1…n de la clé secrète et donc sans connaître la clé secrète s. En effet, comme les composantes s k , k = 1…n appartiennent chacune à B ={0,1} (i.e. : sont chacune binaire), la quantité est égale à qui est chiffré comme . Il s’ensuit qu’une version chiffrée de peut être calculée sans avoir accès à la clé secrète s en utilisant la version chiffrée des composants s k . Ces versions chiffrées des composantes de s sont parfois appelées clés de Boostsrap (« Bootstrap key » en anglais). Les clés de Bootstrap (généralement publiques) sont des versions chiffrées des composantes s k de la clé secrète s chiffrées en utilisant une autre clé s’. est définie comme étant égale à avec : , où z j , j=1…l(K+1), sont l(K+1) version chiffrées de 0, la valeur nulle 0 étant chiffrée avec s’, l étant un nombre entier positif donné; et est une matrice dont la dimension est et dont les coefficients appartiennent au tore T , étant égale à : avec B étant un nombre entier supérieur ou égal à 2. Le produit extérieur , entre : Un message chiffré , correspondant à un message µ appartenant au tore T N [X] et La version chiffrée d’un polynôme à coefficients entiers y, , est calculée selon la méthode détaillée ci-après. Les K+1 composantes c j , j=1..K+1 du message chiffré sont en quelque sorte décomposées en utilisant un système en base B (comme celui utilisé pour calculer les ) Ensuite, il est possible de calculer dans laquelle est le produit matriciel ligne-colonne et est une matrice de dimension (n+1)×l dont la forme est la suivante : Avec Le résultat appartient à et est une version chiffrée de y.µ. En d’autres termes, en décryptant cette quantité avec la clé s’ on retrouve y.µ. Cette méthode de calcul peut être appliquée à tout message appartenant au tore T . En utilisant les clés BK i introduite ci-dessus, on obtient pour le calcul homomorphe de coef 0 (X α .v(X)),à savoir l’équation suivante : L’équation ci-dessus permet donc d’effectuer le rafraîchissement ou bootstrapping du message chiffré sans besoin de connaître la clé de chiffrement. Procédé d’obtention (100) d’un élément chiffré homomorphe d’une liste chiffrée homomorphe , l’élément chiffré homomorphe étant associé à un indice , étant compris entre 0 et N-1, les éléments de la liste appartenant à un tore T, la liste et l’indice étant chiffrés à l’aide d’une même clé, ledit procédé comprenant les étapes suivantes : Obtenir un chiffré homomorphe (101) d’un polynôme Q(X), Q(X) étant une agrégation des éléments de la liste , j étant compris entre 0 et N-1, chaque coefficient du polynôme étant une combinaison linéaire d’éléments de la liste , appartenant à un espace quotient , étant un espace des polynômes de degré N-1 avec coefficients à valeurs dans le tore T et étant un polynôme cyclotomique d’ordre M ; Obtenir un chiffré homomorphe (102) d’un monôme , étant une fonction de l’indice associé à l’élément à obtenir, appartenant à un espace quotient , étant un ensemble de polynômes à coefficients dans les nombres entiers ; Déterminer un polynôme chiffré homomorphe (103) en tant que produit modulaire homomorphe entre et ; Extraire le coefficient k (104) du polynôme chiffré homomorphe , k étant déterminé sur la base du polynôme Q(X) et de la fonction utilisée dans le monôme P(X), le coefficient k du polynôme chiffré homomorphe correspondant à l’élément chiffré homomorphe à obtenir. Procédé d’obtention (100) d’un élément chiffré homomorphe d’une liste chiffrée homomorphe selon la revendication précédente dans lequel chaque coefficient du polynôme Q(X) est une combinaison linéaire obtenue selon la formule suivante avec , , et le coefficient du polynôme correspondant à l’élément chiffré homomorphe à extraire est le coefficient k = 0, γ étant égale à . Procédé d’obtention (100) d’un élément chiffré homomorphe d’une liste chiffrée homomorphe selon la revendication 1 dans lequel : Le polynôme chiffré homomorphe est obtenu à partir de la liste comprenant les éléments , étant un entier compris entre 0 et , le polynôme chiffré homomorphe étant sous la forme d’un chiffré homomorphe de , étant une fonction à valeurs dans l’ensemble des nombres entiers compris entre 0 et N-1 et et M = 2 α ; Le monôme chiffré homomorphe est obtenu à partir de l’indice , étant sous la forme d’un chiffré homomorphe de , étant une fonction à valeurs dans l’ensemble des nombres entiers compris entre 0 et N-1 ; Le polynôme chiffré homomorphe est obtenu selon la formule ; Le coefficient k du polynôme à extraire est donné par . Procédé selon la revendication précédente dans lequel : Le polynôme chiffré homomorphe est déterminé selon la formule suivante ; Le monôme chiffré homomorphe est déterminé selon la formule suivante Procédé selon la revendication 3 ou la revendication 4 dans lequel les fonctions et sont la fonction identité de sorte à avoir et et le coefficient k du polynôme à extraire est le coefficient k = 0. Programme d’ordinateur comprenant des instructions exécutables par un processeur et conçues pour mettre en œuvre un procédé selon l’une quelconque des revendications 1 à 5 lorsque ces instructions sont exécutées par ledit processeur. Procédé d’insertion (400) d’un élément chiffré homomorphe dans une liste chiffrée homomorphe de sorte à obtenir une liste chiffrée homomorphe modifiée , dans lequel : L’élément chiffré homomorphe est obtenu par chiffrement homomorphe d’un élément en clair appartenant à un tore T ; La liste chiffrée homomorphe est obtenue à partir d’une liste en clair comprenant les éléments , étant un entier compris entre 0 et , N étant un nombre entier supérieur ou égal à 1, les éléments appartenant au tore T , la liste chiffrée homomorphe étant sous la forme d’un chiffré homomorphe de ; La liste chiffrée homomorphe modifiée est un chiffré homomorphe d’une liste en clair comprenant les éléments pour et pour , étant un entier compris entre 0 et N-1 ; Ledit procédé comprenant les étapes suivantes : Recevoir (401) l’élément chiffré homomorphe , la liste chiffrée homomorphe et un indice chiffré homomorphe sous la forme d’un chiffré homomorphe de , , et étant chiffrés à l’aide d’une même clé s ; Extraire, conformément au procédé selon l’une quelconque des revendications 1 à 5, l’élément (402) de la liste chiffrée homomorphe ; Calculer de façon homomorphe la différence (403) ; Obtenir (404) un chiffré homomorphe de la quantité ; Obtenir la liste chiffrée homomorphe modifiée (405) en calculant de façon homomorphe la somme . Procédé d’insertion (400) d’un élément chiffré homomorphe dans une liste chiffrée homomorphe selon la revendication précédente dans lequel : La liste chiffrée homomorphe est un chiffré homomorphe calculé selon la formule ; L’élément chiffré homomorphe est calculé selon la formule ; Le chiffré homomorphe est calculé selon la formule . Procédé d’insertion (400) d’un élément chiffré homomorphe dans une liste chiffrée homomorphe selon la revendication précédente dans lequel l’étape (404) d’obtenir un chiffré homomorphe de la quantité comprend : Calculer un chiffré homomorphe de la quantité selon la formule ; Calculer le produit modulaire homomorphe selon la formule ; Obtenir, à partir de la quantité , un chiffré homomorphe de la quantité sous la forme de . Procédé d’insertion (400) d’un élément chiffré homomorphe dans une liste chiffrée homomorphe selon l’une des revendications 7 à 9 dans lequel les fonctions et sont la fonction identité de sorte à avoir et . Programme d’ordinateur comprenant des instructions exécutables par un processeur et conçues pour mettre en œuvre un procédé selon l’une quelconque des revendications 7 à 10 lorsque que ces instructions sont exécutées par ledit processeur. Serveur (501) de traitement cryptographique pour le traitement d’une liste chiffrée homomorphe comprenant un module de communication (502) et un module de calcul (503) : Le module de communication (502) étant configuré pour recevoir, de la part d’une entité externe au serveur, un indice chiffré homomorphe ; Le module de calcul (503) étant configuré pour extraire, d’une liste chiffrée homomorphe , un élément chiffré homomorphe associé à l’indice chiffré homomorphe conformément au procédé selon l’une des revendications 1 à 5. Serveur (501) de traitement cryptographique pour le traitement d’une liste chiffrée homomorphe selon la revendication précédente dans lequel : Le module de communication (502) est en outre configuré pour recevoir un élément chiffré homomorphe ; le module de calcul (503) est en outre configuré pour introduire l’élément chiffré homomorphe dans une liste chiffrée homomorphe conformément au procédé selon l’une des revendications 7 à 10. Client (504) configuré pour chiffrer l’indice sous la forme d’indice chiffré homomorphe et/ou un élément sous la forme d’élément chiffré homomorphe et pour communiquer l’indice chiffré homomorphe et/ou l’élément chiffré homomorphe à un serveur (501) selon la revendication 7 ou 8 via un canal de communication (504c). Système cryptographique (500) pour le traitement d’une liste chiffrée homomorphe comprenant : Un serveur (501) de traitement cryptographique pour le traitement d’une liste chiffrée homomorphe selon la revendication 7 ou la revendication 8; Un client (504) selon la revendication 9.