Chiffrement symétrique cherchable

Le chiffrement symétrique cherchable (ou  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échiffrer. 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 , avec chaque document  considéré comme un ensemble de mots-clés issus de l'espace de mots-clés  . Étant donné la clé de chiffrement  et un mot-clé , on peut générer un jeton de recherche  avec lequel on peut rechercher  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é .

Schéma statique, 
Un schéma statique se compose de trois algorithmes .

Présentation des algorithmes 
 prend en entrée un paramètre de sécurité  et une collection de documents  et retourne une clé symétrique , une collection de documents cryptés  et un index chiffré .  prend en entrée la clé secrète  et un mot clé  et retourne un jeton de recherche .  prend en entrée la collection de documents chiffrés , l'index chiffré  et un jeton de recherche  et retourne un ensemble de documents chiffrés

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  et une collection de documents chiffrés . Le client garde secrète la clé  et envoie  et  au serveur. Pour rechercher un mot-clé , le client exécute l'algorithme  avec  et  pour générer un jeton de recherche  envoyé au serveur. Le serveur exécute la recherche avec  et  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  où ,  et  sont comme dans le cas statique.

Présentation des algorithmes 
 prend en entrée la clé secrète  et un nouveau document  et retourne un jeton d'insertion .  prend en entrée la collection de documents chiffrés  et un jeton d'insertion  et retourne une collection à jour de documents chiffrés .  prend en entrée la clé secrète  et un identifiant de document  et retourne un jeton de suppression .  prend en entrée la collection de documents cryptées  et un jeton de suppression  et retourne une collection à jour de documents chiffrés .

Utilisation pratique des algorithmes 
Pour ajouter un nouveau document  le client exécute  avec  et  pour générer un jeton d'insertion  qu'il envoie au serveur. Le serveur exécute  avec  et  et stocke la collection à jour de documents chiffrés. Pour supprimer un document avec identifiant , le client exécute l'algorithme  avec  et  pour générer un jeton de suppression  qu'il envoie au serveur. Le serveur exécute  avec  et  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 Perrig bien que des travaux antérieurs sur Oblivious RAM par Goldreich et Ostrovsky puissent être utilisés en théorie pour résoudre le problème. Ce travail a proposé un schéma chiffrement cherchable avec un algorithme de recherche avec un complexité temporelle en , où . Goh et Chang et Mitzenmacher ont donné de nouvelles constructions SSE avec des algorithmes de recherche qui s'exécutent en , où  est le nombre de documents. Curtmola, Garay, Kamara et Ostrovsky ont ensuite proposé deux constructions statiques avec un temps optimal de recherche en , où  est le nombre de documents contenant . Ce travail proposait également une construction semi-dynamique avec un temps de recherche en , où  est le nombre de mises à jour. Un schéma dynamique optimale a plus tard été proposée par Kamara, Papamanthou et Roeder.

Goh et Chang et Mitzenmacher 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 Ostrovsky 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 Kamara. Islam, Kuzu et Kantarcioglu ont décrit la première attaque basée sur cette fuite d'information.

Toutes les constructions mentionnées précédemment supportent la recherche par mot-clé. Cash, Jarecki, Jutla, Krawczyk, Roşu et Steiner ont proposé un schéma supportant recherche conjonctive de plusieurs mots en temps sous-linéaire en . 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  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 persistant et le modèle instantané.

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 . 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és. On sait cependant comment construire des schémas évitant ces fuites induisent d'importants coûts supplémentaires. 

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 », 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 documents. 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édentes.

Cryptanalyse 

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 fuite.

Notes et références

Notes

Références

Annexes

Bibliographie 
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .

Articles connexes 
 Chiffrement homomorphe
 
 
 

Primitive cryptographique