Brevet FR3042625A1 — publié le 20170421

MÉTHODE D'INTERROGATION CONFIDENTIELLE D'UNE BASE DE DONNÉES CHIFFRÉE DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne le domaine de l'interrogation confidentielle d'une base de données chiffrée. L'invention fait appel à la cryptographie entièrement homomorphe ou FHE (Full Homomorphic Encryption) voire à la cryptographie partiellement homomorphe ou SWHE (SomeWhat Homomorphic Encryption). Elle s'applique plus particulièrement à un contexte d'informatique en nuage (cloud computing). ÉTAT DE LA TECHNIQUE ANTÉRIEURE Le développement récent de l'informatique en nuage a permis à de nombreuses entreprises d'externaliser leurs bases de données dans des centres de données (data centers). Toutefois cette nouvelle pratique, si elle permet de réduire des investissements lourds dans des équipements informatiques, ne va pas sans poser de sérieux problèmes de confidentialité, tant des données stockées dans la base que du contenu des requêtes de recherche. Dans la plupart des secteurs d'activité, notamment dans le domaine médical, financier ou économique, il est essentiel que la confidentialité des données et du contenu des requêtes puisse être garantie non seulement vis-à-vis d'un tiers malveillant mais également vis-à-vis du fournisseur de service informatique en nuage lui-même. Pour satisfaire à cette exigence de confidentialité, on est naturellement conduit à effectuer un chiffrement de tout ou partie des données de l'utilisateur stockées dans la base. Toutefois un simple chiffrement s'avère insuffisant en pratique dans la mesure où la recherche des enregistrements répondant à une requête de l'utilisateur révèle les emplacements où ceux-ci sont stockés. Un tiers malveillant, voire le fournisseur lui-même, peut alors associer les enregistrements chiffrés aux requêtes de l'utilisateur et en déduire des informations confidentielles. 3042625 2 L'article de S. Wang et al. intitulé « Is homomorphic encryption the Holy Grail for data base queries on encrypted data ? », Technical report, Université de Californie, Santa Barbara, 2012, propose une méthode d'interrogation confidentielle d'une base de données dont les enregistrements sont chiffrés au moyen d'un cryptosystème totalement 5 homomorphe. On rappelle tout d'abord qu'un chiffrement totalement homomorphe ou FHE (Full Homomorphic Cryptography) est un chiffrement asymétrique EncPk (de clé publique pk ) vérifiant les relations suivantes: 10 EncPk : X Y Va,be X, EncPk (a + b)= EncPk (a)0 EncPk (b) Va,bE X, EncPk (a.b)= EncPk (a)0 EncPk (b) (1-2) où X est l'espace des messages clairs (dit plus simplement espace des clairs) et Y est 15 l'espace des messages chiffrés (dit plus simplement espace des chiffrés), + et . sont respectivement une opération additive et une opération multiplicative dans l'espace des clairs conférant à X une structure d'anneau ( X,+,.), 0 et 0 sont des opérations correspondantes dans l'espace des chiffrés conférant à Y une structure d'anneau ( Y , 0 , 0 ). On comprend des expressions (1-1) et (1-2) que l'application EncPk de (X , +,.) 20 dans ( Y , 0 , O) est un homomorphisme d'anneaux. En pratique, un chiffrement totalement homomorphe est un chiffrement probabiliste, c'est-à-dire dépendant d'un paramètre aléatoire (ou bruit) r . Le chiffrement d'un message clair m peut ainsi donner différents messages chiffrés EncPk(m,r) suivant la valeur prise par le paramètre r . Toutefois, quelle que soit la valeur prise par ce 25 paramètre, le déchiffrement de EncPk(m,r) redonne toujours le message clair m. Si l'on note Dec$k la fonction de déchiffrement correspondant à EncPk (où sk est la clé secrète de l'utilisateur), on a donc : 3042625 3 Dece(Enc pk(m,r))=m (2) Dans la suite, on adoptera une notation plus simple pour alléger l'exposé, soit r 71= EncPk (m' r) et l'on conviendra d'omettre dans les expressions de chiffrement/ 5 déchiffrement la mention des clés publique et privée. Ainsi, on a Dec(r71)=m. On définit un cryptosystème par un couple d'une fonction de chiffrement Enc(.) et d'une fonction déchiffrement Dec(.). Ainsi, un cryptosystème totalement homomorphe, vérifie avec les notations précédentes : 10 DecP eq= a+b (3-1) Dec[Ft OT,1= ab (3-2) 15 Autrement dit, un chiffrement totalement homomorphe permet de calculer n'importe quelle combinaison d'opérations d'addition et de multiplication sur des clairs à partir d'opérations correspondantes sur les chiffrés. En règle générale, l'espace des clairs est le corps des booléens x = z /2Z, l'opération additive étant un OU exclusif (XOR) et l'opération multiplicative un ET (AND). Il est alors possible d'effectuer des opérations 20 logiques sur des valeurs booléennes à partir d'opérations correspondantes sur leurs valeurs chiffrées. Il convient de noter que lorsque la méthode de chiffrement ne permet de calculer des combinaisons d'opérations d'addition et de multiplication sur des clairs qu'avec une certaine profondeur de combinaison, on préfère utiliser le qualificatif de « partiellement 25 homomorphe ». L'article de S. Wang précité propose de calculer un booléen chiffré pour chaque enregistrement de la base données, ce booléen indiquant si l'enregistrement en question satisfait ou non à la requête de l'utilisateur. Le serveur ne connaissant pas le nombre 3042625 4 d'enregistrements satisfaisant à la requête, l'utilisateur lui fournit une borne supérieure, M', du nombre d'enregistrements qui peuvent lui être retournés, ainsi qu'un paramètre de qualité de résultat 7 . Le serveur utilise un buffer de taille fixe B proportionnelle à yM' dans lequel il stocke les enregistrements, chaque enregistrement 5 du buffer étant stocké de manière aléatoire parmi les y positions du buffer. Un enregistrement ne répondant pas à la requête est stocké sous forme d'une valeur nulle chiffrée ( 0 ) et n'a donc pas d'influence sur le déchiffrement. En revanche, un enregistrement correspondant à la requête est stocké et pourra être déchiffré s'il n'entre pas en collision avec un autre enregistrement. Cette approche probabiliste n'est toutefois 10 pas entièrement satisfaisante dans la mesure où la réponse du serveur peut ne pas être exhaustive, son degré d'exhaustivité dépendant du paramètre de qualité y . Afin de remédier à ce défaut d'exhaustivité, l'article de M. Mani et al. intitulé « Enabling secure database as a service using fully homomorphic properties : challenges and opportunities », publié dans arXiv preprint, 13 Février 2013, pp. 1-13 propose de 15 calculer un booléen chiffré pour chaque enregistrement de la base de données, comme précédemment, puis de procéder en deux temps. Dans un premier temps, le serveur du fournisseur de service détermine le nombre M d'enregistrements répondant à la requête (nombre de « hits ») en sommant les booléens chiffrés, et le transmet à l'utilisateur. Celui-ci déchiffre ce nombre et demande au serveur de lui transmettre M ' > M premiers 20 enregistrements. Le nombre M' est transmis en clair. Le serveur ordonne alors de manière confidentielle les enregistrements selon les valeurs des booléens chiffrés, autrement dit les M' premiers enregistrements de la table ainsi ordonnée contiennent les M enregistrements satisfaisant à la requête. Cette méthode permet de cacher le nombre M d'enregistrements correspondant au résultat. 25 Cette méthode d'interrogation confidentielle préserve bien la confidentialité du résultat mais présente l'inconvénient de requérir un ordonnancement de toute la base de données à chaque requête. Le but de la présente invention est par conséquent de proposer une méthode d'interrogation confidentielle d'une base de données, chiffrée par chiffrement totalement 3042625 5 homomorphe voire partiellement homomorphe, qui remédie à tout ou partie des inconvénients précités, en particulier qui présente un haut degré de confidentialité sans accroissement sensible de la complexité des calculs. 5 EXPOSÉ DE L'INVENTION La présente invention est définie par une méthode d'interrogation confidentielle d'une base de données hébergée par un 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 10 laquelle : (a) l'utilisateur transmet une requête (R ), comprenant un prédicat au serveur ; (b) le serveur calcule la valeur booléenne chiffrée du prédicat pour chaque enregistrement de la table ; (c) le serveur construit un conteneur ( 13m) comprenant un nombre prédéterminé 15 (K) d'emplacements et stocke à l'aveugle aux dits emplacements des enregistrements vérifiant le prédicat et non déjà transmis à l'utilisateur, à partir des valeurs booléennes chiffrées ( obtenues à l'étape (b); (d) le serveur transmet à l'utilisateur le conteneur ainsi construit ; (e) l'utilisateur reçoit le conteneur, déchiffre le contenu de chaque emplacement, 20 et détermine si le conteneur est plein ou non; (f1) si le conteneur est plein, l'utilisateur transmet une requête de continuation ( RCm) 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 à partir des enregistrements stockés dans les conteneurs reçus et déchiffrés à l'étape ou 25 aux étapes (e). La table d'enregistrements est avantageusement représentée par une matrice T de taille NxP 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 obtenu à partir 3042625 6 Q-1 de sa valeur en clair A = 2g par A où a q, q=0,...,Q-1 sont les bits q=0 de la valeur en clair et aq , q=0,...,Q-1 sont leurs chiffrés correspondants, obtenus par ledit chiffrement totalement homomorphe voire partiellement homomorphe. Le prédicat est évalué sur les différents enregistrements, typiquement au moyen 5 d'opérations additives 0 et multiplicatives 0 portant sur les éléments chiffrés. Le conteneur est avantageusement représenté par une matrice B de taille K x P avec K , > ) ou encore un opérateur d'égalité (==). 15 Le serveur évalue le prédicat (c'est-à-dire calcule sa valeur logique) sur les différents enregistrements de la table T et forme un vecteur r de taille N dont les éléments sont des booléens représentant les valeurs logiques ainsi obtenues. Il est essentiel de noter que l'évaluation du prédicat est effectuée sur des chiffrés et non sur des clairs, et que les booléens donnant les valeurs logiques des différents enregistrements sont également 20 chiffrés. En d'autres termes, le serveur ne peut distinguer dans la table les enregistrements correspondant à une valeur vraie et ceux correspondant à une valeur fausse du prédicat. Notons que le serveur n'a pas davantage accès au nombre de résultats, c'est-à-dire au nombre d'enregistrements M donnant lieu à une valeur vraie du prédicat. La méthode d'interrogation confidentielle selon l'invention met en oeuvre un 25 conteneur, également dénommé seau (bucket), de taille fixe, pouvant contenir jusqu'à K enregistrements, au moyen duquel les résultats de la requête sont retournés à l'utilisateur. Plus précisément, le serveur passe en revue tous les enregistrements de la table et transfère à l'aveugle dans le conteneur ceux qui satisfont à la requête, c'est-à-dire ceux 3042625 10 pour lesquels la valeur du prédicat est vraie. Le transfert à l'aveugle est effectué au moyen d'une opération d'affectation détaillée plus loin. Elle garantit que le serveur (ou un tiers malveillant effectuant une attaque sur le serveur) ne puisse déterminer les enregistrements effectivement transférés dans le conteneur. Les emplacements du 5 conteneur dans lesquels un enregistrement n'a pas été transféré contiennent des valeurs chiffrées 0 (indiquant conventionnellement que l'emplacement est vide). La réponse du serveur à l'utilisateur est répartie sur un nombre lit de conteneurs, /31,...,B,' où /h = rm / K1 est la partie entière par excès de la fraction M / K . Le serveur ne peut déterminer à l'avance le nombre lit de conteneurs puisque le nombre M de 10 résultats ne lui est pas révélé. Pour chaque conteneur Bm reçu, l'utilisateur déchiffre le contenu des différents emplacements du conteneur. Si l'utilisateur arrive à un emplacement ne contenant que des 0 celui-ci sait alors qu'il a obtenu tous les résultats. A défaut, si un tel emplacement n'est pas détecté, l'utilisateur renvoie au serveur une requête de continuation, RC', . Le transfert des résultats se fait ainsi par passage de 15 conteneurs (ou seaux) sur demande de l'utilisateur. Au final, le serveur connait indirectement le nombre de conteneurs transférés pour une requête c'est-à-dire la valeur th mais ne connait le nombre de résultats qu'à un nombre K -1 d'enregistrements près. 20 On a représenté sur la figure, la requête initiale R de l'utilisateur et ses requêtes de continuation Rcm, m=1,..,rh-1 successives. En réponse aux requêtes R,RCi,...,RC,T, le serveur transmet respectivement les conteneurs Bm, m=1,..,rh, comme expliqué ci-après. En réponse à la requête R de l'utilisateur, le serveur évalue le prédicat sur chacun 25 des enregistrements de la table T. Cette évaluation se fait bien entendu sur les valeurs chiffrées. Par exemple, si la requête consiste à obtenir tous les enregistrements tels que le contenu F - d'un champ est égal à une valeur chiffrée donnée D, - c'est-à-dire si le prédicat est F =D, où fQ_1...fi fo et dQ_i...dido sont les représentations binaires respectives de 3042625 F et D, on aura : (F-D)=0PC) f CM) g_o 5 _ Autrement dit, l'évaluation du prédicat (F =D) donne une valeur booléenne chiffrée égale à 1 (valeur logique TRUE) si le champ F de l'enregistrement est égal à D et égale à 0 (valeur logique FALSE) dans le cas contraire. D'autres prédicats mettant en oeuvre des opérateurs de comparaison et/ou des 10 opérateurs arithmétiques (0 et O) pourront être utilisés. De manière générale, la valeur logique d'un prédicat peut être obtenue à partir d'opérations 0 et 0 sur les éléments chiffrés d'un enregistrement. On trouvera par exemple le calcul d'un prédicat de comparaison dans l'article de M. Mani et al. précité. En tout état de cause, le serveur évalue le prédicat sur chaque enregistrement 15 i =1,...,N de la table et en déduit un vecteur r de taille N dont les éléments r, sont les résultats de cette évaluation. On définit ensuite un opérateur d'affectation conditionnelle se/ permettant d'affecter un premier mot chiffré A ou un second mot chiffré B à une variable V selon la valeur d'un booléen chiffré F. , de la manière suivante : 20 V =Sel(171,É;F) v,=(co a jep cjob,), q=0,...,Q-1 (7) _ - On comprend de l'expression (7) que le mot chiffré A est assigné à V si c est un 25 chiffré de 1 et que le mot chiffré B est assigné à V si c est un chiffré de O. Il est essentiel de noter que cette affectation est réalisée de manière aveugle, c'est-à-dire que le serveur 11 (6) 3042625 12 calculant l'expression (7) n'a aucun moyen de déterminer lequel des mots A et B est effectivement assigné à V. En effet, en l'absence de la clé de déchiffrement, le serveur ne sait pas si c est un chiffré de 1 ou O. En outre, le mot chiffré assigné étant modifié par le calcul de l'expression (7), il n'est pas possible de déduire cette affectation d'une simple 5 comparaison de V avec A et B. L'opérateur d'affectation Sel permet d'affecter de manière aveugle une valeur chiffrée à un élément d'un vecteur. Plus précisément, si l'on note v =(v1,...,vp) un vecteur de chiffrés et k le chiffré d'un indice k , 1 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 2. Mé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. 3. Mé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. 4. Mé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 5. Mé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 6. Mé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 7. Mé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 . 8. Mé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 9. Mé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 10. Mé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