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.

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

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.

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Searchable symmetric encryption » (voir la liste des auteurs).

Annexes

Bibliographie

• [Amjad, Kamara et Moataz 2019] (en) Ghous Amjad, Seny Kamara et Tarik Moataz, « Breach-Resistant Structured Encryption », dans Proceedings on Privacy Enhancing Technologies, vol. 2019, 1^er janvier 2019 (DOI 10.2478/popets-2019-0014, S2CID 4047057, lire en ligne [PDF]), p. 245-265.
• [Blackstone, Kamara et Moataz 2019] (en) Laura Blackstone, Seny Kamara et Tarik Moataz, « Revisiting Leakage Abuse Attacks », NDSS Symposium,‎ 2019 (résumé, lire en ligne [PDF]).
• [Cash et al. 2013] (en) David Cash, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cătălin Roşu et Michael Steiner, « Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries », dans Advances in Cryptology – CRYPTO 2013, Springer, coll. « Lecture Notes in Computer Science » (n^o 8042), 2013 (ISBN 978-3-642-40041-4, DOI 10.1007/978-3-642-40041-4_20), p. 353–373.
• [Cash et al. 2014] (en) David Cash, Joseph Jaeger, Stanislaw Jarecki†, Charanjit Jutla, Hugo Krawczyk, Marcel-Cătălin Roşu et Michael Steiner, « Dynamic Searchable Encryption in Very-Large Databases : Data Structures and Implementation », NDSS Symposium,‎ 22 février 2014 (résumé, lire en ligne [PDF]).
• [Chang et Mitzenmacher 2005] (en) Yan-Cheng Chang et Michael Mitzenmacher, « Privacy Preserving Keyword Searches on Remote Encrypted Data », dans Applied Cryptography and Network Security, Springer, coll. « Lecture Notes in Computer Science » (n^o 3531), 2005 (ISBN 978-3-540-31542-1, DOI 10.1007/11496137_30), p. 442-455.
• [Chase et Kamara 2010] (en) Melissa Chase et Seny Kamara, « Structured Encryption and Controlled Disclosure », dans Advances in Cryptology - ASIACRYPT 2010, Springer, coll. « Lecture Notes in Computer Science » (n^o 6477), 2010 (ISBN 978-3-642-17373-8, DOI 10.1007/978-3-642-17373-8_33), p. 577-594.
• [Curtmola et al. 2006] (en) Reza Curtmola, Juan Garay, Seny Kamara et Rafail Ostrovsky, « Searchable symmetric encryption: improved definitions and efficient constructions », dans Proceedings of the 13th ACM Conference on Computer and Communications Security, Association for Computing Machinery, 30 octobre 2006 (ISBN 978-1-59593-518-2, DOI 10.1145/1180405.1180417, S2CID 961719), p. 79–88.
• [Goh 2004] (en) Eu-Jin Goh, « Secure Indexes », Cryptology ePrint Archive,‎ 16 mars 2004 (résumé, lire en ligne [PDF]).
• [Goldreich et Ostrovsky 1996] (en) Oded Goldreich et Rafail Ostrovsky, « Software protection and simulation on oblivious RAMs », Journal of the ACM, vol. 43, n^o 3,‎ mai 1996, p. 431-473 (ISSN 0004-5411, DOI 10.1145/233551.233553, hdl 1721.1/103684, S2CID 7502114).
• [Grubbs, Ristenpart et Shmatikov 2017] (en) Paul Grubbs, Thomas Ristenpart et Vitaly Shmatikov, « Why Your Encrypted Database Is Not Secure », dans Proceedings of the 16th Workshop on Hot Topics in Operating Systems, Association for Computing Machinery, 7 mai 2017 (ISBN 978-1-4503-5068-6, DOI 10.1145/3102980.3103007, S2CID 10111288), p. 162–168.
• [Islam, Kuzu et Kantarcioglu 2011] (en) Mohammad Islam, Mehmet Kuzu et Murat Kantarcioglu, « Access Pattern disclosure on Searchable Encryption : Ramification, Attack and Mitigation », Network and Distributed System Security (NDSS) Symposium,‎ 27 novembre 2011 (lire en ligne [PDF]).
• [Kamara et al. 2021] (en) Seny Kamara, Abdelkarim Kati, Tarik Moataz et Thomas Schneider, « Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data », Cryptology ePrint Archive,‎ 2021 (résumé, lire en ligne [PDF]).
• [Kamara, Moataz et Ohrimenko 2018] (en) Seny Kamara, Tarik Moataz et Olya Ohrimenko, « Structured Encryption and Leakage Suppression », dans Advances in Cryptology – CRYPTO 2018, Springer International Publishing, coll. « Lecture Notes in Computer Science » (n^o 10991), 2018 (ISBN 978-3-319-96884-1, DOI 10.1007/978-3-319-96884-1_12, S2CID 51603585), p. 339-370.
• [Karama, Papamanthou et Roeder 2012] (en) Seny Kamara, Charalampos Papamanthou et Tom Roeder, « Dynamic searchable symmetric encryption », dans Proceedings of the 2012 ACM Conference on Computer and Communications Security, Association for Computing Machinery, 16 octobre 2012 (ISBN 978-1-4503-1651-4, DOI 10.1145/2382196.2382298, S2CID 243046), p. 965-976.
• [Pappas et al. 2014] (en) Vasilis Pappas, Fernando Krell, Binh Vo et Vladimir Kolesnikov, « Blind Seer : A Scalable Private DBMS », dans 2014 IEEE Symposium on Security and Privacy, IEEE, mai 2014 (ISBN 978-1-4799-4686-0, DOI 10.1109/sp.2014.30, S2CID 9165575), p. 359-374.
• [Song, Wagner et Perrig 2000] (en) Dawn Xiaoding Song, David Wagner et A. Perrig, « Practical techniques for searches on encrypted data », dans Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, IEEE Comput. Soc, 2000 (ISBN 0-7695-0665-8, DOI 10.1109/secpri.2000.848445, S2CID 2829840), p. 44-55.
• [Stefanov, Papamanthou et Shi 2014] (en) Emil Stefanov, Charalampos Papamanthou et Elaine Shi, « Practical Dynamic Searchable Encryption with Small Leakage », NDSS Symposium,‎ 22 février 2014 (résumé, lire en ligne [PDF]).
• [Yao et al. 2020] (en) Jing Yao, Yifeng Zheng, Yu Guo et Cong Wang, « SoK : A Systematic Study of Attacks in Efficient Encrypted Cloud Data Search », dans Proceedings of the 8th International Workshop on Security in Blockchain and Cloud Computing, Association for Computing Machinery, 6 octobre 2020 (ISBN 978-1-4503-7609-9, DOI 10.1145/3384942.3406869, S2CID 222179683), p. 14-20.
• [Bösch et al. 2014] (en) Christoph Bösch, Pieter Hartel, Willem Jonker et Andreas Peter, « A Survey of Provably Secure Searchable Encryption », dans ACM Computing Surveys, Association for Computing Machinery, 25 août 2014 (DOI 10.1145/2636328)

Articles connexes

• Chiffrement homomorphe
• RAM inconsciente (en)
• Chiffrement structuré (en)
• Chiffrement déterministe (en)