Résumé - Récupération d'informations privées symétrique (SPIR) sur des systèmes répliqués basés sur des graphes

Récupération d'informations privées symétrique (SPIR) sur des systèmes répliqués basés sur des graphes

2025-07-23 17:51:08

{"Shreya Meel","Sennur Ulukus"}

{cs.IT,cs.CR,cs.DB,cs.NI,eess.SP,math.IT}

Ce document présente le problème de recherche d'information privée symétrique (SPIR) sur des bases de données répliquées modélisées par un graph simple. Chaque sommet du graph correspond à un serveur, et un message est répliqué sur deux serveurs si et seulement si il existe une arête entre eux. L'objectif est de permettre à un utilisateur de récupérer le message de son choix à partir de la base de données répliquée sans révéler l'index du message à aucun serveur et sans révéler aucune information sur les autres messages à l'utilisateur. Le document se concentre sur le cas où le aléa commun nécessaire au côté serveur pour réaliser le SPIR est également répliqué aux serveurs selon le graph. Cela introduit une contrainte de confidentialité supplémentaire, car l'aléa est maintenant associé au message par le biais de la réplique partagée. Les principales contributions du document sont : 1. Le document établit une borne inférieure sur la capacité SPIR, c'est-à-dire la vitesse de téléchargement maximale, pour les graphes généraux en proposant un schéma SPIR réalisable. 2. Le document prouve que, pour que tout schéma SPIR soit réalisable, la taille minimale de l'aléa spécifique au message doit être égale à la taille du message. 3. Le document fournit des bornes supérieures correspondantes et dérive la capacité SPIR exacte pour la classe des graphes en chemin et réguliers. Le document présente un schéma permettant d'atteindre une vitesse de N1 pour tout graphique avec N sommets. Le schéma est montré être de capacité atteignable pour la classe des graphes réguliers (où d désigne le degré de chaque sommet) et en chemin par la déduction de bornes supérieures correspondantes. Pour ces classes de graphes, le document trouve que la contrainte supplémentaire de confidentialité de la base de données ne nuit pas à la capacité SPIR de plus de la moitié. Le document discute également de l'impact de l'intégration de la contrainte de confidentialité de la base de données sur la capacité SPIR et fournit des exemples de l'application du schéma à diverses structures de graphes, démontrant son efficacité et son application. En résumé, le document contribue au domaine du SPIR en introduisant une formulation nouvelle pour les bases de données répliquées, en fournissant des bornes théoriques sur la capacité SPIR, et en proposant un schéma pratique permettant d'atteindre des vitesses quasi-optimales. Les résultats présentés dans le document ont le potentiel d'améliorer l'efficacité et la confidentialité des systèmes SPIR dans diverses applications, telles que la recherche de données sécurisées et le stockage distribué.