Privacy-Preserving Computations on Sparse Data

Calculs respectueux de la vie privée sur données éparses Les fuites de données et atteintes à la vie privée soulèvent des inquiétudes croissantes relatives à la protection des informations personnelles. Pour répondre à ces préoccupations, des protocoles cryptographiques appelés calculs multipartites, ou en anglais, Multi-Party Computations (MPC) ont été développés afin de permettre à plusieurs entités d'effectuer conjointement des calculs sur leurs données privées sans les révéler. Ces protocoles ont trouvé des applications notamment dans la lutte contre la fraude fiscale, la santé et l'apprentissage automatique. Cependant, les protocoles MPC existants demeurent insuffisants pour de nombreux scénarios réalistes, en particulier lorsqu'il s'agit de traiter des données de grande dimension ou présentant une structure particulière.Cette thèse se concentre sur les données éparses -- des jeux de données contenant majoritairement des valeurs nulles, qui apparaissent naturellement dans des applications telles que les systèmes de recommandation ou la santé. Alors que les algorithmes pour traiter les données éparses en clair sont bien établis, très peu de protocoles cryptographiques sont optimisés pour ce cadre, ce qui limite l'utilisation de MPC dans les domaines où les données éparses sont la norme.Les contributions centrales de cette thèse introduisent de nouveaux protocoles cryptographiques adaptés à ces données. Nous proposons des protocoles pour la multiplication sécurisée de données éparses, permettant des gains de performance qui rendent possibles des applications jusque-là irréalisables. Nous concevons également de nouveaux algorithmes de Function Secret Sharing (FSS) capables d'effectuer d'agréger des données éparses.Au-delà de ces protocoles, la thèse apporte plusieurs contributions transversales qui interrogent des hypothèses fondamentales et des aspects pratiques des technologies de protection de la vie privée. Nous étudions le rôle des fuites d'information dans les calculs sur données éparses en analysant les fuites dans le chiffrement cherchable, en proposant de nouvelles attaques et en apportant un point de vue statistique sur leurs risques. Nous présentons Fedivertex, un nouveau jeu de données de graphes basé sur les réseaux sociaux décentralisés, conçu pour l'évaluation de l'apprentissage automatique décentralisé. Enfin, nous évaluons la consommation énergétique de plusieurs technologies de protection de la vie privée.Prises dans leur ensemble, ces contributions font progresser la conception de protocoles cryptographiques optimisés pour les données éparses et offrent une perspective plus large sur les défis liés au déploiement pratique des calculs préservant la confidentialité.