Chiffrement symétrique cherchable
# Chiffrement symétrique cherchable

Le chiffrement symétrique cherchable (ou Searchable Symmetric Encryption 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 $\mathbf {D} =(\mathrm {D_{1}} ,\dots ,\mathrm {D_{n}} )$, avec chaque document $\mathrm {D_{i}} \subseteq \mathbb {W}$ considéré comme un ensemble de mots-clés issus de l'espace de mots-clés $\mathbb {W}$ . Étant donné la clé de chiffrement $K$ et un mot-clé $w\in \mathbb {W}$, 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 {SSE=(Setup,Token,Search)}}$$^,.$

**Présentation des algorithmes**

${\mathsf {Setup}}$ prend en entrée un paramètre de sécurité $k$ et une collection de documents $\mathbf {D}$ et retourne une clé symétrique $K$, une collection de documents cryptés $\mathbf {ED}$ et un index chiffré $\mathbf {I}$. ${\mathsf {Token}}$ prend en entrée la clé secrète $K$ et un mot clé $w$ et retourne un jeton de recherche $tk$. ${\mathsf {Search}}$ prend en entrée la collection de documents chiffrés $\mathbf {ED}$, l'index chiffré $\mathbf {I}$ et un jeton de recherche $tk$ et retourne un ensemble de documents chiffrés $\mathbf {R} \subseteq \mathbf {ED}$

**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 ${\mathsf {Setup}}$ qui renvoie une clé secrète $K$ et une collection de documents chiffrés $\mathbf {ED}$. Le client garde secrète la clé $K$ et envoie $\mathbf {ED}$ et $\mathbf {I}$ au serveur. Pour rechercher un mot-clé $w$, le client exécute l'algorithme ${\mathsf {SearchToken}}$ avec $K$ et $w$ pour générer un jeton de recherche $tk$ envoyé au serveur. Le serveur exécute la recherche avec $\mathbf {ED}$ et $tk$ et renvoie au client les documents chiffrés retournés par l'algorithme ${\mathsf {Search}}$.

### 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 {SSE=(Setup,Token,Search,InsertToken,Insert,DeleteToken,Delete)}}$ où ${\mathsf {Setup}}$, ${\mathsf {Token}}$ et ${\mathsf {Search}}$ sont comme dans le cas statique.

**Présentation des algorithmes**

${\mathsf {InsertToken}}$ prend en entrée la clé secrète $K$ et un nouveau document $\mathrm {D_{n+1}}$ et retourne un jeton d'insertion $itk$. ${\mathsf {Insert}}$ prend en entrée la collection de documents chiffrés $\mathrm {EDC}$ et un jeton d'insertion $itk$ et retourne une collection à jour de documents chiffrés $\mathbf {ED'}$. ${\mathsf {DeleteToken}}$ prend en entrée la clé secrète $K$ et un identifiant de document $id$ et retourne un jeton de suppression $dtk$. ${\mathsf {Delete}}$ prend en entrée la collection de documents cryptées $\mathrm {EDC}$ et un jeton de suppression $dtk$ et retourne une collection à jour de documents chiffrés $\mathbf {ED'}$.

**Utilisation pratique des algorithmes**

Pour ajouter un nouveau document $\mathrm {D_{n+1}}$ le client exécute ${\mathsf {InsertToken}}$ avec $K$ et $\mathrm {D_{n+1}}$ pour générer un jeton d'insertion $itk$ qu'il envoie au serveur. Le serveur exécute ${\mathsf {Insert}}$ avec $\mathbf {ED}$ et $itk$ et stocke la collection à jour de documents chiffrés. Pour supprimer un document avec identifiant $id$, le client exécute l'algorithme ${\mathsf {DeleteToken}}$ avec $K$ et $id$ pour générer un jeton de suppression $dtk$ qu'il envoie au serveur. Le serveur exécute ${\mathsf {Delete}}$ avec $\mathbf {ED}$ et $dtk$ et stocke la collection à jour de documents chiffrés.

Un schéma n'implémentant pas ${\mathsf {DeleteToken}}$ et ${\mathsf {Delete}}$ 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(s)$, où $s=|\mathbf {D} |$. Goh et Chang et Mitzenmacher 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 Ostrovsky ont ensuite proposé deux constructions statiques avec un temps optimal de recherche en $O(\mathrm {opt} )$, où $\mathrm {opt}$ est le nombre de documents contenant $w$. Ce travail proposait également une construction semi-dynamique avec un temps de recherche en $O(\mathrm {opt} \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 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 $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 et al. 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 $\Lambda _{\mathrm {opt} }$. 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^,.$

