« Chiffrement symétrique cherchable » : différence entre les versions

Contenu supprimé Contenu ajouté

Intégrés

Version du 28 janvier 2023 à 00:39

Le chiffrement symétrique consultable (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. ^[1] ^[2] 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)}}$ qui fonctionnent comme suit :

${\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$ et une collection de documents cryptés $\mathbf {ED}$
${\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}$ et un jeton de recherche $tk$ et retourne un ensemble de documents chiffrés $\mathbf {R} \subseteq \mathbf {ED}$

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}$ 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 et les algorithmes restants fonctionnent comme suit :

${\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'}$

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 ^[1] bien que des travaux antérieurs sur Oblivious RAM par Goldreich et Ostrovsky ^[3] puissent être utilisés en théorie pour résoudre le problème. Ce travail ^[1] a proposé un schéma chiffrement cherchable avec un algorithme de recherche avec un complexité temporelle en $O(s)$ , où $s=|\mathbf {D} |$ . Goh ^[4] et Chang et Mitzenmacher ^[5] 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 ^[2] 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. ^[6]

Goh ^[4] et Chang et Mitzenmacher ^[5] 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 ^[2] qui ont proposé la notion de sécurité adaptative pour cette primitive cryptographie. 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 . ^[7] Islam, Kuzu et Kantarcioglu ont décrit la première attaque basée sur cette fuite d'information. ^[8]

Toutes les constructions mentionnées précédemment supportent la recherche par mot-clé. Cash, Jarecki, Jutla, Krawczyk, Rosu et Steiner ^[9] 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. ^[10] 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, ^[2] où un adversaire reçoit la collection de données chiffrées et une transcription de toutes les opérations exécutées sur la collection.
le modèle instantané, ^[11] où un adversaire ne reçoit que la collection de données chiffrées.

Sécurité dans le modèle persistant

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 . ^[2] ^[12] On sait cependant comment construire des schémas évitant ces fuites induisent d'importants coûts supplémentaires. ^[13] ^[14]

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" ^[15], 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é

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. ^[11] 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. ^[16]

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. ^[17] ^[18]

Voir aussi

Références

↑ ^{a b et c} Dawn Xiaoding Song, Wagner et Perrig, « Practical techniques for searches on encrypted data », Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, IEEE Comput. Soc,‎ 2000, p. 44–55 (ISBN 0-7695-0665-8, DOI 10.1109/secpri.2000.848445, S2CID 2829840, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :0 » est défini plusieurs fois avec des contenus différents.
↑ ^{a b c d et e} Curtmola, Garay, Kamara et Ostrovsky, « Searchable symmetric encryption: improved definitions and efficient constructions », Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, Virginia, USA, Association for Computing Machinery, cCS '06,‎ 30 octobre 2006, p. 79–88 (ISBN 978-1-59593-518-2, DOI 10.1145/1180405.1180417, S2CID 961719, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :1 » est défini plusieurs fois avec des contenus différents.
↑ Goldreich et 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, lire en ligne)
↑ ^{a et b} Goh, « Secure Indexes » Erreur de référence : Balise <ref> incorrecte : le nom « :2 » est défini plusieurs fois avec des contenus différents.
↑ ^{a et b} (en) Chang et Mitzenmacher, « Privacy Preserving Keyword Searches on Remote Encrypted Data », Applied Cryptography and Network Security, Berlin, Heidelberg, Springer, lecture Notes in Computer Science, vol. 3531,‎ 2005, p. 442–455 (ISBN 978-3-540-31542-1, DOI 10.1007/11496137_30, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :3 » est défini plusieurs fois avec des contenus différents.
↑ Kamara, Papamanthou et Roeder, « Dynamic searchable symmetric encryption », Proceedings of the 2012 ACM Conference on Computer and Communications Security, New York, NY, USA, Association for Computing Machinery, cCS '12,‎ 16 octobre 2012, p. 965–976 (ISBN 978-1-4503-1651-4, DOI 10.1145/2382196.2382298, S2CID 243046, lire en ligne)
↑ (en) Chase et Kamara, « Structured Encryption and Controlled Disclosure », Advances in Cryptology - ASIACRYPT 2010, Berlin, Heidelberg, Springer, lecture Notes in Computer Science, vol. 6477,‎ 2010, p. 577–594 (ISBN 978-3-642-17373-8, DOI 10.1007/978-3-642-17373-8_33, lire en ligne)
↑ Islam, Kuzu et Kantarcioglu, « Access Pattern disclosure on Searchable Encryption:Ramification, Attack and Mitigation », Network and Distributed System Security (NDSS) Symposium, {{Article}} : paramètre « date » manquant (lire en ligne)
↑ (en) Cash, Jarecki, Jutla et Krawczyk, « Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries », Advances in Cryptology – CRYPTO 2013, Berlin, Heidelberg, Springer, lecture Notes in Computer Science, vol. 8042,‎ 2013, p. 353–373 (ISBN 978-3-642-40041-4, DOI 10.1007/978-3-642-40041-4_20, lire en ligne)
↑ Pappas, Krell, Vo et Kolesnikov, « Blind Seer: A Scalable Private DBMS », 2014 IEEE Symposium on Security and Privacy, IEEE,‎ mai 2014, p. 359–374 (ISBN 978-1-4799-4686-0, DOI 10.1109/sp.2014.30, S2CID 9165575, lire en ligne)
↑ ^{a et b} (en) Amjad, Kamara et Moataz, « Breach-Resistant Structured Encryption », Proceedings on Privacy Enhancing Technologies, vol. 2019, n^o 1,‎ 1^er janvier 2019, p. 245–265 (DOI 10.2478/popets-2019-0014, S2CID 4047057, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :4 » est défini plusieurs fois avec des contenus différents.
↑ (en-US) « Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium » (consulté le 22 février 2022)
↑ (en) Kamara, Moataz et Ohrimenko, « Structured Encryption and Leakage Suppression », Advances in Cryptology – CRYPTO 2018, Cham, Springer International Publishing, lecture Notes in Computer Science, vol. 10991,‎ 2018, p. 339–370 (ISBN 978-3-319-96884-1, DOI 10.1007/978-3-319-96884-1_12, S2CID 51603585, lire en ligne)
↑ (en-US) « Revisiting Leakage Abuse Attacks – NDSS Symposium » (consulté le 22 février 2022)
↑ (en-US) « Practical Dynamic Searchable Encryption with Small Leakage – NDSS Symposium » (consulté le 22 février 2022)
↑ Grubbs, Ristenpart et Shmatikov, « Why Your Encrypted Database Is Not Secure », Proceedings of the 16th Workshop on Hot Topics in Operating Systems, New York, NY, USA, Association for Computing Machinery, hotOS '17,‎ 7 mai 2017, p. 162–168 (ISBN 978-1-4503-5068-6, DOI 10.1145/3102980.3103007, S2CID 10111288, lire en ligne)
↑ Yao, Zheng, Guo et Wang, « SoK: A Systematic Study of Attacks in Efficient Encrypted Cloud Data Search », Proceedings of the 8th International Workshop on Security in Blockchain and Cloud Computing, New York, NY, USA, Association for Computing Machinery, sBC '20,‎ 6 octobre 2020, p. 14–20 (ISBN 978-1-4503-7609-9, DOI 10.1145/3384942.3406869, S2CID 222179683, lire en ligne)
↑ Kamara, Kati, Moataz et Schneider, « Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data », {{Article}} : paramètre « périodique » manquant,‎ 2021 (lire en ligne)

[:0-1] {a b et c} Dawn Xiaoding Song, Wagner et Perrig, « Practical techniques for searches on encrypted data », Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, IEEE Comput. Soc,‎ 2000, p. 44–55 (ISBN 0-7695-0665-8, DOI 10.1109/secpri.2000.848445, S2CID 2829840, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :0 » est défini plusieurs fois avec des contenus différents.

[:1-2] {a b c d et e} Curtmola, Garay, Kamara et Ostrovsky, « Searchable symmetric encryption: improved definitions and efficient constructions », Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, Virginia, USA, Association for Computing Machinery, cCS '06,‎ 30 octobre 2006, p. 79–88 (ISBN 978-1-59593-518-2, DOI 10.1145/1180405.1180417, S2CID 961719, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :1 » est défini plusieurs fois avec des contenus différents.

[3] Goldreich et 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, lire en ligne)

[:2-4] {a et b} Goh, « Secure Indexes » Erreur de référence : Balise <ref> incorrecte : le nom « :2 » est défini plusieurs fois avec des contenus différents.

[:3-5] {a et b} (en) Chang et Mitzenmacher, « Privacy Preserving Keyword Searches on Remote Encrypted Data », Applied Cryptography and Network Security, Berlin, Heidelberg, Springer, lecture Notes in Computer Science, vol. 3531,‎ 2005, p. 442–455 (ISBN 978-3-540-31542-1, DOI 10.1007/11496137_30, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :3 » est défini plusieurs fois avec des contenus différents.

[6] Kamara, Papamanthou et Roeder, « Dynamic searchable symmetric encryption », Proceedings of the 2012 ACM Conference on Computer and Communications Security, New York, NY, USA, Association for Computing Machinery, cCS '12,‎ 16 octobre 2012, p. 965–976 (ISBN 978-1-4503-1651-4, DOI 10.1145/2382196.2382298, S2CID 243046, lire en ligne)

[7] (en) Chase et Kamara, « Structured Encryption and Controlled Disclosure », Advances in Cryptology - ASIACRYPT 2010, Berlin, Heidelberg, Springer, lecture Notes in Computer Science, vol. 6477,‎ 2010, p. 577–594 (ISBN 978-3-642-17373-8, DOI 10.1007/978-3-642-17373-8_33, lire en ligne)

[8] Islam, Kuzu et Kantarcioglu, « Access Pattern disclosure on Searchable Encryption:Ramification, Attack and Mitigation », Network and Distributed System Security (NDSS) Symposium, {{Article}} : paramètre « date » manquant (lire en ligne)

[9] (en) Cash, Jarecki, Jutla et Krawczyk, « Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries », Advances in Cryptology – CRYPTO 2013, Berlin, Heidelberg, Springer, lecture Notes in Computer Science, vol. 8042,‎ 2013, p. 353–373 (ISBN 978-3-642-40041-4, DOI 10.1007/978-3-642-40041-4_20, lire en ligne)

[10] Pappas, Krell, Vo et Kolesnikov, « Blind Seer: A Scalable Private DBMS », 2014 IEEE Symposium on Security and Privacy, IEEE,‎ mai 2014, p. 359–374 (ISBN 978-1-4799-4686-0, DOI 10.1109/sp.2014.30, S2CID 9165575, lire en ligne)

[:4-11] {a et b} (en) Amjad, Kamara et Moataz, « Breach-Resistant Structured Encryption », Proceedings on Privacy Enhancing Technologies, vol. 2019, n^o 1,‎ 1^er janvier 2019, p. 245–265 (DOI 10.2478/popets-2019-0014, S2CID 4047057, lire en ligne) Erreur de référence : Balise <ref> incorrecte : le nom « :4 » est défini plusieurs fois avec des contenus différents.

[12] (en-US) « Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium » (consulté le 22 février 2022)

[13] (en) Kamara, Moataz et Ohrimenko, « Structured Encryption and Leakage Suppression », Advances in Cryptology – CRYPTO 2018, Cham, Springer International Publishing, lecture Notes in Computer Science, vol. 10991,‎ 2018, p. 339–370 (ISBN 978-3-319-96884-1, DOI 10.1007/978-3-319-96884-1_12, S2CID 51603585, lire en ligne)

[14] (en-US) « Revisiting Leakage Abuse Attacks – NDSS Symposium » (consulté le 22 février 2022)

[15] (en-US) « Practical Dynamic Searchable Encryption with Small Leakage – NDSS Symposium » (consulté le 22 février 2022)

[16] Grubbs, Ristenpart et Shmatikov, « Why Your Encrypted Database Is Not Secure », Proceedings of the 16th Workshop on Hot Topics in Operating Systems, New York, NY, USA, Association for Computing Machinery, hotOS '17,‎ 7 mai 2017, p. 162–168 (ISBN 978-1-4503-5068-6, DOI 10.1145/3102980.3103007, S2CID 10111288, lire en ligne)

[17] Yao, Zheng, Guo et Wang, « SoK: A Systematic Study of Attacks in Efficient Encrypted Cloud Data Search », Proceedings of the 8th International Workshop on Security in Blockchain and Cloud Computing, New York, NY, USA, Association for Computing Machinery, sBC '20,‎ 6 octobre 2020, p. 14–20 (ISBN 978-1-4503-7609-9, DOI 10.1145/3384942.3406869, S2CID 222179683, lire en ligne)

[18] Kamara, Kati, Moataz et Schneider, « Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data », {{Article}} : paramètre « périodique » manquant,‎ 2021 (lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]