Brevet FR3042625A1 (20170421)
REVENDICATIONS1. Méthode d'interrogation confidentielle d'une base de données hébergée par un 5 serveur, la base de données contenant une table d'enregistrements, chaque enregistrement étant obtenu au moyen d'un chiffrement totalement homomorphe voire partiellement homomorphe de valeurs en clair, dans laquelle : (a) l'utilisateur transmet (310) une requête (R), comprenant un prédicat au serveur ; 10 (b) le serveur (320) calcule la valeur booléenne chiffrée du prédicat pour chaque enregistrement de la table ; caractérisée en ce que : (c) le serveur (330) construit un conteneur ( ) comprenant un nombre prédéterminé (K) d'emplacements et stocke à l'aveugle aux dits emplacements des 15 enregistrements vérifiant le prédicat et non déjà transmis à l'utilisateur, à partir des valeurs booléennes chiffrées ( , i =1,...,N) obtenues à l'étape (b); (d) le serveur transmet (340) à l'utilisateur le conteneur ainsi construit ; (e) l'utilisateur reçoit le conteneur, déchiffre le contenu de chaque emplacement(350), et détermine si le conteneur est plein ou non (360); 20 (f1) si le conteneur est plein, l'utilisateur transmet (380) une requête de continuation (RC', ) au serveur pour une nouvelle itération des étapes (c),(d) et (e) ; (f2) si le conteneur n'est pas plein, l'utilisateur obtient la réponse à ladite requête (370) à partir des enregistrements stockés dans les conteneurs reçus et déchiffrés à l'étape ou aux étapes (e). 25\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la revendication 1, caractérisée en ce que la table d'enregistrements est représentée par une matrice T de taille N xP où N est le nombre d'enregistrements de la table et P le nombre de champs de ces enregistrements, un élément chiffré A de la matrice étant 3042625 21 Q-1 obtenu à partir de sa valeur en clair A = Iaq2q par Aao,a1,...,aQ_i où a q q=0 q=0,...,Q-1 sont les bits de la valeur en clair et a, ,q=0,...,Q-1 sont leurs chiffrés correspondants, obtenus par ledit chiffrement totalement homomorphe voire partiellement homomorphe.\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la revendication 2 caractérisée en ce que le prédicat est évalué sur les différents enregistrements au moyen d'opérations additives 0 et multiplicatives 0 portant sur les éléments chiffrés.\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la revendication 3, caractérisée en ce que le conteneur est représenté par une matrice B de taille KxP avec K\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la revendication 4, caractérisée en ce que l'opération d'affectation d'un vecteur û de P 25 élément chiffrés à la k ème ligne d'une matrice H=(h) d'éléments chiffrés de taille KxP 10 3042625 22 donne une matrice G = (glu) d'éléments chiffrés, de même taille, telle que Dec(gii)=Dec(hii) dis k et Dec(gki)=Dec(ui), 1\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la 5 revendication 4 ou 5, caractérisée en ce que le booléen chiffré est calculé au moyen de _ - ^ c =ri®(niasi\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la revendication 6, caractérisée en ce que la variable chiffrée idx est mise à jour à chaque - - - enregistrement balayé par id, = + r .\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon la revendication 6 ou 7, caractérisée en ce que l'indice chiffré k de la ligne de la matrice B est mis à jour à chaque enregistrement balayé par k=k+c\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon l'une quelconque des revendications précédentes, caractérisée en ce que la base de données est partitionnée en portions de taille NIL à l'exception éventuellement d'une portion, les étapes (c),(d),(e), (f1)-(f2) étant effectuées, en série ou en parallèle, sur chacune desdites portions de la base. 3042625 23\n<CLM>\1\tMéthode d'interrogation confidentielle d'une base de données selon l'une quelconque des revendications précédentes, caractérisée en ce que la méthode de chiffrement totalement homomorphe utilise un cryptosystème de Brakerski. 5