Brevet FR3059445A1 — publié le 20180601

Procédé de chiffrement cherchable L'invention se rapporte au domaine des télécommunications. Elle concerne plus particulièrement un système de chiffrement dit « cherchable », c' est- à-dire un système permettant de détecter la présence d'un certain mot dans un chiffré. Le recours de plus en plus systématique au chiffrement de données pose de réels problèmes dans un monde numérique où le traitement de données est souvent confié à une entité tierce à laquelle on ne souhaite pas accorder un accès en clair aux données. Ce peut être le cas par exemple d'un système de stockage décentralisé de type cloud computing auquel une entreprise peut faire appel pour stocker l'intégralité de ses archives de manière chiffrée. Il se peut alors qu'un utilisateur dans l'entreprise souhaite récupérer, parmi ces données archivées, une donnée en particulier. Le gestionnaire du cloud peut se retrouver incapable de détecter la donnée de l'utilisateur parmi l'ensemble des archives chiffrées et peut donc se retrouver obligé de retourner l'intégralité des archives chiffrées à l'entreprise. Des solutions cryptographiques existent afin d'identifier une donnée particulière dans un ensemble de données chiffrées et éviter ainsi de rapatrier l'intégralité des archives chiffrées. La solution cryptographique mise en avant dans ce cas est appelée « chiffrement cherchable » (ou « searchable encryption » en anglais). Le chiffrement cherchable permet de détecter si un élément est un chiffré d'un mot-clé, noté W, à condition de détenir une certaine information, appelée habituellement « trappe » et associée préalablement au mot-clé W. Dans ce cas, la donnée qui comprend le mot-clé est chiffrée de manière classique et un chiffrement cherchable est appliqué au mot-clé. Ainsi, dans l'exemple du stockage dans un cloud, l'utilisateur qui souhaite envoyer pour archivage une donnée dans le cloud de manière sécurisée définit un mot-clé qu'il associe à cette donnée. Il chiffre alors classiquement sa donnée et applique un chiffrement cherchable au mot-clé associé puis transmet ces éléments chiffrés au cloud pour archivage. Il peut ensuite demander le rapatriement de la donnée chiffrée archivée, en précisant le mot-clé qu'il lui avait associé. Il est également possible d'appliquer cette technique de recherche d'informations dans du trafic chiffré. Par exemple, dans le cas d'un système de détection d'intrusions, il est habituel de chercher un virus (ou « malware » en anglais) dans un flux de données en détectant la présence d'une certaine chaîne de caractères, communément appelée « signature », qui constitue alors un mot-clé à rechercher. Cependant, lorsqu'il s'agit d'un flux de données, la notion de mot-clé est difficile à définir. En effet, un flux de données, par exemple un flux Internet, n'a pas réellement de structure : il peut contenir des URL (de l'anglais « Uniform Resource Locator »), du code binaire, etc., dont il est difficile d'extraire des mots-clés. Par ailleurs, s'agissant d'un 3059445 2 flux chiffré émis dans un réseau entre deux entités : un émetteur et un récepteur, il est difficile d'appliquer le chiffrement cherchable directement. En effet, l'émetteur en charge de la définition des mots-clés n'a pas connaissance a priori des informations que recherche le récepteur. Ainsi, la définition de mots-clés dans un flux peut s'avérer problématique. 5 Une solution récemment proposée utilise des algorithmes de chiffrement cherchable pour traiter des flux de données. Cette solution, appelée « BlindBox », consiste à découper la donnée, traitée comme une chaîne de caractères, en sous-chaînes d'une certaine longueur / et à faire de ces dernières les mots-clés de la donnée. Par exemple, si / = 3 et que l'on considère des chaînes d'octets, la donnée « exemple » est découpée en les sous-chaînes suivantes : « exe », 10 « xem », « emp » et « ple ». Chacune de ces sous-chaînes est alors considérée comme un mot- clé et est chiffrée en utilisant un algorithme de chiffrement cherchable. Cependant, cette solution ne permet de chercher que des mots de taille 1. Les mots-clés à chercher, par exemple les signatures dans le cas de malware, ont rarement la même taille. Il est alors nécessaire d'ajuster la solution. 15 Une première solution est de reproduire le découpage et le chiffrement pour chaque taille de mot-clé possible. Cette solution pose des problèmes évidents d'efficacité : elle accroît la complexité du chiffrement et le volume du trafic. Une deuxième solution consiste à découper si nécessaire les mots-clés à chercher pour les forcer à être de même taille. Si par exemple, il est question d'émettre une trappe pour le mot 20 « execute » et que la longueur des trappes est limitée à trois, alors on associe au mot « execute » les trappes « exe », « cut » et « ute ». L'entité qui génère ces trappes souhaitait que soit identifiée la présence de « execute » dans le flux chiffré, mais avec cette découpe, tous les exécutables, d'extension « exe » sont détectés. Ici, le nombre de mots-clés est multiplié et l'information révélée peut être plus importante que nécessaire. Par ailleurs, au vu du nombre de 25 mots-clés à chercher, un risque est que l'entité qui effectue la recherche dispose d'une trappe pour presque tous les mots de longueurs trois et qu'elle soit ainsi capable, en utilisant chacune de ces trappes, de déduire l'intégralité de la donnée en clair. Cette solution nuit donc à la sécurité. Ces exemples illustrent la complexité du choix de mots-clés pour la mise en oeuvre du 30 chiffrement cherchable dans le cas d'un flux de données et pour les procédés qui l'utilisent. Un des buts de l'invention est de remédier à des insuffisances/inconvénients de l'état de la technique et/ou d'y apporter des améliorations. A cette fin, l'invention propose un procédé de génération de trappes dans un système de 35 chiffrement cherchable, ledit système définissant une clé secrète et une clé publique, une trappe 3059445 3 V étant associée à un mot-clé W comprenant 1 données élémentaires w1 ladite trappe étant générée par : - génération de 1 aléas yl, y2, ..., vi, - génération d'un polynôme V en un élément z, fonction de la clé secrète, et de degré 1, 5 un j-ième coefficient dudit polynôme, 1 REVENDICATIONS1. Procédé de génération de trappes dans un système de chiffrement cherchable, ledit système définissant une clé secrète et une clé publique, une trappe (V) étant associée à un mot- clé (W) comprenant 1 données élémentaires (w1 ...14,1), ladite trappe étant générée par : - génération (E301) de 1 aléas (y1, y2, ..., vi), - génération (E302) d'un polynôme (V) en un élément z, fonction de la clé secrète, et de degré 1, un j-ième coefficient dudit polynôme, 1 2. Procédé de chiffrement cherchable d'un système définissant une clé secrète et une clé publique, un chiffré (C) d'un flux de données (B) qui comprend n données élémentaires (b1, b2, , tin) comprenant : - génération (E23) d'un aléa (a), - pour toute donnée élémentaire b1, j = 1 à n, génération (E24) d'un élément fonction de la clé publiqueg( X (b i).Z l) et de l'aléa, ledit élément étant associé à un élément aléatoire d'un groupe (g) d'un environnement bilinéaire, ledit élément associé à l'élément aléatoire du groupe formant une première donnée de chiffrement (C1,1), et génération d'un facteur de décalage ffl -i - f ) fonction de l'aléa et de la clé publique, et associé à l'élément aléatoire du groupe, ledit facteur de décalage étant représentatif d'une position dudit monôme dans le flux chiffré (C), ledit facteur de décalage associé à l'élément aléatoire du groupe formant une deuxième donnée de chiffrement (C1,2), ledit chiffré (C) du flux de données comprenant pour tout j = 1 à n, les première et deuxième données de chiffrement. 3. Procédé de détection d'un mot-clé (W) dans un chiffré (C) d'un flux de données (B) dans un système de chiffrement cherchable, ledit système définissant une clé secrète et une clé publique, ledit mot-clé comprenant 1 données élémentaires (w1 w1), le procédé comprenant : - obtention (E40) d'une trappe (T) associée au mot-clé, ladite trappe comprenant 1 aléas (hvi) associés à un élément aléatoire (h) d'un groupe d'un environnement bilinéaire, et un polynôme (V) en un élément z, fonction de la clé secrète et de degré 1, ledit polynôme étant associé à l'élément aléatoire du groupe (hv), un i-ième coefficient dudit polynôme, 1 4. Procédé de déchiffrement d'un chiffré (C) d'un flux de données (B), ledit flux de données comprenant n données élémentaires (b1, b2, bn), le chiffré étant généré conformément au procédé de chiffrement cherchable selon la revendication 2, le procédé de déchiffrement comprenant : 20 - obtention (E50) d'une trappe associée à chacune des données élémentaires distinctes du flux de données, ladite trappe étant générée conformément au procédé de génération de trappes selon la revendication 1, - détection (E52) de la présence de ladite trappe, conformément au procédé de détection de trappes selon la revendication 3. 25 5. Dispositif de génération de trappes (60) dans un système de chiffrement cherchable, ledit système définissant une clé secrète et une clé publique, une trappe (V) étant associée à un mot-clé (W) comprenant 1 données élémentaires (w1 w1), ladite entité comprenant : - des premiers moyens de génération (604), agencés pour générer 1 aléas (y1, y2, ..., vi), 30 - des deuxièmes moyens de génération (605), agencés pour générer un polynôme (V) en un élément z, fonction de la clé secrète, et de degré 1, un j-ième coefficient dudit polynôme, 1 6. Programme pour une entité de génération de trappes dans un système de chiffrement cherchable, comprenant des instructions de code de programme destinées à commander l'exécution des étapes du procédé de génération de trappes selon la revendication 1, lorsque le 5 programme est exécuté sur ladite entité. 7. Dispositif de chiffrement cherchable (70) d'un système définissant une clé secrète et une clé publique, un chiffré (C) d'un flux de données (B) qui comprend n données élémentaires (b1, b2, bn), ladite entité comprenant : 10 - des premiers moyens de génération (704), agencés pour générer un aléa (a), - des deuxièmes moyens de génération (705), agencés pour générer, pour toute donnée ).z bj ( x élémentaire hi, j = 1 à n, un élément fonction de la clé publique (g j) et de l'aléa, ledit élément étant associé à un élément aléatoire d'un groupe (g) d'un environnement bilinéaire, ledit élément associé à l'élément aléatoire du groupe formant une première donnée de 15 chiffrement (C1,1), et génération d'un facteur de décalage (g azi-1, ) fonction de l'aléa et de la clé publique, et associé à l'élément aléatoire du groupe, ledit facteur de décalage étant représentatif d'une position dudit monôme dans le flux chiffré (C), ledit facteur de décalage associé à l'élément aléatoire du groupe formant une deuxième donnée de chiffrement (C1,2), ledit chiffré (C) du flux de données comprenant pour tout j = 1 à n, les première et deuxième 20 données de chiffrement. 8. Programme pour une entité de chiffrement cherchable, comprenant des instructions de code de programme destinées à commander l'exécution des étapes du procédé de chiffrement cherchable selon la revendication 2, lorsque le programme est exécuté sur ladite entité. 25 9. Dispositif (80) de détection d'un mot-clé (W) dans un chiffré (C) d'un flux de données (B) dans un système de chiffrement cherchable, ledit système définissant une clé secrète et une clé publique, ledit mot-clé comprenant l données élémentaires (w1 ...14,1), ladite entité comprenant : 30 - des moyens (804) d'obtention, agencés pour obtenir une trappe (T) associée au mot- clé, ladite trappe comprenant l aléas (hvi) associés à un élément aléatoire (h) d'un groupe d'un environnement bilinéaire, et un polynôme (V) en un élément z, fonction de la clé secrète et de degré 1, ledit polynôme étant associé à l'élément aléatoire du groupe (hv), un i-ième coefficient 3059445 23 dudit polynôme, 1 10 - des moyens (806) de couplage, agencés pour, pour tout i = 1 à 1, calculer un couplage du facteur de décalage associé à la position courante et du polynôme (V) associé à la trappe, ledit couplage produisant un deuxième polynôme (U) de degré 1, - des moyens (807) de comparaison, agencés pour comparer les premier et deuxième polynômes, une égalité des deux polynômes étant représentative de la présence du mot-clé W 15 dans le flux à partir de la position courante j. 10. Programme pour une entité de détection de la présence d'un mot-clé dans un chiffré, comprenant des instructions de code de programme destinées à commander l'exécution des étapes du procédé de détection de la présence d'un mot-clé dans un chiffré selon la 20 revendication 3, lorsque le programme est exécuté sur ladite entité. 11. Système de chiffrement cherchable comprenant : - un dispositif (60) de génération de trappes selon la revendication 5, - un dispositif (70) de chiffrement cherchable selon la revendication7, et 25 - un dispositif (80) de détection de la présence d'un mot-clé dans un chiffré selon la revendication 9.