L’audit révèle des violations de confidentialité dans le code PrivDPR testé
En termes simples
Cet article propose une façon de vérifier si un système qui publie des graphes tient sa promesse de confidentialité. Un auditeur choisit deux graphes d’entrée qui diffèrent par les connexions d’un sommet, puis examine des caractéristiques comme le nombre d’arêtes pour voir si les sorties révèlent cette différence.
À partir du nombre d’arêtes, les auteurs ont certifié statistiquement des violations pour six paires de graphes testées avec le code PrivDPR publié. Cela révèle un défaut dans cette implémentation, pas dans tous les systèmes de confidentialité pour les graphes.
La recherche
Lorsqu’un mécanisme de publication de graphes affirme que ses sorties protègent les changements touchant un sommet, comment un auditeur peut-il vérifier cette affirmation si une modification locale peut affecter de nombreuses structures liées ?
La réponse dépend des graphes voisins comparés et des caractéristiques des graphes publiés examinées.
Les auteurs séparent le choix des paires de graphes voisins de celui des statistiques de sortie, puis vérifient statistiquement si les graphes publiés contredisent la revendication de confidentialité d’un mécanisme.
Lorsqu’un mécanisme de confidentialité publie un réseau, une petite modification de l’entrée peut affecter de nombreuses structures liées. Les auditeurs doivent donc choisir à la fois les graphes voisins à comparer et les caractéristiques des sorties susceptibles de révéler une différence.
Les auteurs ont testé leur implémentation publiée de PrivDPR sur six paires de ce type.
Avec le nombre d’arêtes, ils ont certifié statistiquement une violation du niveau de confidentialité revendiqué, ε=0.1 avec δ=10⁻⁵, pour chaque paire, avec un niveau de confiance de 99 % par test ; cela réfute la revendication pour cette implémentation.
L’étude de cas porte sur un seul mécanisme de confidentialité pour les graphes et ne mesure pas systématiquement l’effet de la structure des canaries sur la capacité de détection de l’audit.
Comme la méthode ne teste que certaines paires et statistiques, un audit qui ne détecte aucune violation ne permet pas de conclure et ne peut pas certifier la confidentialité.
Analyse
Détails
- Auteurs de l’article original
- Nicholas D'Silva, Surya Nepal, Salil S. Kanhere
- Soumis à arXiv
- Licence
- arXiv non-exclusive