Autour de la construction de protocoles de Private Information Retrieval

Un protocole de récupération confidentielle d'information (private information retrieval, PIR) permet d'extraire n'importe quelle 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é algorithmique optimale. La seconde se concentre sur la complexité de communication, et se place dans le contexte d'une base de données encodée à l'aide de codes régénérants optimaux.