Séminaire LJK-Modèles et Algorithmes Déterministes: CASYS

 

Le Jeudi 31 Janvier 2019 à 9h30 en Salle 106 - Batiment IMAG

 

Séminaire de Julien LAVAUZELLE (IRMAR, Université de Rennes 1)

 

Autour de la construction de protocoles de Private Information Retrieval

 

Résumé:

 

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.