Note: Descriptions are shown in the official language in which they were submitted.
CA 03050353 2019-07-16
WO 2018/150119 1
PCT/FR2018/050276
PROCEDE DE RECHERCHE D'INFORMATIONS DANS UN CORPUS CHIFFRE
STOCKE SUR UN SERVEUR
Domaine de l'invention
Le domaine de l'invention concerne la recherche
d'informations dans une base de données sous une forme
préservant la confidentialité des données et des requêtes.
L'application concerne notamment les systèmes de
traitements de données personnelles, et en particulier de
données de santé.
Les bases de données font partie intégrante dans de
nombreuses applications, telles que les applications
financières et les applications de cybersanté médicales. Les
bases de données peuvent être très sensibles, contenant des
données précieuses d'une entreprise ou d'individus. Le vol de
données sensibles est une préoccupation croissante pour les
individus, les entreprises et les gouvernements.
Les bases de données peuvent être constituées de
collections de fichiers bruts ou gérées à l'aide du système de
gestion de base de données (SGBD), telles que la base de
données Oracle, MySQL, Microsoft SQL Server, etc. Une base de
données peut être déployée sur un serveur au sein d'une
entreprise, sur un serveur virtuel dans un nuage ( cloud en
anglais), ou sur un service de SGBD dans un nuage. Le vol de
données est une préoccupation pour chaque type de déploiement.
Lorsque les bases de données sont déployées sur un
serveur dans les locaux d'une entreprise, le serveur est
physiquement sous le contrôle de l'entreprise. Si le serveur
est compromis ou infecté par des logiciels malveillants ou des
virus, les pirates pourraient être en mesure d'accéder au
fichier de données de base de données brutes et de voler les
données en contournant tout mécanisme de contrôle d'accès de
l'entreprise. D'autre part, les administrateurs de bases de
CA 03050353 2019-07-16
WO 2018/150119 2
PCT/FR2018/050276
données de l'entreprise ont la possibilité de violer la vie
privée et l'intégrité des données intentionnellement ou
accidentellement, car ils peuvent accéder aux données stockées
pour effectuer les tâches de gestion de base de données. Un
système de base de données peut également être déployé par une
entreprise sur un serveur virtuel, qui fonctionne sur un nuage
comme Amazon Elastic Compute Cloud (Amazon EC2). Dans ce cas,
le serveur virtuel qui sous-tend la base de données est
physiquement sous le contrôle du fournisseur de nuage, et sur
le serveur virtuel de l'entreprise installe SGBD pour gérer
leurs bases de données. Comme dans le cas ci-dessus, le vol de
données se produit également dans ce cas, si l'infrastructure
cloud est compromise par des attaquants, infectée par des
logiciels malveillants ou des virus, et les administrateurs de
bases de données de l'entreprise pourraient violer la
confidentialité et l'intégrité des bases de données.
En outre, si les fournisseurs de cloud ne sont pas
tous dignes de confiance ; ils peuvent voler des données de
base de données dans les serveurs virtuels fournis par eux.
Pour pallier à ces risques, on a récemment envisagé
l'utilisation de solutions utilisant des méthodes de
chiffrement homomorphe (ou Homomorphic Encryption, HE, en
anglais) pour l'interrogation de bases de données.
Les méthodes de chiffrement homomorphe ont
notamment été développées pour des applications de moteur de
recherche : l'utilisateur envoie une requête chiffrée au
moteur de recherche, sans que ce dernier n'ait connaissance de
la requête reçue. Il applique une opération classique de
recherche de documents correspondants et renvoie la réponse à
l'utilisateur de façon chiffrée. Ainsi, le moteur de recherche
ne connaît jamais le contenu en clair la requête.
Ces méthodes de chiffrement homomorphe permettent
aussi de faire une recherche parmi des fichiers chiffrés sur
un serveur distant pour récupérer les fichiers qui contiennent
CA 03050353 2019-07-16
WO 2018/150119 3
PCT/FR2018/050276
un terme transmis sous la forme d'une requête transmise de
façon chiffrée à un serveur distant. Le serveur applique la
recherche sans connaître ce les termes de la requête en clair
et retourne le résultat. Le serveur ne connaît jamais ni les
requêtes ni les documents enregistrés dans la base de données
autrement que sous une forme chiffrée. Une attaque du serveur
ne crée de ce fait aucun risque en ce qui concerne la
confidentialité des informations, par exemple des données
personnelles ou des données de santé.
Une autre application concerne la biométrie
exploitant une base d'empreintes digitales des personnes
autorisées à effectuer une action, par exemple entrer dans un
bâtiment protégé. Ces empreintes sont naturellement chiffrées,
car ce sont des données personnelles non révocables.
Les utilisateurs scannent leurs empreintes
digitales et ces empreintes sont comparées à celles dans la
base de données. Deux empreintes digitales d'une même personne
prises à deux moments différents ne sont jamais strictement
identiques et il n'est donc pas possible de faire une simple
comparaison des empreintes chiffrées (deux chiffrés de deux
empreintes différentes sont évidemment différents). Grâce au
chiffrement homomorphe, il est possible de comparer les
empreintes digitales chiffrées sans jamais les déchiffrer.
Etat de la technique
On connaît dans l'état de la technique un document
présentant les bases du chiffrement homomorphe, qui est la
thèse A FULLY HOMOMORPHIC ENCRYPTION SCHEME: A DISSERTATION
SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE
COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY en
septembre 2009, qui décrit au chapitre 7 les principes de base
de l'application à la recherche d'informations.
CA 03050353 2019-07-16
WO 2018/150119 4
PCT/FR2018/050276
On connaît aussi
l'article Multi-keyword
Similarity Search over Encrypted Cloud Data ; Mikhail
Strizhov 1 Indrajit Ray 1 29th IFIP International Information
Security Conference (SEC), Jun 2014, Marrakech, Morocco.
Springer, IFIP. Cet article décrit une solution basée sur le
chiffrement homomorphe pour la recherche de documents chiffrés
sur un serveur sans nécessiter que les documents soient
déchiffrés avant la recherche.
On connaît aussi le brevet américain US8904171
décrivant un procédé de recherche sécurisée et de récupération
d'informations qui comprend la réception d'une requête
chiffrée, la création d'un arbre de recherche permuté avec des
n uds qui ont été permutés et chiffrés.
L'arbre de recherche est chiffré avec une première
clé de chiffrement privée. Le serveur reçoit une requête d'un
client, la requête comprenant un ensemble de mots-clés, dans
lequel chaque terme de requête est chiffré avec la première
clé de chiffrement privée. La recherche est effectuée en
utilisant une requête et une évaluation à chaque n ud de
l'arbre afin de déterminer si une ou plusieurs correspondances
existent. La réponse est basée sur la concordance de mots-clés
pour chaque document et un ou plusieurs n uds chiffrés avec la
première clé de chiffrement privée.
On connaît encore le brevet européen EP2865127
décrivant un chiffrement homomorphe pour interrogation de base
de données. Des valeurs numériques sont chiffrées à l'aide de
clés et de nombres aléatoires afin de produire un texte
chiffré. Le texte chiffré est homomorphe et est composé de
deux sous-textes chiffrés ou plus. Des interrogations faisant
appel à des opérations d'addition, de moyenne et de
multiplication peuvent être effectuées sans déchiffrer les
valeurs numériques applicables à l'interrogation. Chaque sous-
texte chiffré est stocké dans un seul enregistrement et dans
des attributs séparés. L'invention porte sur des procédés de
CA 03050353 2019-07-16
WO 2018/150119 5
PCT/FR2018/050276
chiffrement et de déchiffrement, de création d'une table
appropriée, d'interrogation d'une telle base de données et de
mise à jour d'une telle base de données.
On connaît en outre le documents US 2010/146299.
Inconvénients de l'art antérieur
Un des inconvénients du chiffrement homomorphe est
que la taille des clés et le coût (en temps de calcul) des
opérations sont largement plus importants que les traitements
de chiffrement classiques.
Les solutions de l'art antérieur présentent un
inconvénient majeur résultant de la puissance de calcul
nécessaire pour exécuter sur le serveur les traitements de
chiffrement homomorphe à chaque indexation d'un nouveau
document ainsi qu'à chaque nouvelle requête. Pour cette
raison, les solutions de l'art antérieur ne sont applicables
qu'à des corpus très restreints, par exemple un annuaire
d'entreprise ou un petit ensemble de documents textuels.
Par ailleurs, les solutions de l'art antérieur sont
limitées à la recherche de documents sur la base d'un critère
binaire de présence ou d'absence dans le document d'un terme
de la requête, sans permettre de proposer de manière efficace
un ordonnancement de la pertinence des documents correspondant
à la requête.Le procédé selon l'invention propose une solution
efficace à la recherche d'informations dans un corpus chiffré
de grande taille.
Solutions apportées par l'invention
Afin de répondre à ces inconvénients, l'invention
concerne un premier aspect d'un procédé de recherche
d'informations dans un corpus chiffré stocké sur un serveur, à
partir d'une requête numérique calculée sur un équipement
CA 03050353 2019-07-16
WO 2018/150119 6
PCT/FR2018/050276
client, contenant une séquence de termes, comportant les
étapes suivantes :
- Chiffrement de ladite requête sur un équipement
informatique client
- Transmission de ladite requête chiffrée à un serveur de
gestion de base de données
- Calcul homomorphe sur le serveur de la réponse chiffrée à
la requête chiffrée enregistrée sur le serveur
- Transmission de la réponse chiffrée à l'équipement client
- Déchiffrement sur l'équipement client de la réponse
chiffrée (50) et extraction des identifiants des documents
Caractérisé en ce qu'il comporte
a) des étapes de calcul sur l'équipement client,
lors de l'introduction d'un nouveau document requêtable
pour chaque document i appartenant au corpus, d'une première
table TFi et d'une deuxième table dfi
- ladite première table TFi comprenant, pour chaque
terme indexé w du document i, le nombre
d'occurrences du terme w dans le document i
- ladite deuxième table Adfi constituée par l'index
des mots w présents dans le document i
b) le chiffrement du document i et de ladite table
Adfi, ainsi que le chiffrement par un procédé de chiffrement
homomorphe de ladite table TF, et la transmission de ces trois
informations numériques chiffrées au serveur pour
l'enregistrement dans un espace de stockage dédié à un
utilisateur A ou un groupe {Au} d'utilisateurs
c) une étape de création ou de mise à jour d'un
index df A sur l'équipement client, associé à un utilisateur
A, pour l'ensemble des documents i accessibles par
l'utilisateur A ledit index df A étant constitué par une table
CA 03050353 2019-07-16
WO 2018/150119 7
PCT/FR2018/050276
indiquant pour chaque terme w le nombre de documents i
contenant ledit terme w
d) des étapes de requêtage consistant à :
¨ chiffrer sur l'équipement client une requête Q_x
constituée par une succession de termes, par un chiffrement
homomorphe appartement au même cryptosystème que le
chiffrement appliqué à TF
¨ transmettre la requête ainsi chiffrée au serveur
pour la réalisation de ladite étape de calcul homomorphe et de
transmission d'une réponse chiffrée au client et de
déchiffrement par l'équipement client
une étape additionnelle exécutée Sur
l'équipement client, d'agrégation desdits identifiants des
données contenues dans ladite réponse chiffrée et dans l'index
df A enregistré sur l'équipement client
¨ la présentation du résultat sous une forme
ordonnée des documents en application du traitement de l'étape
précédente.
Selon une variante, le procédé comporte une étape
de reconstitution sur l'équipement client de l'index df_A à
partir des informations {Adfi} chiffrées enregistrées pour
chaque document i dans l'espace dédié du serveur affecté à
l'utilisateur A.
Selon une variante, les calculs effectués sur le
serveur sont implémentés de manière parallèle et/ou
distribuée.
Selon une autre variante, le serveur (2) est
constitué par une plateforme nuagique (en anglais cloud ).
L'invention concerne aussi un procédé de
préparation d'une base requêtable à de document i contenant
une séquence de termes, caractérisé en ce qu'il comporte les
étapes suivantes :
CA 03050353 2019-07-16
WO 2018/150119 8
PCT/FR2018/050276
a) des étapes de calcul sur l'équipement client,
lors de l'introduction d'un nouveau document requêtable
pour chaque document i appartenant au corpus, d'une première
table TFi et d'une deuxième table Adfi
- ladite première table TFi comprenant, pour chaque
terme indexé w du document i, le nombre d'occurrences
du terme w dans le document i
- ladite deuxième table Adfi constituée par la présence
ou non de chaque terme w dans le document i
b) le chiffrement du document i et de ladite table
Adfi, ainsi que le chiffrement par un procédé de chiffrement
homomorphe de ladite table TF, et la transmission de ces trois
informations numériques chiffrés au serveur pour
l'enregistrement dans un espace de stockage dédié à un
utilisateur A ou un groupe {Au} d'utilisateurs
c) une étape de création ou de mise à jour d'un
index df A sur l'équipement client, associé à un utilisateur
A, pour l'ensemble des documents i accessibles par
l'utilisateur A ledit index df A étant constitué par une table
indiquant pour chaque terme w le nombre de documents i
contenant ledit terme w.
L'invention concerne aussi un procédé de recherche
d'informations dans un corpus chiffré stocké sur un serveur, à
partir d'une requête numérique calculée sur un équipement
client, contenant une séquence de termes, caractérisé en ce
qu'il comporte les étapes suivantes :
- Chiffrement de ladite requête sur un équipement
informatique client
- Transmission de ladite requête chiffrée à un serveur de
gestion de base de données
- Calcul homomorphe sur le serveur de la réponse chiffrée à
la requête chiffrée enregistrée sur le serveur
- Transmission de la réponse chiffrée à l'équipement client
CA 03050353 2019-07-16
WO 2018/150119 9
PCT/FR2018/050276
- Déchiffrement sur l'équipement client de la réponse
chiffrée et extraction des identifiants des documents
lesdites étapes de requêtage consistant à :
¨ chiffrer sur l'équipement client une requête Q_x
constituée par une succession de termes, par un chiffrement
homomorphe appartement au même cryptosystème que le
chiffrement appliqué à TF
¨ transmettre la requête ainsi chiffrée au serveur
pour la réalisation de ladite étape de calcul homomorphe et de
transmission d'une réponse chiffrée au client et de
déchiffrement par l'équipement client
et comporte une étape additionnelle exécutée sur
l'équipement client, d'agrégation desdits identifiants des
données contenues dans ladite réponse chiffrée et dans l'index
df _A enregistré sur l'équipement client
et une étape de présentation du résultat sous une
forme ordonnée des documents en application du traitement de
l'étape précédente.
Description détaillée d'un exemple non limitatif de
l'invention
La présente invention sera mieux comprise à la
lecture de la description qui suit, concernant un exemple non
limitatif de réalisation se référant aux dessins annexés où :
¨ la figure 1 représente une vue schématique d'un
système informatique selon l'invention
¨ la figure 2 représente une vue schématique des
flux de données entre les différentes ressources
informatiques.
Architecture matérielle
CA 03050353 2019-07-16
WO 2018/150119 10
PCT/FR2018/050276
La figure 1 représente une vue schématique de
l'architecture matérielle de l'invention.
Elle comprend un équipement informatique (1) client
relié à un serveur (2) par un réseau informatique, par exemple
Internet.
Le serveur (2) est associé à une mémoire (3) pour
l'enregistrement d'une base de données. Le serveur (2)
comporte un processeur pour réaliser des traitements
numériques.
Le serveur (2) et les mémoires (3) sont dans un
exemple particulier constitués par un ensemble de ressources
distribuées, par exemple de type cloud .
Architecture fonctionnelle
La figure 2 représente un exemple d'architecture
fonctionnelle.
L'équipement client (1) assure le traitement
initial d'un document i constitué par un fichier numérique (9)
enregistré dans une mémoire de travail.
Optionnellement, chaque terme du document fait
l'objet d'un prétraitement préalable par des moyens connus de
type radicalisation ( stemming en anglais),
liste
d'exclusions (suppression des mots courants ( stop list en
anglais) et tout autre traitement linguistique usuel).
Préparation des fichiers chiffrés requêtables.
Le traitement initial se décompose en trois tâches.
La première tâche consiste à appliquer un
chiffrement au document i avec un procédé cryptographique
connu, par exemple un chiffrement symétrique AES et enregistre
CA 03050353 2019-07-16
WO 2018/150119 11
PCT/FR2018/050276
une version chiffrée (10) de ce document sur l'équipement
client, et optionnellement sur le serveur (2) ou un service de
stockage tiers. Le corpus de documents chiffrés ainsi défini
constitue la base de documents (32).
Une seconde tâche, exécutée parallèlement ou
séquentiellement, consiste à calculer un index des occurrences
des termes présents dans le fichier (9), et à enregistrer une
table TFi (14) des occurrences, sous la forme d'une liste des
termes wi présents dans le document i, chacun des termes wi de
cette liste étant associé à un nombre correspondant à
l'occurrence tf du terme wi dans le document i.
La table TFi (14) est donc de type {[wi ;
pour un document i.
Une troisième tâche, exécutée parallèlement ou
séquentiellement, consiste à calculer une table Adfi (15)
correspondant, pour chaque terme wi, la présence ou non du
terme dans le document. Cette table Adfi (15) est donc de type
{[wi
On procède ensuite au chiffrement de la table TFi
(14) par un procédé de chiffrement homomorphe, par exemple
selon un procédé décrit dans l'article Zhou, H., & Wornell, G.
(2014, February). Efficient homomorphic encryption on integer
vectors and its applications. In Information Theory and
Applications Workshop (ITA), 2014 (pp. 1-9). IEEE.
Le résultat de ce chiffrement de la table TFi (14)
est un ensemble de données chiffrées (11). Chaque ensemble de
données chiffrées (11) est transmis par l'équipement client
(1) au serveur (2).
Le regroupement des ensembles de données chiffrées
(11) constitue une base chiffrée (30) de tous les {TF}.
Parallèlement ou séquentiellement, on procède à un
chiffrement de la table Adfi (15) selon un procédé connu, par
CA 03050353 2019-07-16
WO 2018/150119 12
PCT/FR2018/050276
exemple AES et la transmission au serveur (2) pour enregistrer
une version chiffrée (12) sur le serveur (2).
L'ensemble des fichiers chiffrés (12) enregistré
sur le serveur constitue une base (31).
Chaque fichier chiffré (12) enregistré sur le
serveur (2) permet de reconstituer une table df_A (13) par
déchiffrement par un algorithme inverse à celui utilisé pour
le chiffrement de précité.
Cette table df_A (13) est calculée uniquement sur
l'équipement client (1), à partir :
¨ Soit de l'ensemble des tables chiffrées (31)
enregistrées sur le serveur (2), après leur transmission sur
l'équipement client (1)
¨ soit directement par mise à jour d'une table df_A
(13) enregistrée localement sur l'équipement client (1), la
mise à jour étant réalisée à chaque ajout d'une table Adfi
(15).
Cette étape de préparation des données conduit à
l'enregistrement sur le serveur de données qui ne sont pas
directement requêtables et qui ne dévoilent pas d'informations
signifiantes sur le contenu ni les documents, notamment en cas
d'attaque du serveur ou d'action malveillante d'un utilisateur
à privilège.
Requêtage
Le requêtage est réalisé par l'émission d'une
requête textuelle formée par une combinaison de mots (20) à
partir de l'équipement client (1).
Optionnellement, cette requête (20) est prétraitée
par des moyens connus de type radicalisation ( stemming en
anglais, liste d'exclusions (suppression des mots courants
CA 03050353 2019-07-16
WO 2018/150119 13
PCT/FR2018/050276
( stop list en anglais) et tout autre traitement
linguistique usuel.
La requête (20) est chiffrée avec le même procédé
de chiffrement homomorphe que celui utilisé pour le
chiffrement de la table TFi (14) pour obtenir une requête
chiffrée (21).
La requête chiffrée (21) est transmise au serveur
(2) qui enregistre pour constituer une requête (40).
Par application d'un calcul sur les données
chiffrées de manière homomorphe (30) et de la requête (40), le
serveur (2) calcule une réponse chiffrée (41).
Ce traitement consiste à calculer, dans le domaine
chiffré, le nombre d'occurrences de chaque terme qk de la
requête (40) pour chaque document i connu.
On dénombre pour chacun des k termes qk et pour
chaque document i, les valeurs tf pour les cas où qk
correspond à un terme wi, à partir des tables chiffrées {[wi ;
tfi,j]}i (30) et dans l'espace chiffré, sans déchiffrement des
variables wi, qk et
L'ensemble de ces dénombrements constitue une
réponse (41) qui est transmise à l'équipement client (1) qui
l'enregistre localement sous forme de réponse (50).
Le client (1) est en mesure ensuite de procéder au
déchiffrement de la réponse (50) pour calculer une réponse
déchiffrée (51).
Finalement, le client (1) peut combiner la réponse
(51) et la table df A (13) pour calculer un score TF-IDF (52)
(anglais Term Frequency-Inverse Document Frequency) selon un
procédé connu.
Ce score (52) constitue une clé de classement des
documents i par ordre de pertinence vis-à-vis de la requête
(20).
CA 03050353 2019-07-16
WO 2018/150119 14 PCT/FR2018/050276
Optionnellement, l'équipement client (1) présente
les résultats à la manière d'un moteur de recherche et permet
à l'utilisateur de retrouver l'enregistrement correspondant.
