Brevet FR3134672A1 — publié le 20231020

La présente invention concerne une méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données hébergée par un serveur, lesdits enregistrements étant stockés dans la base de données sous forme d’empreintes numériques, chaque empreinte numérique étant obtenue par hachage d’un enregistrement au moyen d’une fonction de hachage publique. Les empreintes sont masquées au moyen d’un chiffrement par flot à partir d’une clé symétrique d’un premier utilisateur. Le premier utilisateur peut accorder à un second utilisateur l’autorisation d’interroger la base de données en transmettant au serveur les masques inverses des différentes lignes, chiffrés par la clé publique d’un cryptosystème homomorphe additif du second utilisateur. Les lignes de la base de données sont démasquées (325) dans le domaine homomorphe et le second utilisateur transmet une requête chiffrée (340) pour interroger la base selon un protocole PIR. Le second utilisateur peut alors déchiffrer (350) la réponse du serveur à l’aide de la clé privée de son cryptosystème homomorphe et déterminer (360) si l’empreinte de l’enregistrement recherché est présente ou non dans la réponse ainsi déchiffrée. Fig. 3 METHODE D’INTERROGATION CONFIDENTIELLE MULTI-UTILSATEUR DE LA PRÉSENCE D’UN ENREGISTREMENT DANS UNE BASE DE DONNÉES La présente invention concerne de manière générale le domaine de l’interrogation confidentielle d’une base de données. Elle fait appel au chiffrement homomorphe additif et au requêtage par protocole PIR ( Private Information Retrieval ). Etat de la technique antérieure L’interrogation confidentielle d’une base de données permet à un client d’extraire des données d’une base hébergée par un serveur distant, sans divulgation à des tiers ou au serveur lui-même, de l’objet de la requête et du résultat de celle-ci. Les méthodes d’interrogation confidentielle font généralement appel à un traitement par chiffrement homomorphe de la base de données requêtée. On peut distinguer celles qui utilisent un chiffrement pleinement homomorphe ou FHE ( Full Homomorphic Encryption ) de la base de données et celles qui utilisent simplement un chiffrement homomorphe additif. Les premières autorisent une grande variété de types de requête mais ne permettent pas un passage à l’échelle en termes de taille de la base de données, autrement dit elles ne sont pas scalables à des tailles de la base importantes, à tout de moins pour des temps de latence (c’est-à-dire de réponse à une requête) inférieurs à une valeur de seuil acceptable (typiquement de quelques minutes). Les secondes ne permettent que des requêtes de format contraint mais autorisent un passage à l’échelle aisé relativement à la taille de la base de données. Le protocole PIR ( Private Information Retrieval ) est une méthode d’interrogation confidentielle de base de données faisant appel à un traitement par chiffrement homomorphe additif utilisant le cryptosystème de Paillier. On trouvera par exemple une description d’une méthode d’interrogation confidentielle d’une base de données au moyen du protocole PIR dans l’article intitulé « EncryptedQuery scalable Private Information Retrieval », EnQuery, 29.11.2018. Cette méthode d’interrogation confidentielle correspond toutefois à un cas d’usage mono-utilisateur. En effet, les données stockées dans la base sont des valeurs hachées obtenues au moyen d’une fonction de hachage cryptographique à clé privée, ladite clé privée appartenant à l’utilisateur. Ainsi, si un second utilisateur souhaite requêter la base en question, la clé privée utilisée dans la fonction de hachage doit être communiquée au second utilisateur, sans passer par le serveur, de manière à préserver la confidentialité vis-à-vis de ce dernier. De manière plus générale, si différents utilisateurs disposent chacun d’une base de données (du type envisagé ci-dessus) et souhaitent partager leurs droits d’accès, ils doivent s’échanger leurs clés privées, ce qui n’est pas une solution satisfaisante. En outre, on comprend dans ce scénario qu’il y a autant de clés privées que de bases de données, ce qui conduit à une multiplication du nombre de requêtes pour une même interrogation. Le but de la présente invention est de proposer une méthode d’interrogation multi-utilisateur d’une base de données qui ne présente pas les inconvénients de l’art antérieur, en particulier qui ne nécessite pas un échange d’informations confidentielles entre lesdits utilisateurs lorsqu’un utilisateur souhaite autoriser un autre à accéder à ladite base. Présentation de l’invention La présente invention est définie par une méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données hébergée par un serveur, lesdits enregistrements étant stockés dans la base de données sous forme d’empreintes numériques, chaque empreinte numérique étant obtenue par hachage d’un enregistrement au moyen d’une fonction publique de hachage et chaque ligne de la base de données contenant les empreintes numériques partageant leurs premiers bits, ladite méthode d’interrogation confidentielle étant originale en ce que : - un premier utilisateur dispose d’une clé symétrique de chiffrement par flot et un second utilisateur dispose d’un cryptosytème homomorphe au moins additif ; - les lignes de la base de données sont chiffrées au moyen dudit chiffrement par flot par addition de masques ayant chacun la taille d’une ligne de la base de données ; - le premier utilisateur autorise l’accès à la base de données au second utilisateur en chiffrant les masques inverses au moyen de la clé publique dudit cryptosystème homomorphe et en transmettant les masques inverses ainsi chiffrés au serveur; - les lignes de la base de données sont transchiffrées dans le domaine homomorphe par addition aux dites lignes des masques inverses ainsi chiffrés ; - le second utilisateur calcule l’empreinte numérique de l’enregistrement au moyen de ladite fonction publique de hachage et en déduit une valeur entière, , correspondant aux premiers bits; - le second utilisateur construit une requête sous la forme d’un premier vecteur de taille constitué d’un chiffré homomorphe de la valeur « 1 » en position et de chiffrés homomorphes de la valeur « 0 » aux autres positions, la requête étant transmise au serveur ; - le serveur évalue dans le domaine homomorphe le produit scalaire entre le premier vecteur et un second vecteur de taille constitué par les lignes chiffrées de la base de données, le résultat étant transmis comme réponse au second utilisateur; - le second utilisateur déchiffre ladite réponse au moyen de la clé privée de son cryptosystème homomorphe et en déduit le contenu en clair de la ligne de la base de données ; - le second utilisateur recherche si l’empreinte numérique de l’enregistrement se trouve parmi les empreintes numériques de la ligne ainsi obtenue. Le chiffrement par flot pourra utiliser une primitive de chiffrement choisie par exemple parmi AES-CTR, Trivium et Grain. La fonction publique de hachage cryptographique pourra être SHA-3. Selon un mode avantageux de réalisation, le cryptosystème homomorphe est un chiffrement homomorphe additif. Le chiffrement homomorphe additif pourra utiliser de préférence un cryptosystème de Paillier de clé publique avec où sont deux nombres premiers. Dans ce cas, le serveur retourne comme réponse un premier et un second chiffrés stockés à la ligne , le second utilisateur effectuant un déchiffrement de chacun des premier et second chiffrés au moyen de la clé privée de son cryptosystème homomorphe, puis effectue un déchiffrement au moyen de cette même clé privée des résultats ainsi obtenus après les avoir concaténés. Selon une variante, le chiffrement homomorphe additif utilise une pluralité de chiffrés de « 0 » par un chiffrement de Pallier, , ,le chiffrement homomorphe additif d’un entier étant obtenu par : où , sont des bits aléatoires sélectionnant lesdits chiffrés de « 0 ». Avantageusement, les chiffrés de « 0 » sont calculés une fois pour toutes et stockés par le second utilisateur. Le transchiffrement des lignes de la base de données peut être réalisé une fois pour toutes par le serveur lorsque le second utilisateur a été autorisé à interroger la base de données par le premier utilisateur. Alternativement, le transchiffrement des lignes de la base de données est réalisé de manière dynamique par le serveur à chaque interrogation du second utilisateur. D’autres caractéristiques et avantages de l’invention apparaîtront à la lecture d’un mode de réalisation préférentiel de l’invention, fait en référence aux figures jointes parmi lesquelles : représente de manière schématique le contexte d’application de la présente invention ; représente de manière schématique la structure de la base de données utilisée dans la ; représente de manière schématique une méthode d’interrogation d’une base de données selon un mode de réalisation de la présente invention ; Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données hébergée par un serveur, lesdits enregistrements étant stockés dans la base de données sous forme d’empreintes numériques, chaque empreinte numérique étant obtenue par hachage d’un enregistrement au moyen d’une fonction publique de hachage et chaque ligne de la base de données contenant les empreintes numériques partageant leurs premiers bits, caractérisée en ce que : un premier utilisateur dispose d’une clé symétrique de chiffrement par flot et un second utilisateur dispose d’un cryptosytème homomorphe au moins additif (310) ; les lignes de la base de données sont chiffrées au moyen dudit chiffrement par flot par addition de masques ayant chacun la taille d’une ligne de la base de données ; le premier utilisateur autorise l’accès à la base de données au second utilisateur en chiffrant les masques inverses au moyen de la clé publique dudit cryptosystème homomorphe et en transmettant les masques inverses ainsi chiffrés au serveur (315) ; les lignes de la base de données sont transchiffrées (325) dans le domaine homomorphe par addition aux dites lignes des masques inverses ainsi chiffrés ; le second utilisateur calcule l’empreinte numérique de l’enregistrement au moyen de ladite fonction publique de hachage et en déduit une valeur entière, , correspondant aux premiers bits (330) ; le second utilisateur construit une requête sous la forme d’un premier vecteur de taille constitué d’un chiffré homomorphe de la valeur « 1 » en position et de chiffrés homomorphes de la valeur « 0 » aux autres positions, la requête étant transmise au serveur (340) ; le serveur évalue dans le domaine homomorphe le produit scalaire entre le premier vecteur et un second vecteur de taille constitué par les lignes chiffrées de la base de données, le résultat étant transmis comme réponse au second utilisateur (345); le second utilisateur déchiffre ladite réponse au moyen de la clé privée de son cryptosystème homomorphe et en déduit le contenu en clair de la ligne de la base de données (350) ; le second utilisateur recherche si l’empreinte numérique de l’enregistrement se trouve parmi les empreintes numériques de la ligne ainsi obtenue (360). Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon la revendication 1 caractérisée en ce que le chiffrement par flot utilise une primitive de chiffrement choisie parmi AES-CTR, Trivium et Grain. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon la revendication 1 ou 2, caractérisée en ce que la fonction publique de hachage cryptographique est SHA-3. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon l’une des revendications précédentes, caractérisée en ce que le cryptosystème homomorphe est un chiffrement homomorphe additif sans être FHE. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon la revendication 4, caractérisée en ce que le chiffrement homomorphe additif utilise un cryptosystème de Paillier de clé publique avec où sont deux nombres premiers. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon la revendication 5, caractérisée en ce que le serveur retourne comme réponse un premier et un second chiffrés stockés à la ligne , le second utilisateur effectuant un déchiffrement de chacun des premier et second chiffrés au moyen de la clé privée de son cryptosystème homomorphe, puis effectue un déchiffrement au moyen de cette même clé privée des résultats ainsi obtenus après les avoir concaténés. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon la revendication 5, caractérisée en ce que le chiffrement homomorphe additif utilise une pluralité de chiffrés de « 0 » par un chiffrement de Pallier, , ,le chiffrement homomorphe additif d’un entier étant obtenu par : où , sont des bits aléatoires sélectionnant lesdits chiffrés de « 0 ». Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon la revendication 7, caractérisée en ce que les chiffrés de « 0 » sont calculés une fois pour toutes et stockés par le second utilisateur. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon l’une des revendications précédentes, caractérisée en ce que le transchiffrement des lignes de la base de données est réalisée une fois pour toutes par le serveur lorsque le second utilisateur a été autorisé à interroger la base de données par le premier utilisateur. Méthode d’interrogation confidentielle de la présence d’un enregistrement dans une base de données selon l’une des revendications 1 à 8, caractérisée en ce que le transchiffrement des lignes de la base de données est réalisé de manière dynamique par le serveur à chaque interrogation du second utilisateur.