Les cryptographes conçoivent une approche pour une confidentialité totale des recherches | Magazine Quanta

Nous savons tous qu’il faut faire attention aux détails que nous partageons en ligne, mais les informations que nous recherchons peuvent également être révélatrices. Recherchez un itinéraire et notre position devient beaucoup plus facile à deviner. Recherchez un mot de passe dans une mine de données compromises et nous risquons de le divulguer nous-mêmes.

Ces situations alimentent une question clé en cryptographie : comment pouvez-vous extraire des informations d’une base de données publique sans rien révéler sur ce à quoi vous avez accédé ? C'est l'équivalent de consulter un livre à la bibliothèque sans que le bibliothécaire sache lequel.

Concevoir une stratégie qui résout ce problème – connue sous le nom de récupération d’informations privées – est « un élément de base très utile dans un certain nombre d’applications préservant la confidentialité », a déclaré David Wu, cryptographe à l'Université du Texas à Austin. Depuis les années 1990, les chercheurs ont approfondi la question et amélioré les stratégies d’accès privé aux bases de données. Un objectif majeur, encore impossible avec de grandes bases de données, est l’équivalent d’une recherche privée sur Google, où vous pouvez parcourir un tas de données de manière anonyme sans effectuer de gros travaux de calcul.

Aujourd'hui, trois chercheurs ont Fabriqué une version recherchée depuis longtemps de la récupération d'informations privées et l'a étendue pour construire une stratégie de confidentialité plus générale. L'œuvre, qui a reçu un Prix ​​du meilleur papier en juin à l'assemblée annuelle Symposium sur la théorie de l'informatique, fait tomber un obstacle théorique majeur sur la voie d’une recherche véritablement privée.

"[C'est] quelque chose en cryptographie que je suppose que nous voulions tous mais que nous ne croyions pas vraiment à son existence", a déclaré Vinod Vaikuntanathan, un cryptographe du Massachusetts Institute of Technology qui n'a pas participé à l'article. "C'est un résultat historique."

Le problème de l’accès aux bases de données privées a pris forme dans les années 1990. Au début, les chercheurs pensaient que la seule solution consistait à analyser l’intégralité de la base de données à chaque recherche, ce qui reviendrait à demander à un bibliothécaire de parcourir chaque étagère avant de revenir avec votre livre. Après tout, si la recherche sautait une section, le bibliothécaire saurait que votre livre ne se trouve pas dans cette partie de la bibliothèque.

Cette approche fonctionne assez bien à petite échelle, mais à mesure que la base de données se développe, le temps nécessaire à son analyse augmente au moins proportionnellement. À mesure que vous lisez des bases de données plus volumineuses – et Internet est une base de données assez importante – le processus devient d’une inefficacité prohibitive.

Au début des années 2000, les chercheurs ont commencé à soupçonner qu’ils pourraient contourner l’obstacle de l’analyse complète en « prétraitant » la base de données. En gros, cela signifierait coder l’intégralité de la base de données sous la forme d’une structure spéciale, afin que le serveur puisse répondre à une requête en lisant juste une petite partie de cette structure. Un prétraitement suffisamment minutieux pourrait, en théorie, signifier qu'un seul serveur hébergeant des informations ne passe par le processus qu'une seule fois, permettant ainsi à tous les futurs utilisateurs de récupérer des informations en privé sans aucun effort supplémentaire.

Pour Daniel Wiss, cryptographe à la Northeastern University et co-auteur du nouvel article, cela semblait trop beau pour être vrai. Vers 2011, il a commencé à essayer de prouver que ce genre de stratagème était impossible. « J'étais convaincu que cela n'était pas possible », a-t-il déclaré.

Mais en 2017, deux groupes de chercheurs publié résultats cela l'a fait changer d'avis. Ils ont construit les premiers programmes capables d'effectuer ce type de récupération d'informations privées, mais ils n'ont pas été en mesure de démontrer que ces programmes étaient sécurisés. (Les cryptographes démontrent la sécurité d'un système en montrant que le briser est aussi difficile que résoudre un problème difficile. Les chercheurs n'ont pas pu le comparer à un problème difficile canonique.)

Ainsi, même avec son espoir renouvelé, Wichs supposait qu’une version sécurisée de ces programmes était encore loin. Au lieu de cela, lui et ses co-auteurs — Wei-Kai Lin, maintenant à l'Université de Virginie, et Ethan Mook, également chez Northeastern, a travaillé sur des problèmes qu'ils pensaient plus faciles, qui impliquaient des cas où plusieurs serveurs hébergeaient la base de données.

Dans les méthodes étudiées, les informations contenues dans la base de données peuvent être transformées en une expression mathématique, que les serveurs peuvent évaluer pour extraire les informations. Les auteurs ont pensé qu’il pourrait être possible de rendre ce processus d’évaluation plus efficace. Ils ont joué avec une idée de 2011, lorsque d'autres chercheurs avaient trouvé un moyen d'évaluer rapidement une telle expression en la prétraitant, créant ainsi des tableaux de valeurs spéciaux et compacts qui vous permettent d'ignorer les étapes normales d'évaluation.

Cette méthode n'a produit aucune amélioration et le groupe a failli abandonner, jusqu'à ce qu'ils se demandent si cet outil pourrait réellement fonctionner dans le cas convoité d'un serveur unique. Ils ont constaté qu'ils choisissaient un polynôme avec suffisamment de soin et qu'un seul serveur pourrait le prétraiter sur la base du résultat de 2011, ce qui donnerait lieu au système de recherche sécurisé et efficace auquel nous réfléchissions depuis des années. Soudain, ils avaient résolu le problème le plus difficile après tout.

Au début, les auteurs n'y croyaient pas. « Voyons ce qui ne va pas », se souvient Wichs. "Nous avons continué à essayer de comprendre où cela tombait en panne."

Mais la solution tenait : ils avaient réellement découvert un moyen sécurisé de prétraiter une base de données sur un seul serveur afin que n'importe qui puisse extraire des informations en secret. "C'est vraiment au-delà de tout ce que nous avions espéré", a déclaré Yuval Ishaï, cryptographe au Technion en Israël qui n’a pas participé à ces travaux. C'est un résultat que « nous n'avons même pas eu le courage de demander », a-t-il déclaré.

Après avoir élaboré leur système de recherche secrète, les auteurs se sont tournés vers l'objectif réel d'une recherche privée sur Internet, qui est plus compliquée que d'extraire des informations d'une base de données, a déclaré Wichs. Le système de recherche privée à lui seul permet une version de recherche privée de type Google, mais il est extrêmement laborieux : vous exécutez vous-même l'algorithme de Google et extrayez secrètement des données d'Internet si nécessaire. Wichs a déclaré qu'une véritable recherche, dans laquelle vous envoyez une requête et restez assis pendant que le serveur collecte les résultats, est en réalité la cible d'une approche plus large connue sous le nom de cryptage homomorphe, qui dissimule les données afin que quelqu'un d'autre puisse les manipuler sans jamais rien en savoir. .

Les stratégies de chiffrement homomorphes typiques se heurteraient au même problème que la récupération d'informations privées, en parcourant péniblement tout le contenu d'Internet à chaque recherche. Mais en utilisant leur méthode de recherche privée comme échafaudage, les auteurs ont construit un nouveau système qui exécute des calculs qui ressemblent davantage aux programmes que nous utilisons quotidiennement, extrayant des informations de manière secrète sans balayer tout Internet. Cela augmenterait l’efficacité des recherches sur Internet et de tous les programmes nécessitant un accès rapide aux données.

Bien que le chiffrement homomorphique soit une extension utile du système de recherche privée, Ishai a déclaré qu'il considère la récupération d'informations privées comme le problème le plus fondamental. La solution des auteurs est la « pierre angulaire magique » et leur stratégie de chiffrement homomorphe en est une suite naturelle.

Pour l’instant, aucun des deux schémas n’est utile en pratique : le prétraitement est actuellement utile aux extrêmes, lorsque la taille de la base de données tend vers l’infini. Mais en réalité, son déploiement signifie que ces économies ne peuvent pas se matérialiser et que le processus prendrait trop de temps et d'espace de stockage.

Heureusement, a déclaré Vaikuntanathan, les cryptographes ont une longue histoire d’optimisation de résultats qui étaient initialement peu pratiques. Si les travaux futurs permettent de rationaliser l’approche, il pense que les recherches privées à partir de bases de données géantes pourraient être à portée de main. « Nous pensions tous que nous étions en quelque sorte coincés là-bas », a-t-il déclaré. "Ce que donne le résultat de Daniel, c'est de l'espoir."

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs en informatique et vous serez inscrit pour gagner gratuitement Quanta marchandise.