Chiffrement symétrique cherchable

Fonctionnement d'une recherche de mot-clé dans un schéma de chiffrement symétrique cherchable

Le chiffrement symétrique cherchable (ou Modèle:Lang en anglais) est une forme de chiffrement qui permet d'effectuer des recherches efficacement dans une collection de documents chiffrés sans avoir la possibilité de les déchiffrerModèle:SfnModèle:,Modèle:Sfn. Cette primitive cryptographique peut être utilisée pour stocker des fichiers sur un serveur cloud sans jamais révéler les fichiers en clair, mais tout en préservant la capacité du serveur à effectuer des recherches.

Description

Un schéma de chiffrement symétrique cherchable est un schéma de chiffrement à clé symétrique chiffrant une collection de documents $𝐃=({\mathrm{D}}_{\mathrm{1}},\dots ,{\mathrm{D}}_{\mathrm{n}})$, avec chaque document ${\mathrm{D}}_{\mathrm{i}}\subseteq 𝕎$ considéré comme un ensemble de mots-clés issus de l'espace de mots-clés $𝕎$ . Étant donné la clé de chiffrement $K$ et un mot-clé $w\in 𝕎$, on peut générer un jeton de recherche $tk$ avec lequel on peut rechercher $w$ dans la collection de documents chiffrées. Le résultat de la recherche est le sous-ensemble de documents chiffrés contenant le mot-clé $w$.

Schéma statique,

Un schéma statique se compose de trois algorithmes $𝖲𝖲𝖤\mathsf{=}\mathsf{(}𝖲𝖾𝗍𝗎𝗉,𝖳𝗈𝗄𝖾𝗇,𝖲𝖾𝖺𝗋𝖼𝗁\mathsf{)}$Modèle:SfnModèle:,Modèle:Sfn.

Présentation des algorithmes

$𝖲𝖾𝗍𝗎𝗉$ prend en entrée un paramètre de sécurité $k$ et une collection de documents $𝐃$ et retourne une clé symétrique $K$, une collection de documents chiffrés $𝐄𝐃$ et un index chiffré $𝐈$. $𝖳𝗈𝗄𝖾𝗇$ prend en entrée la clé secrète $K$ et un mot clé $w$ et retourne un jeton de recherche $tk$. $𝖲𝖾𝖺𝗋𝖼𝗁$ prend en entrée la collection de documents chiffrés $𝐄𝐃$, l'index chiffré $𝐈$ et un jeton de recherche $tk$ et retourne un ensemble de documents chiffrés $𝐑\subseteq 𝐄𝐃$

Utilisation pratiques des algorithmes

Un schéma statique est utilisé par un client et un serveur comme suit. Le client chiffre sa collection de documents à l'aide de l'algorithme $𝖲𝖾𝗍𝗎𝗉$ qui renvoie une clé secrète $K$ et une collection de documents chiffrés $𝐄𝐃$. Le client garde secrète la clé $K$ et envoie $𝐄𝐃$ et $𝐈$ au serveur. Pour rechercher un mot-clé $w$, le client exécute l'algorithme $𝖲𝖾𝖺𝗋𝖼𝗁𝖳𝗈𝗄𝖾𝗇$ avec $K$ et $w$ pour générer un jeton de recherche $tk$ envoyé au serveur. Le serveur exécute la recherche avec $𝐄𝐃$ et $tk$ et renvoie au client les documents chiffrés retournés par l'algorithme $𝖲𝖾𝖺𝗋𝖼𝗁$.

Schéma dynamique

Un schéma dynamique supporte, en plus de la recherche, l'insertion et la suppression de documents. Un schéma dynamique se compose de sept algorithmes $𝖲𝖲𝖤\mathsf{=}\mathsf{(}𝖲𝖾𝗍𝗎𝗉,𝖳𝗈𝗄𝖾𝗇,𝖲𝖾𝖺𝗋𝖼𝗁,𝖨𝗇𝗌𝖾𝗋𝗍𝖳𝗈𝗄𝖾𝗇,𝖨𝗇𝗌𝖾𝗋𝗍,𝖣𝖾𝗅𝖾𝗍𝖾𝖳𝗈𝗄𝖾𝗇,𝖣𝖾𝗅𝖾𝗍𝖾\mathsf{)}$Modèle:Sfn où $𝖲𝖾𝗍𝗎𝗉$, $𝖳𝗈𝗄𝖾𝗇$ et $𝖲𝖾𝖺𝗋𝖼𝗁$ sont comme dans le cas statique.

Présentation des algorithmes

$𝖨𝗇𝗌𝖾𝗋𝗍𝖳𝗈𝗄𝖾𝗇$ prend en entrée la clé secrète $K$ et un nouveau document ${\mathrm{D}}_{\mathrm{n}\mathrm{+}\mathrm{1}}$ et retourne un jeton d'insertion $itk$. $𝖨𝗇𝗌𝖾𝗋𝗍$ prend en entrée la collection de documents chiffrés $\mathrm{E}\mathrm{D}\mathrm{C}$ et un jeton d'insertion $itk$ et retourne une collection à jour de documents chiffrés $𝐄{𝐃}^{\prime }$. $𝖣𝖾𝗅𝖾𝗍𝖾𝖳𝗈𝗄𝖾𝗇$ prend en entrée la clé secrète $K$ et un identifiant de document $id$ et retourne un jeton de suppression $dtk$. $𝖣𝖾𝗅𝖾𝗍𝖾$ prend en entrée la collection de documents cryptées $\mathrm{E}\mathrm{D}\mathrm{C}$ et un jeton de suppression $dtk$ et retourne une collection à jour de documents chiffrés $𝐄{𝐃}^{\prime }$.

Utilisation pratique des algorithmes

Pour ajouter un nouveau document ${\mathrm{D}}_{\mathrm{n}\mathrm{+}\mathrm{1}}$ le client exécute $𝖨𝗇𝗌𝖾𝗋𝗍𝖳𝗈𝗄𝖾𝗇$ avec $K$ et ${\mathrm{D}}_{\mathrm{n}\mathrm{+}\mathrm{1}}$ pour générer un jeton d'insertion $itk$ qu'il envoie au serveur. Le serveur exécute $𝖨𝗇𝗌𝖾𝗋𝗍$ avec $𝐄𝐃$ et $itk$ et stocke la collection à jour de documents chiffrés. Pour supprimer un document avec identifiant $id$, le client exécute l'algorithme $𝖣𝖾𝗅𝖾𝗍𝖾𝖳𝗈𝗄𝖾𝗇$ avec $K$ et $id$ pour générer un jeton de suppression $dtk$ qu'il envoie au serveur. Le serveur exécute $𝖣𝖾𝗅𝖾𝗍𝖾$ avec $𝐄𝐃$ et $dtk$ et stocke la collection à jour de documents chiffrés.

Un schéma n'implémentant pas $𝖣𝖾𝗅𝖾𝗍𝖾𝖳𝗈𝗄𝖾𝗇$ et $𝖣𝖾𝗅𝖾𝗍𝖾$ est dit semi-dynamique.

Historique du chiffrement symétrique cherchable

Le problème de la recherche sur des documents chiffrées a été considéré d'abord par Song, Wagner et PerrigModèle:Sfn bien que des travaux antérieurs sur Oblivious RAM par Goldreich et OstrovskyModèle:Sfn puissent être utilisés en théorie pour résoudre le problème. Ce travailModèle:Sfn a proposé un schéma chiffrement cherchable avec un algorithme de recherche avec un complexité temporelle en $O(s)$, où $s=|𝐃|$. GohModèle:Sfn et Chang et MitzenmacherModèle:Sfn ont donné de nouvelles constructions SSE avec des algorithmes de recherche qui s'exécutent en $O(n)$, où $n$ est le nombre de documents. Curtmola, Garay, Kamara et OstrovskyModèle:Sfn ont ensuite proposé deux constructions statiques avec un temps optimal de recherche en $O(\mathrm{o}\mathrm{p}\mathrm{t})$, où $\mathrm{o}\mathrm{p}\mathrm{t}$ est le nombre de documents contenant $w$. Ce travail proposait également une construction semi-dynamique avec un temps de recherche en $O(\mathrm{o}\mathrm{p}\mathrm{t}\cdot \log (u))$, où $u$ est le nombre de mises à jour. Un schéma dynamique optimale a plus tard été proposée par Kamara, Papamanthou et RoederModèle:Sfn.

GohModèle:Sfn et Chang et MitzenmacherModèle:Sfn ont proposé des définitions de sécurité pour le chiffrement symétrique cherchable. Celles-ci ont été renforcées et étendues par Curtmola, Garay, Kamara et OstrovskyModèle:Sfn qui ont proposé la notion de sécurité adaptative pour cette primitive cryptographique. Ce travail a également été le premier à identifier les informations révélées indirectement par le protocole et à les encadrer dans une définition de sécurité. Ces fuites d'information ont ensuite été formalisées et généralisées par Chase et KamaraModèle:Sfn. Islam, Kuzu et Kantarcioglu ont décrit la première attaque basée sur cette fuite d'informationModèle:Sfn.

Toutes les constructions mentionnées précédemment supportent la recherche par mot-clé. Cash, Jarecki, Jutla, Krawczyk, Roşu et SteinerModèle:Sfn ont proposé un schéma supportant recherche conjonctive de plusieurs mots en temps sous-linéaire en $n$. Le schéma peut également être étendu pour prendre en charge les recherches disjonctives et booléennes en temps sous-linéaire. Dans le même temps, Pappas Modèle:Et al.Modèle:Sfn ont décrit une construction qui prend en charge les recherches conjonctives et toutes les recherches disjonctives et booléennes en temps sous-linéaire.

Sécurité

Les schémas de chiffrement symétrique cherchable sont conçus pour garantir que le serveur ne peut pas apprendre d'informations partielles sur les documents ou sur les requêtes de recherche au-delà d'une fuite d'information bien définie et raisonnable. Les schémas tentent de minimiser les fuites tout en obtenant la meilleure efficacité de recherche possible. La sécurité peut être analysée dans plusieurs modèles contradictoires, mais les plus courants sont le modèle persistantModèle:Sfn et le modèle instantanéModèle:Sfn.

Sécurité dans le modèle persistant

Un adversaire dans le modèle persistant reçoit la collection de données chiffrées et une transcription de toutes les opérations exécutées sur la collection.

Dans le modèle persistant, il existe des schémas qui permettent d'obtenir une grande variété de profils de fuite. Le profil de fuite le plus courant pour les schémas statiques avec recherche par mot-clé en un temps optimal est ${\mathrm{\Lambda }}_{\mathrm{o}\mathrm{p}\mathrm{t}}$. Ce profil de fuite révèle le nombre et la taille des documents dans la collection et, pour chaque requête, il est possible d'identifier si la requête a déjà été exécutée et quels documents chiffrés ont été retournésModèle:SfnModèle:,Modèle:Sfn. On sait cependant comment construire des schémas évitant ces fuites induisent d'importants coûts supplémentairesModèle:SfnModèle:,Modèle:Sfn.

Lorsque l'on considère les schémas dynamiques, l'état de l'art permet une recherche en temps optimal avec des profil de fuite garantissant une « confidentialité avant »Modèle:Sfn, ce qui signifie que les insertions ne peuvent pas être corrélées avec les requêtes de recherche passées.

Sécurité dans le modèle d'instantané

Un adversaire dans le modèle instantané ne reçoit que la collection de données chiffrées.

Dans le modèle d'instantané, il est possible de construire des schémas dynamiques efficaces ne révélant que le nombre et la taille des documentsModèle:Sfn. Lors de l'utilisation d'un schéma sécurisé dans le modèle d'instantané, il convient d'examiner attentivement la manière dont le schéma sera déployé, car certains systèmes peuvent mettre en cache les requêtes de recherche précédentesModèle:Sfn.

Cryptanalyse

Modèle:Article connexe Un profil de fuite ne décrit que la fuite d'un schéma donné, mais ne dit rien sur l'exploitation potentielle d'une telle fuite. La cryptanalyse est donc utilisée pour mieux comprendre la sécurité réelle d'un profil de fuite. Il existe une grande variété d'attaques, basées sur une variété d'hypothèses et attaquant différents profils de fuiteModèle:SfnModèle:,Modèle:Sfn.

Annexes

Bibliographie

• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Chapitre.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Chapitre.
• Modèle:Chapitre.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Chapitre

Articles connexes

• Chiffrement homomorphe
• Modèle:Lien
• Modèle:Lien
• Modèle:Lien

Modèle:Portail