Géométrie et algèbre effectives

Un protocole de récupération confidentielle d’information (private information retrieval, PIR) permet d’extraire l’entrée D_i d’une base de données D, sans révéler d’information sur i à l’entité qui détient D. Dans cet exposé, nous donnerons un aperçu de techniques existantes pour la construction de tels protocoles. Nous préciserons notamment des paramètres qui quantifient leur efficacité, tels que la complexité algorithmique des serveurs, la complexité de communication ou la redondance de stockage. Nous présenterons enfin deux constructions de protocoles de PIR. La première, fondée sur des objets combinatoires appelés designs transversaux, atteint une complexité calculatoire optimale pour les serveurs qui détiennent la base de données. La seconde se concentre sur la complexité de communication, et se place dans le contexte de fichiers encodés à l’aide de codes régénérants optimaux. ​