Brevet FR3150382A1 — publié le 20241227

Procédé pour détecter la présence d’un élément chiffré homomorphe dans un ensemble chiffré homomorphe Procédé (100) pour détecter la présence d’un élément chiffré homomorphe c > dans un ensemble chiffré homomorphe L >, ledit procédé comprenant les étapes suivantes : Chiffrement totalement homomorphe (101), par un client et à l’aide d’une clé , d’un élément en clair µ pour obtenir le chiffré homomorphe c > ; Réception (102) de l’élément chiffré homomorphe c > par le serveur ; Application d’un opérateur d’extraction (103a) à l’ensemble chiffré homomorphe de sorte à extraire une empreinte de l’ensemble chiffré homomorphe ; Comparaison homomorphe (103b) de l’empreinte extraite de l’ensemble chiffré homomorphe et d’une fonction de l’élément chiffré homomorphe c > pour obtenir un indicateur de présence I > ledit indicateur de présence I > étant sous forme chiffrée homomorphe ; Emission (104) de l’indicateur de présence I >. Figure à publier avec l’abrégé : Figure 1 Procédé pour détecter la présence d’un élément chiffré homomorphe dans un ensemble 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 d’ensembles chiffrés homomorphes. ARRIÈRE-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, recevoir les données, chiffrées, 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 la somme et la soustraction homomorphe d’éléments appartenant à un tore T , la somme et la soustraction de polynômes chiffrés homomorphes appartenant à l’anneau de polynômes de degré N, ou encore le produit modulaire homomorphe entre deux éléments appartenant à . 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 des messages 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 d’ensembles homomorphes. Certaines applications de traitement de données requièrent la détection de la présence d’un élément dans un ensemble, par exemple la présence d’un identifiant utilisateur dans une liste d’utilisateurs autorisés à accéder à un certain bien ou service, tout en protégeant les données personnelles des utilisateurs. Un autre exemple d’application nécessitant la détection de la présence d’un utilisateur dans ensemble d’utilisateur est la vente aux enchères d’annonces publicitaires sur internet. En effet la publicité en ligne utilise le ciblage depuis plus de 10 ans et cherche à montrer une annonce publicitaire uniquement aux utilisateurs susceptibles d’acheter le bien ou le service faisant l’objet de l’annonce. Pour ce faire, les annonceurs publicitaires collectent les données personnelles des utilisateurs et les utilisent pour mieux viser les possibles acheteurs. Toutefois, la collecte de données personnelles représente souvent une atteinte à la vie privée des utilisateurs et est de plus en plus règlementée par les pouvoirs publics partout dans le monde. Dans ce contexte, la détection de la présence d’un élément chiffré homomorphe dans un ensemble chiffré homomorphe sans déchiffrement préalable de l’ensemble et de l’élément chiffrés est particulièrement intéressante car elle permettrait aux annonceurs de bien cibler les utilisateurs sans pour autant avoir accès aux données personnelles en clair. Certains documents de l’état de la technique traitent du problème de la détection de la présence d’un élément chiffré homomorphe dans un ensemble d’éléments chiffrés homomorphes. Par exemple, le document EP4111635A1 « Procédé pour tester l'appartenance d'un élément de données à une liste d'éléments de données de référence », demande de brevet européen déposé le 2/10/2021 au nom de Thalès, divulgue une technique de détection de la présence d’un élément candidat chiffré homomorphe dans une liste d’éléments. Toutefois, la méthode divulguée dans ce document nécessite une opération de comparaison pour chaque élément appartenant à la liste, ce qui augmente excessivement le temps requis pour détecter la présence de l’élément candidat dans l’ensemble. Le document US10015007B2 « Performing efficient comparison operations on encrypted data », brevet US déposé le 25/11/2015 au nom de IBM, divulgue une méthode de comparaison entre éléments chiffrés homomorphes mais ne traite pas du problème de la détection de la présence d’un élément candidat dans un ensemble d’éléments chiffrés homomorphes. Il existe donc un besoin de développer des techniques permettant de détecter la présence d’un élément chiffré homomorphe dans un ensemble d’éléments chiffrés homomorphes. Par ailleurs, il est nécessaire de développer des méthodes de détection qui soient totalement homomorphes, 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é pour détecter la présence d’un élément chiffré homomorphe c > dans un ensemble chiffré homomorphe L >, l’ensemble chiffré homomorphe L > étant chiffré à l’aide d’une clé et étant mémorisé dans un serveur, ledit procédé comprenant les étapes suivantes : Chiffrement totalement homomorphe, par un client et à l’aide de la clé , d’un élément en clair µ pour obtenir l’élément chiffré homomorphe c > ; Réception de l’élément chiffré homomorphe c > par le serveur ; Application d’un opérateur d’extraction à l’ensemble chiffré homomorphe L > de sorte à extraire une empreinte de l’ensemble chiffré homomorphe ; Comparaison homomorphe de l’empreinte extraite de l’ensemble chiffré homomorphe et d’une fonction de l’élément chiffré homomorphe c > pour obtenir un indicateur de présence I > de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe L >, ladite comparaison étant effectuée sans déchiffrement de l’élément chiffré homomorphe c > et sans déchiffrement de l’ensemble chiffré homomorphe L >, ledit indicateur de présence I > étant sous forme chiffrée homomorphe ; Émission de l’indicateur de présence I >. Les chevrons … > indiquent un chiffré homomorphe d’une quantité. Par exemple, le symbole i > indique un chiffré homomorphe de l’entier . Par empreinte de l’ensemble chiffré homomorphe, il est entendu le résultat de l’application de l’opérateur d’extraction à l’ensemble chiffré homomorphe. Par exemple, l’empreinte de l’ensemble chiffré homomorphe peut être une portion de l’ensemble chiffré homomorphe ou une fonction d’une portion de l’ensemble chiffré homomorphe. La portion de l’ensemble chiffré homomorphe correspondant à l’empreinte extraite peut comprendre un ou plusieurs éléments de l’ensemble chiffré homomorphe. Par chiffré totalement homomorphe, il est entendu un élément chiffré obtenu à l’aide d’une technique de chiffrement totalement homomorphe ou FHE selon la terminologie anglaise « Fully Homorphic Encryption ». Par opérateur d’extraction, il est entendu une séquence d’opérations permettant d’extraire une empreinte de l’ensemble chiffré homomorphe. Les étapes d’application de l’opérateur d’extraction et de comparaison homomorphe peuvent être répétées de sorte à couvrir l’intégralité de l’ensemble chiffré homomorphe. Dans une autre approche, les étapes d’application de l’opérateur d’extraction et de comparaison homomorphe peuvent être répétées de sorte à mettre en œuvre une recherche dichotomique de l’élément chiffré c > homomorphe dans l’ensemble chiffré homomorphe. Le procédé selon le premier aspect de l’invention permet de détecter la présence d’un élément chiffré homomorphe dans un ensemble chiffré homomorphe tout en empêchant l’accès au message µ en clair. Par exemple, le message µ peut être un identifiant utilisateur, un numéro de téléphone, un cookie ou toute information concernant l’utilisateur. Grâce au chiffrement totalement homomorphe, le message µ et donc les données personnelles de l’utilisateur sont protégées. En d’autres termes, le serveur et les autres entités impliquées dans le procédé ne peuvent pas distinguer les informations chiffrées homomorphes du bruit aléatoire. Pour chaque mise en œuvre du procédé, un nouveau chiffrement du message est réalisé lors de la première étape du procédé, ce qui rend les attaques par corrélation moins probables. Le serveur reçoit l’élément chiffré homomorphe c > et calcule de façon homomorphe un indicateur de présence I > de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe L >. Lors de l’étape d’émission de l’indicateur de présence I >, l’indicateur de présence I > peut par exemple être émis vers un utilisateur possédant la clé ou vers un autre utilisateur pour poursuivre les calculs, peut être stocké dans une base de données ou encore émis vers une entité configurée pour déchiffrer ledit indicateur de présence I >. L’indicateur de présence I > peut alors être utilisé par exemple pour évaluer si l’utilisateur fait partie des utilisateurs ayant accès à un certain service dans un système ou à certains espaces dans un bâtiment. Le procédé selon le premier aspect de l’invention trouve en outre son application dans les problèmes concernant le calcul de l’intersection de deux ensembles, par exemple dans des domaines tels que le stockage de langages artificiels, la génomique, les bases de données qui peuvent utiliser des arbres-B. Par ailleurs, le procédé selon le premier aspect de l’invention peut être utilisé pour tous les problèmes utilisant des tables de hachage. Dans un autre exemple, l’indicateur de présence I > peut être utilisé par un serveur de type acheteur de publicité ou plateforme d’achats (« Demand Side Platform » ou DSP selon la terminologie anglaise) pour évaluer si l’utilisateur est une cible d’intérêt pour une annonce publicitaire donnée. Dans ce cas, l’ensemble L > peut être un public fourni par un système de Gestion de la Relation Client (« Customer Relationship Management » ou CRM selon la terminologie anglaise) ou un segment d’une plateforme de gestion de donnée (« Data Management Platform » ou DMP selon la terminologie anglaise) ou CDP pour «Customer Data Platform». Il est important de noter que le serveur, par exemple la plateforme d’achats DSP, ne déchiffre pas l’indicateur de présence I > . Cet indicateur peut être envoyé à une autre entité, par exemple une boîte noire transactionnelle (« Hardware Security Module » ou HSM selon la terminologie anglaise), qui est la seule entité impliquée dans le procédé selon le premier aspect de l’invention qui soit capable de déchiffrer le résultat de la détection. Si l’élément chiffré homomorphe c > fait partie de l’ensemble chiffré homomorphe L > le serveur peut autoriser l’utilisateur à accéder à un certain bien ou service ou, dans le cas d’un DSP, envoyer une offre pour afficher une annonce publicitaire susceptible d’intéresser le client. Il est important de noter que, dans tous les cas, le serveur n’a aucun accès au message en clair µ et ne connaît pas les données personnelles de l’utilisateur. En d’autres termes, grâce au fait que l’entité configurée pour déchiffrer l’indicateur de présence I > est la seule entité capable de déchiffrer le résultat de la recherche de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe I >, les données personnelles du client ou utilisateur résultent protégées et inaccessibles lors de la mise en œuvre du procédé selon le premier aspect de l’invention. Dans un ou plusieurs modes de réalisation, l’indicateur de présence I > est de type booléen. Ce type d’indicateur de présence permet de chiffrer de façon directe le résultat de la recherche de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe. Dans un ou plusieurs modes de réalisation, le message µ est un identifiant d’un utilisateur, le client étant associé audit utilisateur. Dans un ou plusieurs modes de réalisation, le serveur est une plateforme d’achats ou DSP. Dans un ou plusieurs modes de réalisation, l’indicateur de présence I > est émis vers une entité configurée pour déchiffrer l’indicateur de présence I >, ladite entité étant une boîte noire transactionnelle, le procédé selon le premier aspect de l’invention comprend en outre une étape de réception de l’indicateur de présence I > par une entité de type boîte noire transactionnelle et une étape de déchiffrement homomorphe de l’indicateur I > par l’entité de type boîte noire transactionnelle. Dans un ou plusieurs modes de réalisation, l’empreinte de la liste chiffrée homomorphe est un élément de la liste chiffrée 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é, l’étape d’application d’un opérateur d’extraction 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. 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. Ce mode de réalisation de l’étape d’application d’un opérateur d’extraction à la liste chiffrée homomorphe 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. Ce mode de réalisation de l’étape d’application d’un opérateur d’extraction à la liste chiffrée homomorphe 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 . Ce mode de réalisation de l’étape d’application d’un opérateur d’extraction à la liste chiffrée homomorphe 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 de ce mode de réalisation de l’étape d’application d’un opérateur d’extraction 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é – à savoir l’empreinte de la liste chiffrée homomorphe - à 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, l’étape d’application d’un opérateur d’extraction à la liste chiffrée homomorphe 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 de l’étape d’application de l’opérateur d’extraction : La polynôme chiffré homomorphe est obtenu selon la formule suivante ; Le monôme chiffré homomorphe est déterminé selon la formule suivante Dans un ou plusieurs modes de réalisation du procédé selon le premier aspect de l’invention : L’ensemble chiffré homomorphe possède une structure de type filtre de Bloom de taille m , m étant un entier supérieur à 1, le filtre de Bloom comprenant h tableaux, h étant un entier supérieur ou égal à 1, chaque tableau étant associé à une fonction de hachage ; L’étape de chiffrement totalement homomorphe de l’élément µ pour obtenir l’élément chiffré homomorphe c > est réalisée à l’aide de la formule suivante , comprenant h composantes, chaque composante étant obtenue an appliquant une des h fonction de hachage à une quantité , la quantité étant le reste de la division de par m ; L’étape d’application d’un opérateur d’extraction comprend l’extraction de h pluralités d’éléments chiffrés homomorphes de l’ensemble chiffré homomorphe , chaque pluralité d’éléments chiffrés homomorphes extraits correspondant à un des h tableaux du filtre de Bloom ; L’étape de comparaison homomorphe comprend le calcul de h produits modulaires homomorphes entre pluralités d’éléments chiffrés homomorphes extraits et composantes de l’élément chiffré homomorphe c >; L’indicateur de présence I > est déterminé à partir d’une fonction appliquée aux résultats des h produits modulaires homomorphes. Dans un ou plusieurs modes de réalisation, la fonction appliquée aux résultats des h produits modulaires homomorphes est la somme des h produits modulaires homomorphes. Par filtre de Bloom on entend une structure de données connue dans l’état de la technique et définie par un tableau de m bits et h fonctions de hachage, chaque fonction de hachage associant un élément de la base de données à représenter dans le filtre de Bloom à un des m bits. Un filtre de Bloom est une structure de données probabiliste adaptée pour tester la présence d’un élément dans un ensemble. Une structure de données de type filtre de Bloom s’avère particulièrement avantageuse car la taille du tableau est fixée, même si l’ensemble de données dans lequel effectuer la recherche varie. Dans le cas du procédé selon le premier aspect de l’invention, le choix d’un filtre de Bloom pour représenter l’ensemble d’éléments chiffrés homomorphes L > est particulièrement efficace pour réduire le temps nécessaire pour la recherche d’un élément chiffré homomorphe c >. Par ailleurs, il est possible de fixer la taille m des tableaux en le considérant comme un paramètre initial, le nombre total n d’éléments stockables dans le filtre de Bloom étant déterminé par m et le nombre h de fonctions de hachage. Par produit modulaire homomorphe , 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. Définition de chiffrement TLWE 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 déchiffrement, le vecteur a est un vecteur de projection de la clé s 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 C(X) = , 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 , étant la taille du message à chiffrer. 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 TRGSW 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 , k étant la taille du polynôme à chiffrer. Le chiffré TRGSW de m est alors déterminé de la façon suivante : avec , où zj, 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 TGRSW et un TRLWE 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 : Dans un ou plusieurs modes de réalisation : L’ensemble chiffré homomorphe est une liste triée chiffrée homomorphe ; L’empreinte de la liste chiffrée homomorphe extraite lors de l’application d’un opérateur d’extraction comprend un seul élément de la liste chiffré homomorphe ; L’étape d’application d’un opérateur d’extraction et l’étape de comparaison homomorphe sont répétées pour former une séquence de comparaisons homomorphes entre les éléments extraits de la liste triée homomorphe et l’élément chiffré homomorphe c > de sorte à réaliser une recherche dichotomique de l’élément chiffré homomorphe c > dans la liste triée chiffrée homomorphe ; L’indicateur de présence I > est déterminé à partir de la dernière comparaison homomorphe de la séquence de comparaisons homomorphes. Par liste triée, il est entendu un ensemble dont les éléments sont associés à un indice et ordonnés selon ledit indice. Un deuxième aspect de l’invention porte sur un client configuré pour : réaliser une étape de chiffrement homomorphe d’un élément en clair µ de sorte à obtenir un élément chiffré homomorphe c > conformément au procédé selon l’une quelconque des revendications précédentes ; Transmettre, au moyen d’un canal de communication, l’élément chiffré homomorphe c > à un serveur ; Un troisième aspect de l’invention est un serveur configuré pour : Mémoriser la liste chiffré homomorphe L > ; Appliquer un opérateur d’extraction de sorte à extraire une empreinte de l’ensemble chiffré homomorphe conformément au procédé selon l’une des revendications précédentes ; Réaliser la comparaison homomorphe de la fonction de l’élément chiffré homomorphe c > et de l‘empreinte de l’ensemble chiffré homomorphe L > conformément au procédé selon l’une des revendications précédentes et déterminer un indicateur I > de présence de l’élément chiffré homomorphe c dans l’ensemble chiffré homomorphe L >, I > étant sous forme d’un chiffré homomorphe ; Emettre l’indicateur de présence I >. Un quatrième aspect de l’invention porte sur un système cryptographique comprenant un client selon le deuxième aspect de l’invention, un serveur selon le troisième aspect de l’invention et une entité configurée pour déchiffrer l’indicateur de présence I > émis par le serveur. Dans un ou plusieurs modes de réalisation, l’entité configurée pour déchiffrer l’indicateur de présence I > est une boîte noire transactionnelle. Dans un ou plusieurs modes de réalisation, l’entité configurée pour déchiffrer l’indicateur de présence I > est en outre configurée pour transmettre le résultat du déchiffrement de l’indicateur de présence I > au serveur. Un cinquième aspect de l’invention porte sur un produit programme d’ordinateur comprenant des instructions exécutables par un ordinateur et conçues pour la mise en œuvre du procédé selon le premier aspect de l’invention lorsque ces instructions sont exécutées par le processeur. 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é de détection de la présence d’un élément chiffré homomorphe dans un ensemble chiffré homomorphe selon le premier aspect de l’invention. illustre l’utilisation d’une structure de données de type filtre de Bloom dans la mise en œuvre du procédé selon le premier aspect de l’invention. illustre un ordinogramme d’un mode de réalisation d’une étape d’application d’un opérateur d’extraction d’un élément chiffré homomorphe d’un ensemble chiffré homomorphe. illustre schématiquement un exemple de chiffrement homomorphe d’un ensemble d’éléments. illustre schématiquement l’extraction d’un élément chiffré homomorphe de l’ensemble chiffré homomorphe illustré à la . illustre un mode de réalisation d’un système cryptographique selon le quatrième aspect de l’invention. DESCRIPTION DETAILLEE La illustre schématiquement un mode de réalisation du procédé 100 selon le premier aspect de l’invention. Selon le mode de réalisation représenté à la , le procédé 100 selon le premier aspect de l’invention comprend : Une étape de chiffrement totalement homomorphe 101 d’un élément en clair µ pour obtenir le chiffré homomorphe c, le chiffrement étant réalisé à l’aide de la clé s ; Une étape 102 de réception, par un serveur hébergeant l’ensemble chiffré homomorphe L >, de l’élément chiffré homomorphe c >, l’ensemble chiffré homomorphe L > étant chiffré à l’aide de la clé ; Une étape 103a d’application d’un opérateur d’extraction d’une empreinte de l’ensemble chiffré homomorphe L >. Une étape de comparaison homomorphe 103b de l’empreinte extraite de l’ensemble chiffré homomorphe et de l’élément chiffré homomorphe c > pour obtenir un indicateur de présence de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe L >, ladite comparaison étant effectuée sans déchiffrement de l’élément chiffré homomorphe c > et sans déchiffrement de l’ensemble chiffré homomorphe L >, ledit indicateur de présence I > étant sous forme chiffrée homomorphe ; Une étape 104 d’émission de l’indicateur de présence I > ; Une étape 105a de réception de l’indicateur de présence I > par une entité de type boîte noire transactionnelle ; Une étape 105b de déchiffrement homomorphe de l’indicateur de présence I par la boîte noire transactionnelle. Grâce au chiffrement totalement homomorphe du message µ, la détection de la présence de l’élément c > dans l’ensemble chiffré homomorphe est réalisée sans déchiffrement. Les différents éléments impliqués dans la mise en œuvre du procédé 100 selon le premier aspect de l’invention n’ont aucun accès au message en clair µ, ce qui protège les données personnelles de l’utilisateur. La seule opération de déchiffrement est réalisée lors de l’étape 105b par la boîte noire transactionnelle, le but étant de déchiffrer l’indicateur de présence I > pour que le serveur puisse connaître le résultat de la recherche de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe L >. Dans un mode de réalisation du procédé 100 selon le premier aspect de l’invention, l’ensemble chiffré homomorphe L > possède une structure de type filtre de Bloom. Une structure de données de type filtre de Bloom est définie par un tableau de taille m bits et par h fonction de hachage. Les h fonctions de hachage permettent de remplir h tableaux de taille m en associant chaque élément d’un ensemble à représenter dans le filtre de Bloom à un des m bits du tableau. La structure d’un filtre de Bloom est décrite plus en détails en référence à la . Selon ce mode de réalisation, l’étape 101 de chiffrement totalement homomorphe de l’élément µ pour obtenir l’élément chiffré homomorphe c > est réalisée à l’aide de la formule suivante . résulte de l’application de h fonctions de hachage au message µ, h étant un entier supérieur ou égal à 1. Par exemple, est obtenu par concaténation de h composantes, chaque composante étant obtenue en appliquant une des h fonctions de hachage à la quantité , la quantité étant le reste de la division de l’élément par l’entier m. Dans ce mode de réalisation, l’étape d’application d’un opérateur d’extraction 103a comprend l’extraction des h tableaux compris dans le filtre de Bloom, chaque tableau correspondant à une des h fonctions de hachage. L’étape de comparaison 103b comprend le calcul de h produit modulaires homomorphes entre respectivement un des tableaux extraits du filtre de Bloom et la composante de c > correspondante. Par tableau extrait et composante correspondante on entend ici le tableau et la composante associés à la même fonction de hachage. L’indicateur de présence I > peut être déterminé à partir de la somme des résultats des h produits modulaires homomorphes. Chaque produit modulaire homomorphe est le plus souvent égal à un chiffré de 0 si l’élément n’appartient pas à l’ensemble chiffré homomorphe et il est toujours un chiffré de 1 si l’élément est compris dans l’ensemble. Il s’ensuit que si la somme des résultats des produits modulaires homomorphes est égal à h, on considère que l’élément chiffré homomorphe c > appartient à l’ensemble chiffré homomorphe représenté sous forme d’un filtre de Bloom. La illustre schématiquement un mode de réalisation du procédé 100 selon le premier aspect de l’invention. Dans cet exemple l’ensemble d’éléments chiffrés homomorphes est représenté par un filtre de Bloom 502b. Dans le cas illustré à la le serveur est une plateforme d’achats DSP qui doit évaluer si un client 501 appartient à l’ensemble d’éléments chiffrés 502b. Par exemple, le serveur DSP doit évaluer si le client est susceptible d’être intéressé par une annonce publicitaire donnée. Dans l’exemple illustré à la , le client 501 est un utilisateur dont un identifiant unique ID est calculé à partir d’informations personnelles. L’identifiant unique peut être un cookie, un identifiant de type « identifier for advertising » ou IFA, un numéro de téléphone, une adresse email ou encore une combinaison de ces éléments. Un chiffré totalement homomorphe RID de l’identifiant unique ID est calculé par le terminal l’utilisateur. Cela protège les informations personnelles de l’utilisateur car ni le serveur DSP ni la boîte noire transactionnelle n’ont accès aux informations en clair. Dans cet exemple le chiffré totalement homomorphe RID est calculé en tant que chiffré totalement homomorphe de la quantité c1 , c1 étant obtenu en appliquant h fonctions de hachage à l’identifiant ID. Les résultats de l’application des h fonctions de hachage sont juxtaposés pour obtenir la quantité c1. Dans un mode de réalisation, le chiffré homomorphe de l’identifiant unique est obtenu à l’aide de la formule suivante : . Dans un mode de réalisation du procédé 100 selon l’invention, à chaque fois que le chiffré homomorphe RID est transmis, un calcul homomorphe est réalisé par l’entité qui reçoit RID, par exemple en rajoutant un chiffré homomorphe de 0. Cela permet d’avoir un RID différent à chaque étape, de sorte à réduire le risque d’attaques par corrélation. Lors de l’étape 103b de comparaison homomorphe, le serveur DSP calcule h produits modulaires homomorphes entre h tableaux ou empreintes du registre représenté dans le filtre de Bloom et les h composantes de l’identifiant chiffré homomorphe RID. La somme des résultats des h produits modulaires homomorphes permet de déterminer un indicateur I > de présence de l’élément chiffré homomorphe dans l’ensemble chiffré homomorphe L > représenté sous la forme d’un filtre de Bloom. Dans cet exemple, l’ensemble chiffré homomorphe L > peut être une liste de re-ciblage, un public obtenu à partir d’un système de gestion de la clientèle CRM ou un segment fourni par une plateforme de gestion de données. L’indicateur I > peut être une variable de type booléen chiffrant l’information concernant la présence de l’élément RID dans l’ensemble chiffré homomorphe L >. En d’autres termes, l’indicateur de présence I > comprend la réponse chiffrée à la question « Le serveur DSP veut-il montrer une annonce publicitaire à cet utilisateur ? » L’indicateur chiffré I > est ensuite envoyé à une entité configurée pour déchiffrer l’indicateur de présence I > telle qu’une boîte noire transactionnelle – non représentée à la - qui est la seule entité capable de le déchiffrer et d’envoyer la réponse en clair au serveur DSP. En cas de réponse positive, à savoir en cas de booléen de type « vrai », le serveur DSP peut envoyer une offre à une plateforme de vente ou « Supply-Side platform », SSP, selon la terminologie anglaise. Si acceptée, cette offre lui permet d’acheter un espace publicitaire pour afficher son annonce. Il est important de noter que la seule information retenue par le serveur DSP concerne l’affichage d’une annonce auprès de l’utilisateur associé à l’identifiant RID. Selon un autre mode de réalisation, l’ensemble chiffré homomorphe est sous la forme d’une liste triée. Dans ce cas, l’étape de comparaison homomorphe comprend la mise en œuvre d’une recherche dichotomique dans la liste triée chiffré homomorphe. La recherche dichotomique comprend une séquence de comparaisons homomorphes entre les éléments extraits de la liste et l’élément recherché c >, chaque comparaison homomorphe comprenant au moins un produit modulaire homomorphe entre l’élément de la liste chiffrée homomorphe et l’élément recherché. De façon connue, on entend par recherche dichotomique une méthode de recherche d’un élément dans une liste triée dans laquelle la première comparaison est réalisée entre l’élément recherché et un élément central de la liste. Si l’élément recherché est l’élément central, la recherche se termine. Si les deux éléments sont différents, seule la moitié de la liste comprenant l’élément recherché est utilisée et l’algorithme continue récursivement sur cette moitié de liste. L’indicateur de présence I > est donc déterminé sur la base du résultat de la dernière comparaison homomorphe de la séquence de comparaisons homomorphes. Le procédé 100 selon le premier aspect de l’invention comprend une étape 103a comprenant l’extraction d’un élément chiffré homomorphe d’un ensemble chiffrée homomorphe. Un exemple d’un tel procédé d’extraction homomorphe développé par la demanderesse est donné dans les paragraphes suivants. Modes de réalisation de l’étape 103a d’application d’un opérateur d’extraction d’une empreinte d’un ensemble chiffré homomorphe. La illustre un mode de réalisation de l’étape d’application 103a d’un opérateur d’extraction d’une empreinte d’un ensemble chiffré homomorphe. Telle qu’illustrée à la figure 3, l’étape d’application 103a d’un opérateur d’extraction permet d’extraire une empreinte de la liste chiffrée homomorphe comprenant un élément chiffré homomorphe . L’élément chiffré homomorphe est 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 sont chiffrés à l’aide d’une même clé. L’étape 103a selon le mode de réalisation illustré à la figure 3 comprend une étape 103a.1 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. L’étape 103a tel qu’illustré à la figure 1 comprend en outre une étape 103a.2 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 103a.3, le polynôme chiffré homomorphe est déterminé en tant que produit modulaire homomorphe entre et . L’étape d’extraction 103a.4 du coefficient k de permet d’obtenir l’empreinte de la liste chiffrée homomorphe, dans ce cas 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 103a.3 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 103a.4 d’extraction du coefficient d’ordre du polynôme . Les figures 4a et 4b illustrent plus en détail un exemple d’un mode de réalisation de l’étape 103a. Selon le mode de réalisation illustré à la figure 4a, 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 4b, 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 illustre un mode de réalisation d’un système cryptographique 500 pour la détection de la présence d’un élément chiffré homomorphe dans un ensemble chiffré homomorphe selon le quatrième aspect de l’invention. Le système cryptographique 500 comprend un client 501 selon le deuxième aspect de l’invention, un serveur 502 selon le troisième aspect de l’invention et une entité 503 configurée pour déchiffrer l’indicateur de présence I >. Le client est par exemple un utilisateur dont on veut détecter la présence dans un ensemble chiffré L >. Le client est configuré pour réaliser une étape de chiffrement totalement homomorphe d’un élément en clair µ. Le résultat du chiffrement est un chiffré totalement homomorphe c > qui est ensuite transmis par le client 501 à un serveur 502. Le message µ est par exemple un identifiant unique utilisateur. L’identifiant unique utilisateur peut comprendre des données personnelles de l’utilisateur comme il a été décrit en relation à l’identifiant ID et à son chiffré homomorphe RID. Le serveur 502 est configuré pour recevoir le chiffré homomorphe c > et pour mémoriser l’ensemble chiffré homomorphe L >. Le serveur 502 est configuré pour mettre en œuvre une étape d’application d’un opérateur d’extraction 103a d’une empreinte de l’ensemble chiffré homomorphe L >. Le serveur 502 peut en outre réaliser une étape de comparaison 103b entre l’empreinte extraite de l’ensemble chiffré homomorphe L > et l’élément chiffré homomorphe c > afin d’en détecter la présence dans l’ensemble L >. À la suite de la mise en œuvre de l’étape de comparaison 103b du procédé 100 selon le premier aspect de l’invention, le serveur 502 obtient un indicateur de présence I > de l’élément chiffré homomorphe dans l’ensemble chiffré homomorphe L >. L’indicateur de présence I > est ensuite transmis à une entité 503 configurée pour le déchiffrement telle qu’une boîte noire transactionnelle. La boîte noire transactionnelle est le seul élément du système cryptographique 500 capable de déchiffrer l’indicateur de présence et de communiquer au serveur si l’élément c > fait partie de l’ensemble L >. Avantageusement, la seule information en clair à laquelle le serveur 502 a accès est la variable booléenne I indiquant la présence de l’élément chiffré homomorphe dans l’ensemble chiffré homomorphe L >. En d’autres termes, le serveur 502 n’a aucun accès à des informations en clair concernant le client ou utilisateur 501. 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é (100) pour détecter la présence d’un élément chiffré homomorphe c > dans un ensemble chiffré homomorphe L >, l’ensemble chiffré homomorphe L > étant chiffré à l’aide d’une clé et étant mémorisé dans un serveur (502), ledit procédé (100) comprenant les étapes suivantes : Chiffrement totalement homomorphe (101), par un client (501) et à l’aide de la clé , d’un élément en clair µ pour obtenir l’élément chiffré homomorphe c > ; Réception (102) de l’élément chiffré homomorphe c > par le serveur (502) ; Application d’un opérateur d’extraction (103a) à l’ensemble chiffré homomorphe L > de sorte à extraire une empreinte de l’ensemble chiffré homomorphe ; Comparaison homomorphe (103b) de l’empreinte extraite de l’ensemble chiffré homomorphe et d’une fonction de l’élément chiffré homomorphe c > pour obtenir un indicateur de présence I > de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe L >, ladite comparaison étant effectuée sans déchiffrement de l’élément chiffré homomorphe c > et sans déchiffrement de l’ensemble chiffré homomorphe L >, ledit indicateur de présence I > étant sous forme chiffrée homomorphe ; Emission (104) de l’indicateur de présence I >. Procédé (100) selon la revendication précédente dans lequel l’indicateur de présence I > est de type booléen. Procédé (100) selon l’une des revendications précédentes dans lequel l’élément chiffré homomorphe c > est un identifiant d’un utilisateur, le client (501) étant associé audit utilisateur. Procédé (100) selon la revendication précédente dans lequel le serveur (502) est une plateforme d’achats (DSP). Procédé (100) selon l’une des revendications précédentes dans lequel l’indicateur de présence I > est émis vers une entité (503) configurée pour déchiffrer l’indicateur de présence I >, ladite entité (503) étant une boîte noire transactionnelle (HSM), ledit procédé (100) comprenant en outre une étape (105a) de réception de l’indicateur de présence I > par la boîte noire transactionnelle (HSM) et une étape (105b) de déchiffrement homomorphe de l’indicateur de présence I > par la boîte noire transactionnelle (HSM). Procédé (100) selon l’une des revendications précédentes dans lequel l’empreinte de la liste chiffrée homomorphe est un élément de la liste chiffrée 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é et dans lequel l’étape d’application d’un opérateur d’extraction (103a) d’une empreinte de la liste chiffrée homomorphe comprend : Obtenir un chiffré homomorphe (103a.1) 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 (103a.2) 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 (103a.3) en tant que produit modulaire homomorphe entre et ; Extraire le coefficient k (103a.4) 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’empreinte de la liste chiffrée homomorphe à extraire. Procédé (100) selon l’une des revendications précédentes dans lequel : L’ensemble chiffré homomorphe possède une structure de type filtre de Bloom (502b) de taille m , m étant un entier supérieur à 1, le filtre de Bloom comprenant h tableaux, h étant un entier supérieur ou égal à 1, chaque tableau étant associé à une fonction de hachage ; L’étape de chiffrement totalement homomorphe (101) de l’élément µ pour obtenir l’élément chiffré homomorphe c > est réalisée à l’aide de la formule suivante , comprenant h composantes, chaque composante étant obtenue an appliquant une des h fonctions de hachage à une quantité , la quantité étant le reste de la division de par m ; L’étape d’application d’un opérateur d’extraction (103a) comprend l’extraction de h pluralités d’éléments chiffrés homomorphes de l’ensemble chiffré homomorphe L >, chaque pluralité d’éléments chiffrés homomorphes extraits correspondant à un des h tableaux du filtre de Bloom ; L’étape de comparaison homomorphe (103b) comprend le calcul de h produits modulaires homomorphes entre pluralités d’éléments chiffrés homomorphes extraits et composantes de l’élément chiffré homomorphe c > ; L’indicateur de présence I > est déterminé à partir d’une fonction appliquée aux résultats des h produits modulaires homomorphes. Procédé (100) selon l’une des revendications 1 à 6 dans lequel : L’ensemble chiffré homomorphe est une liste triée chiffrée homomorphe ; L’empreinte de la liste chiffrée homomorphe extraite lors de l’application d’un opérateur d’extraction (103a) comprend un seul élément de la liste chiffré homomorphe ; L’étape d’application d’un opérateur d’extraction (103a) et l’étape de comparaison homomorphe (103b) sont répétées pour former une séquence de comparaisons homomorphes entre éléments extraits de la liste triée homomorphe et l’élément chiffré homomorphe c > de sorte à réaliser une recherche dichotomique de l’élément chiffré homomorphe c > dans la liste triée chiffrée homomorphe ; L’indicateur de présence I > est déterminé à partir de la dernière comparaison homomorphe de la séquence de comparaisons homomorphes. Client (501) configuré pour : réaliser une étape de chiffrement totalement homomorphe d’un élément en clair µ de sorte à obtenir un élément chiffré homomorphe c > conformément au procédé selon l’une quelconque des revendications précédentes ; Transmettre, au moyen d’un canal de communication (501c), l’élément chiffré homomorphe c > à un serveur (502) ; Serveur (502) configuré pour : Mémoriser la liste chiffrée homomorphe L > ; Appliquer un opérateur d’extraction (103a) de sorte à extraire une empreinte de l’ensemble chiffré homomorphe conformément au procédé selon l’une des revendications 1 à 8 ; Réaliser la comparaison homomorphe (103b) de la fonction de l’élément chiffré homomorphe c > et de l’empreinte extraite de l’ensemble chiffré homomorphe L > conformément au procédé selon l’une des revendications 1 à 8 et déterminer un indicateur I > de présence de l’élément chiffré homomorphe c > dans l’ensemble chiffré homomorphe L >, I > étant sous forme d’un chiffré homomorphe ; Émettre l’indicateur de présence I >. Système cryptographique (500) comprenant un client (501) selon la revendication 9, un serveur (502) selon la revendication 10 et une entité (503) configurée pour déchiffrer l’indicateur de présence I > émis par le serveur. Système cryptographique (500) selon la revendication précédente dans lequel l’entité configurée pour déchiffrer l’indicateur de présence I > est une boîte noire transactionnelle (HSM). Système cryptographique (500) selon la revendication 11 ou la revendication 12 dans lequel l’entité (503) configurée pour déchiffrer l’indicateur de présence I > est en outre configurée pour transmettre le résultat du déchiffrement de l’indicateur de présence I > au serveur (502). Produit programme d’ordinateur comprenant des instructions exécutables par un ordinateur et conçues pour la mise en œuvre du procédé selon l’une des revendications 1 à 8 lorsque ces instructions sont exécutées par le processeur.