October 04, 2022. Mathias Joly

Titre:  Les protocoles de PIR (Private Information Retrieval)
et leurs applications à la détection d’URLs malveillantes.

Résumé: Les protocoles de PIR permettent à un client de
récupérer un élément x_i d’une base de données en connaissant
l’indice i de cet élément dans la base de données, sans que les
serveurs ne puisse déterminer i. L’état de l’art des protocoles
de PIR à deux serveurs montre que le protocole de BGI16 a
les meilleurs coûts de communication et les meilleurs coûts
de calcul côté client. 
Ce protocole utilise une DPF (Distributed Point Function).
Si une Point Function est une fonction qui est nulle partout
sauf en un point a où elle vaut b, une Distributed Point Function
est un couple de fonctions pseudo-aléatoires, qui sont identiques
partout sauf en a, où faire le XOR de leurs valeurs donne b
(connaître l’une de ces fonctions ne donne aucune information
sur a ou b).
Lorsqu’un client veut se rendre sur un site web, le navigateur
doit vérifier que l’URL de ce site ne figure pas dans la liste des
URLs malveillantes connues. Pour l’instant, cette vérification
se fait par des serveurs à distance de manière non confidentielle.
Il y a-t-il un schéma qui conserve la confidentialité de l’URL et
garde un temps d’exécution acceptable ?

Je présenterai donc l’état de l’art des PIR à deux serveurs,
puis j’expliquerai comment construire une DPF ainsi qu’un protocole
de PIR avec DPF, enfin je montrerai comment appliquer ce protocole
à la détection d’URLs malveillantes.