Brevet FR3040842A1 — publié le 20170310

MÉTHODE D'INTERROGATION CONFIDENTIELLE D'UN SERVICE GÉODÉPENDANT PAR CRYPTOGRAPHIE HOMOMORPHE DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne notamment le domaine des services géodépendants ou services LBS (Location Based Services). Une application importante de l'invention concerne le domaine de la navigation par itinéraires masqués. ÉTAT DE LA TECHNIQUE ANTÉRIEURE Les services géodépendants (LBS) ont connu un développement spectaculaire ces dernières années avec la banalisation des terminaux mobiles intelligents de troisième et quatrième génération. Parmi les services LBS on peut citer la recherche de points d'intérêt ou POI (Point Of interest), la localisation d'un utilisateur, ou encore la recherche d'itinéraires. Les services LBS ont pour point commun de fournir une information fonction de la position de l'utilisateur. La position d'un utilisateur étant une information sensible, les services en question doivent pouvoir garantir confidentialité et respect de la vie privée (privacy) de l'utilisateur. Cette exigence est d'autant plus nécessaire que le service LBS peut être offert de manière délocalisée au moyen d'une plateforme de cloud computing. Différents schémas ont été proposés pour assurer la confidentialité des données de localisation des utilisateurs : recours à un tiers de confiance ou TTP (Trusted Third Party), schéma semi-distribué faisant appel à au moins deux entités indépendantes, architecture client-serveur, schéma collaboratif à confidentialité distribuée au sein d'un réseau ad hoc. L'architecture client-serveur présente l'avantage de ne pas recourir à un tiers de confiance. Cependant, la préservation de la confidentialité requiert alors que le serveur, considéré a priori comme non fiable, puisse fournir l'information demandée par 3040842 2 l'utilisateur sans que la position de ce dernier ne lui soit révélée. Une telle méthode d'interrogation confidentielle, autrement dit sans possibilité pour le fournisseur du service d'avoir accès à l'argument en clair de la requête de l'utilisateur, en l'occurrence ici sa position, est appelée méthode PIR (Private Information Retrieval). 5 La Fig. 1 illustre le principe d'une méthode PIR dans une architecture client- serveur. Le serveur d'un fournisseur de service LBS, 110, dispose d'une base de données, 130 qui contient N enregistrements, soit 0[1,...,N], chaque enregistrement étant 10 constitué par un élément d'information. Un utilisateur (ou client) 120 envoie une requête Q(i) où i est un index paramétrant la position de l'utilisateur, celui-ci souhaitant en fait obtenir l'élément d'information 0, de la base de données. La requête Q(i) est chiffrée de sorte qu'il est impossible pour le serveur de retrouver la valeur d'index i. Le serveur 110 calcule à partir 15 du tableau O et de la requête Q(i) un résultat R(O,Q(i)) au moyen d'une transformation mathématique et ce résultat est renvoyé à l'utilisateur. Celui-ci déchiffre le résultat R(O,Q(i)) pour obtenir l'élément 0, . On trouvera un exemple de méthode PIR dans l'article de G. Ghinita et al. intitulé « Private queries in Location Based Services : anonymizers are not necessary » publié dans 20 Proc. of Sigmod 2008, pp. 121-132. Cette méthode PIR assure la confidentialité de la position de l'utilisateur grâce à l'intractabilité du problème de résiduosité quadratique selon lequel il est extrêmement difficile de déterminer si un entier est un résidu quadratique modulo n , où n = qiq2 est un entier avec qpq2 grands nombres premiers, sans connaître q1 et q2. La méthode PIR décrite dans cet article utilise un tableau dans 25 lequel chaque cellule correspond à une position et contient la liste des POI les plus proches de cette position. Elle permet ainsi à un utilisateur d'obtenir les POI les plus proches de lui. Bien que cette méthode PIR permette d'obtenir un degré élevé de confidentialité, elle est relativement complexe et nécessite d'effectuer un grand nombre de calculs. Le but de la présente invention est par conséquent de proposer une méthode 3040842 3 d'interrogation confidentielle d'un fournisseur de service, en particulier d'un fournisseur de service géodépendant, qui soit plus simple que celle de l'art antérieur tout en garantissant un degré élevé de confidentialité. Un but subsidiaire de la présente invention est de pouvoir offrir à un utilisateur un service de navigation à itinéraires masqués. 5 EXPOSÉ DE L'INVENTION La présente invention est définie par une méthode d'interrogation confidentielle d'un serveur par un utilisateur, ledit serveur étant équipé d'une base de données représentée par un vecteur d'enregistrements, dans laquelle : 10 - l'utilisateur construit un vecteur V; dont tous les éléments sauf celui d'un indice i sont des chiffrés de zéro et dont l'élément d'indice i est un chiffré de un, le chiffrement étant effectué au moyen d'un cryptosystème probabiliste vérifiant les propriétés homomorphiques suivantes : 15 Dec sk[Enc pk (a, r) CD Enc pk (b,r)1= a +b Dec sk[a 0 Enc pk (b, r)1= a.b où (sk,pk) est une paire de clés privée et publique de l'utilisateur, Encpk est une opération de chiffrement au moyen de la clé publique, Dec sk une opération de 2 0 déchiffrement à l'aide de la clé privée, a,b sont des clairs, est un opérateur sur l'espace des chiffrés et 0 est un opérateur entre l'espace des clairs et l'espace des chiffrés ; - l'utilisateur transmet au serveur une requête ayant pour argument le vecteur y ; - le serveur effectue un produit scalaire entre le vecteur des enregistrements O et le vecteur V; et renvoie (250, 350) le produit scalaire Ci ainsi obtenu à l'utilisateur ; 25 - l'utilisateur déchiffre le produit scalaire Ci pour obtenir l'enregistrement d'indice i de la base de données. 3040842 4 Le cryptosystème peut être choisi par exemple parmi le cryptosystème de Pallier, le cryptosystème de Regev et le cryptosystème de Fau-Vercauteren. Selon un mode de réalisation avantageux, les enregistrements sont constitués par les valeurs prises par une fonction F connue du serveur sur un ensemble de positions 5 possibles de l'utilisateur dans une zone géographique donnée. L'invention concerne également une méthode de navigation confidentielle au sein d'une zone géographique donnée, mettant en oeuvre la méthode d'interrogation confidentielle définie ci-dessus et dans laquelle : - ladite zone géographique contient une pluralité de points de référence, chaque 10 couple de points de référence étant associé à un indice ; - ladite base de données contient pour chaque indice correspondant à un couple de points de référence, un enregistrement d'un chemin optimal au sens d'un critère prédéterminé entre ces points, le chemin optimal étant défini par une liste d'indices de points de référence (k1,....,kQ ) par lequel passe ce chemin ; 15 - l'utilisateur détermine les indices respectifs (iA,iB) d'un couple de points de départ, A, et de destination, B, et en déduit l'indice i correspondant du couple de points ( A,B); - l'enregistrement d'indice i obtenu par déchiffrement du produit scalaire, C,, fournit à l'utilisateur l'itinéraire entre les points A et B. 20 Dans une utilisation dynamique, le serveur met à jour périodiquement ou sur requête les chemins optimaux entre les points de référence de la zone géographique. Avantageusement, le serveur stocke une pluralité de vecteurs V; relatifs à une pluralité M de couples de points favoris de départ et de destination. Dans ce cas, l'utilisateur transmet au serveur une sous-requête spécifiant parmi la 25 pluralité de couples de points favoris, le couple pour lequel il souhaite obtenir un itinéraire et que le serveur retourne le produit scalaire entre le vecteur des enregistrements O et le vecteur V; correspondant à cette sous-requête. Alternativement, le serveur effectue périodiquement un calcul de produit scalaire entre les vecteurs V; relatifs aux couples de points favoris et le vecteur des 3040842 5 enregistrements O, le serveur construisant un vecteur C des produits scalaires ainsi obtenus. Dans ce cas, l'utilisateur construit un second vecteur Ui de taille M dont tous les éléments sauf celui d'un indice j sont des chiffrés de zéro et dont l'élément d'indice j 5 est un chiffré de un, le chiffrement étant réalisé au moyen dudit cryptosystème, l'utilisateur transmet au serveur une sous-requête ayant pour argument le second vecteur 'Ji . Le serveur effectue avantageusement un second produit scalaire entre le vecteur C et le vecteur U et renvoie à l'utilisateur le second produit scalaire ainsi obtenu. L'utilisateur déchiffre alors le second produit scalaire pour obtenir le produit 10 scalaire C,, puis déchiffre le premier produit scalaire pour obtenir l'itinéraire pour le couple de points souhaités. BRÈVE DESCRIPTION DES DESSINS 15 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 en référence aux figures jointes parmi lesquelles : La Fig. 1 représente le principe d'une méthode PIR connue de l'état de la technique; La Fig. 2 représente un ordinogramme de la méthode PIR selon un mode de 20 réalisation de l'invention; La Fig. 3 représente un ordinogramme d'une navigation à itinéraires masqués utilisant la méthode PIR de la Fig. 2. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS 25 La méthode d'interrogation confidentielle selon la présente invention sera décrite ci-après dans le contexte d'une architecture client-serveur comme précédemment décrite en relation avec la Fig. 1. Dans un mode de réalisation particulier de l'invention le serveur fournira un service géodépendant (LBS), notamment, la recherche de points d'intérêt (P01) 3040842 6 ou un service de navigation à itinéraires masqués comme décrit en détail plus loin. Cependant, dans sa forme la plus générale, l'invention pourra trouver application dans d'autres types de services, par exemple un service de consultation de dossier médical. Quel que soit le type de service envisagé, le serveur est équipé d'une base de 5 données contenant une pluralité d'enregistrements indexés par un index i. Ainsi la base de données peut être considérée comme un vecteurO = (01,...0,v)T, chaque élément du vecteur correspondant à un enregistrement. Sans perte de généralité, on supposera dans la suite que les enregistrements sont représentés par des éléments de Zn, = Z/n2Z où n= pq est un entier, produit de deux (grands) nombres premiers p et q . 10 L'idée à la base de l'invention est d'utiliser un cryptosystème probabiliste ayant des propriétés homomorphiques particulières permettant d'extraire un enregistrement à l'aide d'un simple produit scalaire. On rappelle tout d'abord qu'un chiffrement probabiliste Enc(.,r) est un chiffrement dépendant d'un paramètre aléatoire r. Le chiffrement d'un message clair m 15 peut ainsi donner différents messages chiffrés Enc(m,r) suivant la valeur prise par le paramètre r . Toutefois, quelle que soit la valeur prise par ce paramètre, le déchiffrement de Enc(m,r) redonne toujours le message clair m. Autrement dit, il existe une fonction de déchiffrement Dec telle que : 20 Dec (Enc(m,r))= m (1) On rappelle ensuite qu'un chiffrement homomorphe est un chiffrement asymétrique Encpk (de clé publique pk) vérifiant la propriété suivante: 25 Encpk : X Y V a,b e X, Encpk (a+b)=Enc pk(a)e Eitc'k (b) (2) où X est l'espace des messages clairs (dit plus simplement espace des clairs) et Y est 3040842 7 l'espace des messages chiffrés (dit plus simplement espace des chiffrés), + une opération additive dans l'espace des clairs conférant à X une structure de groupe, 0 une opération dans l'espace des chiffrés conférant à Y une structure de groupe. On comprend ainsi que l'application Encpk de (X,+) dans (Y/) est un homomorphisme de groupes. Si l'on 5 note Dec sk la fonction de déchiffrement correspondant à Encpk (où sk est la clé secrète de l'utilisateur), la propriété (1) peut s'exprimer alternativement par : Dec sk[Enc pk (a) CD Encpk (01= a +b (3) 10 Autrement dit, il est possible d'effectuer une opération additive entre deux clairs à partir d'une opération correspondante entre leurs chiffrés. On supposera dans la suite que X =Zn = Z/ nZ et que Y =Zn, = Z/n2Z . Il résulte de ce qui précède qu'une méthode de chiffrement probabiliste homomorphe Encpk (.,r) vérifie la relation suivante : 15 Dec sk[Enc pk (a , r)CD Enc pk (b, r)1= a +b (4) où l'on a convenu comme précédemment que r est un paramètre aléatoire, pk est la clé publique de chiffrement et sk la clé secrète de déchiffrement. Les messages a et b sont 20 des messages en clair. En sus de la propriété d'homomorphisme additif exprimée en (4), on suppose que la méthode de chiffrement vérifie la propriété suivante : Dec sk[a 0 Enc pk (b,r)1= a.b (5) 25 où 0 est une opération externe de X xY Y et où . est une opération multiplicative dans Y . En d'autres termes, il est possible d'effectuer une opération multiplicative entre deux clairs à partir du chiffré de l'un d'eux. Il est à noter que la relation (5) n'est pas à 3040842 8 proprement parler une propriété d'homomorphisme dans la mesure où l'ensemble de départ est le produit cartésien X xY . Il n'est donc pas nécessaire que le cryptosystème soit de type FHE (Fully Homomophic Encryption). 5 On connait des cryptosystèmes probabilistes vérifiant les conditions (4) et (5), notamment le cryptosystème de Pallier, dans lequel le chiffrement d'un message 0 m REVENDICATIONS1. Méthode d'interrogation confidentielle d'un serveur par un utilisateur, ledit serveur étant équipé d'une base de données représentée par un vecteur d'enregistrements, caractérisée en ce que : - l'utilisateur construit (220, 320) un vecteur y dont tous les éléments sauf celui d'un indice i sont des chiffrés de zéro et dont l'élément d'indice i est un chiffré de un, le chiffrement étant effectué au moyen d'un cryptosystème probabiliste vérifiant les propriétés homomorphiques suivantes : Dec e[Enc pk (a, r) CD Enc pk (b,r)1= a +b Dec sk[a Enc pk (b,r)1= a.b où (sk, pk) est une paire de clés privée et publique de l'utilisateur, Encpk est une opération de chiffrement au moyen de la clé publique, Dec sk une opération de déchiffrement à l'aide de la clé privée, a,b sont des clairs, e est un opérateur sur l'espace des chiffrés et 0 est un opérateur entre l'espace des clairs et l'espace des chiffrés ; - l'utilisateur transmet (230, 330)) au serveur une requête ayant pour argument le vecteur V;; - le serveur effectue (240, 340) un produit scalaire entre le vecteur des enregistrements O et le vecteur V; et renvoie (250, 350) le produit scalaire Ci ainsi obtenu à l'utilisateur ; - l'utilisateur déchiffre (260, 360) le produit scalaire Ci pour obtenir l'enregistrement d'indice i de la base de données. 2. Méthode d'interrogation confidentielle selon la revendication 1, caractérisée en ce que le cryptosystème est un cryptosystème choisi parmi le cryptosystème de Pallier, le cryptosystème de Regev et le cryptosystème de Fau-Vercauteren. 3040842 16 3. Méthode d'interrogation confidentielle selon la revendication 1 ou 2, caractérisée en ce que les enregistrements sont constitués par les valeurs prises par une fonction F connue du serveur sur un ensemble de positions possibles de l'utilisateur 5 A =1,...,N1 dans une zone géographique donnée. 4. Méthode de navigation confidentielle au sein d'une zone géographique donnée, mettant en oeuvre la méthode d'interrogation confidentielle selon la revendication 1 ou 2, caractérisée en ce que : 10 - ladite zone géographique contient une pluralité de points de référence, chaque couple de points de référence étant associé à un indice ; - ladite base de données contient pour chaque indice correspondant à un couple de points de référence, un enregistrement d'un chemin optimal au sens d'un critère prédéterminé entre ces points, le chemin optimal étant défini par une liste d'indices de 15 points de référence (k1,....,kQ ) par lequel passe ce chemin ; - l'utilisateur détermine (310) les indices respectifs (iA,iB) d'un couple de points de départ, A, et de destination, B, et en déduit l'indice i correspondant du couple de points (A ,B); - l'enregistrement d'indice i obtenu par déchiffrement du produit scalaire, C,, 20 fournit à l'utilisateur l'itinéraire entre les points A et B. 5. Méthode de navigation confidentielle selon la revendication 4, caractérisée en ce que le serveur met à jour périodiquement ou sur requête les chemins optimaux entre les points de référence de la zone géographique. 25 6. Méthode de navigation confidentielle selon la revendication 4 ou 5, caractérisée en ce que le serveur stocke une pluralité de vecteurs y relatifs à une pluralité M de couples de points favoris de départ et de destination. 3040842 17 7. Méthode de navigation confidentielle selon la revendication 6, caractérisée en ce que l'utilisateur transmet au serveur une sous-requête spécifiant parmi la pluralité de couples de points favoris, le couple pour lequel il souhaite obtenir un itinéraire et que le serveur retourne le produit scalaire entre le vecteur des enregistrements O et le 5 vecteur V; correspondant à cette sous-requête. 8. Méthode de navigation confidentielle selon la revendication 6, caractérisée en ce que le serveur effectue périodiquement un calcul de produit scalaire entre les vecteurs V; relatifs aux couples de points favoris et le vecteur des enregistrements O, le 10 serveur construisant un vecteur C des produits scalaires ainsi obtenus. 9. Méthode de navigation confidentielle selon la revendication 8, caractérisée en ce que l'utilisateur construit un second vecteur Ui de taille M dont tous les éléments sauf celui d'un indice j sont des chiffrés de zéro et dont l'élément d'indice j est un chiffré 15 de un, le chiffrement étant réalisé au moyen dudit cryptosystème, l'utilisateur transmet au serveur une sous-requête ayant pour argument le second vecteur Ui . 10. Méthode de navigation confidentielle selon la revendication 9, caractérisée en ce que le serveur effectue un second produit scalaire entre le vecteur C et le vecteur Ui 20 et renvoie à l'utilisateur le second produit scalaire ainsi obtenu. 11. Méthode de navigation confidentielle selon la revendication 10, caractérisée en ce que l'utilisateur déchiffre le second produit scalaire pour obtenir le produit scalaire C,, puis déchiffre le premier produit scalaire pour obtenir l'itinéraire pour le couple 25 de points souhaités.