Résumé technique : SPIDER et baseSPIDER

Énoncé du problème

L'article aborde le défi du déploiement de la récupération d'information privée (PIR) dans deux environnements web distincts mais critiques :

1. Passage à l'échelle pour les grandes entrées : Les serveurs web modernes servent des objets massifs (images, vidéos, grands enregistrements). Les schémas PIR à serveur unique et à état existants souffrent souvent de facteurs constants élevés dans la communication et le calcul, qui deviennent prohibitifs lorsque les entrées de la base de données ($\beta$) sont grandes.
2. La contrainte du serveur par défaut : La plupart des schémas PIR à serveur unique récents et efficaces nécessitent un serveur « coopératif » effectuant des opérations spécifiques (par exemple, l'opération XOR des éléments récupérés) ou maintenant des métadonnées spécifiques à la PIR. Cependant, les services web réels (par exemple, Wikidata, les réseaux de diffusion de contenu standards) sont des serveurs « par défaut » : ils offrent uniquement un accès standard en lecture seule basé sur l'index, ne peuvent pas être modifiés et ne fournissent aucune API spécialisée. Les solutions PIR existantes ne peuvent pas fonctionner dans ce contexte non coopératif sans violer le modèle économique ou les contraintes techniques du serveur.

Méthodologie

L'article introduit deux protocoles : baseSPIDER (pour les serveurs coopératifs) et SPIDER (pour les serveurs par défaut). Tous deux reposent sur un client à état qui effectue une phase de prétraitement unique pour stocker des « indices » en vue de futures requêtes.

1. Mécanisme central : Indices basés sur les multisets

Contrairement aux travaux antérieurs (par exemple, PIANO, RMS) qui partitionnent la base de données en fragments, baseSPIDER et SPIDER utilisent une nouvelle construction d'indices basée sur les multisets.

• Génération d'indices : Lors du prétraitement, le client échantillonne $m$ indices. Chaque indice est un multiset de $k \approx \sqrt{n}$ indices sélectionnés uniformément au hasard parmi tous les multisets possibles de taille $\sqrt{n}$ sur une base de données de taille $n$.
• Stockage compact : Au lieu de stocker la liste complète des indices, le client stocke une graine de 64 bits et le résultat précalculé de l'opération XOR des entrées de la base de données correspondantes. La graine permet la reconstruction déterministe du multiset via une bijection « étoiles et barres ».
• Propriété de masquage : L'idée clé est que si un multiset choisi uniformément a un élément retiré (masqué), le $(k-1)$-multiset restant est distribué uniformément et indépendamment de l'élément retiré. Cela garantit que le serveur ne peut pas distinguer quel élément était la cible de la requête.

2. baseSPIDER (Serveur coopératif)

• Fonctionnement : Le client sélectionne un indice contenant l'index cible $i$, le « masque » en retirant $i$ du multiset, et envoie les $k-1$ indices restants au serveur.
• Rôle du serveur : Le serveur calcule le XOR des entrées à ces $k-1$ indices et renvoie une seule valeur.
• Récupération : Le client effectue l'opération XOR entre la réponse du serveur et l'indice stocké (qui contient le XOR de toutes les $k$ entrées) pour récupérer l'entrée cible $i$.
• Ravitaillement des indices : Pour empêcher le serveur de déduire les modèles d'accès au fil du temps, les indices utilisés sont jetés. Le client maintient un pool d'indices et utilise une stratégie de remplacement (échangeant un index utilisé contre un indice survivant aléatoire) pour maintenir la couverture sans biais.

3. SPIDER (Serveur par défaut)

• Transformation : SPIDER adapte baseSPIDER pour ne nécessiter aucun calcul côté serveur au-delà de la récupération standard.
• Fonctionnement : Au lieu de demander au serveur d'effectuer l'opération XOR sur les entrées, le client demande les entrées brutes correspondant aux indices masqués.
• Rôle du client : Le client effectue l'opération XOR localement.
• Actualisation continue : Comme le client télécharge $k-1$ entrées par requête, il peut utiliser ces entrées brutes pour construire de nouveaux indices en arrière-plan, permettant des requêtes continues sans phase de prétraitement distincte et lourde.

Contributions clés

1. Communication optimisée pour les grandes entrées (baseSPIDER) :

   • baseSPIDER atteint la complexité de communication asymptotiquement optimale de $\tilde{O}(\sqrt{n} \cdot \beta)$ tout en améliorant les facteurs constants.
   • Il réduit la communication par requête de $2 \cdot \beta$ (dans l'état de l'art RMS-24) à exactement $1 \cdot \beta$. C'est une amélioration pratique significative pour les bases de données avec de grandes entrées.
   • Il offre une conception conceptuellement plus simple par rapport aux approches antérieures basées sur le fractionnement.

2. Première PIR à serveur unique pour les serveurs par défaut (SPIDER) :

   • SPIDER est la première construction à réaliser la confidentialité PIR sur un serveur n'effectuant aucune opération spécifique à la PIR et ne maintenant aucun état spécifique à la PIR.
   • Il ne nécessite que des API de récupération indexée standard.
   • Bien qu'il entraîne un calcul client plus élevé (XOR de $\sqrt{n}$ entrées) et un téléchargement par requête plus élevé ($\sqrt{n} \cdot \beta$), il permet la PIR sur l'infrastructure web existante et non modifiée.

3. Transformation générale :

   • L'article démontre que la transformation d'un contexte coopératif vers un contexte de serveur par défaut peut être appliquée largement à d'autres schémas PIR récents (PIANO-23/24, RMS-24, WR-25), les adaptant au paradigme du serveur par défaut.

Résultats et évaluation

• Analyse de complexité :
  • Communication : baseSPIDER atteint $1 \cdot \beta$ par requête (amorti $\sqrt{n} \cdot \beta$). SPIDER atteint $\sqrt{n} \cdot \beta$ par requête (amorti $\sqrt{n} \cdot \beta$).
  • Stockage : Le stockage client est de $O(\sqrt{n} \cdot \log n \cdot \beta)$ pour les deux schémas.
  • Calcul : Le calcul serveur est de $O(\sqrt{n})$ par requête (dominé par les E/S). Le calcul client implique $O(\sqrt{n})$ opérations XOR par requête dans SPIDER.
• Résultats expérimentaux :
  • Dans le contexte coopératif, baseSPIDER surpasse RMS-24 en latence de bout en bout, en particulier à mesure que la taille de l'entrée ($\beta$) augmente, en raison de la réduction de moitié du trafic réseau.
  • La latence de recherche d'indices (scan linéaire) est un goulot d'étranglement pour les petites entrées, mais devient négligeable par rapport à la latence réseau et aux E/S pour les grandes entrées.
  • SPIDER a été intégré avec succès à Wikidata, démontrant que le schéma fonctionne sur un point de terminaison SPARQL réel et non coopératif sans modifier le serveur.

Importance et affirmations

L'article affirme que SPIDER et baseSPIDER répondent aux deux principaux obstacles restants au déploiement pratique de la PIR sur le web ouvert :

1. Performance : En améliorant les facteurs constants, baseSPIDER rend la PIR viable pour la récupération de données à grande échelle où la bande passante est une contrainte critique.
2. Déployabilité : En éliminant le besoin de coopération du serveur, SPIDER permet une récupération respectueuse de la vie privée sur le web « par défaut », où les serveurs sont non coopératifs et ne peuvent pas être modifiés.

Les auteurs notent que, bien que SPIDER fasse un compromis sur la communication optimale par requête pour la compatibilité serveur, il permet des « requêtes continues et ininterrompues » en exploitant les données téléchargées pour le ravitaillement des indices. Ce travail établit qu'une récupération privée et performante est possible même sous les contraintes les plus strictes du web moderne, à condition que le client soit à état et dispose de la volonté d'effectuer un calcul local supplémentaire.