In plain words
This paper introduces a way to check whether a graph release system keeps its privacy promise. An auditor chooses two input graphs that differ in one vertex’s connections, then checks features such as the number of edges to see whether the outputs reveal that change.
Using edge count, the authors found statistically certified violations in six tested graph pairs for the released PrivDPR code. This shows a flaw in that implementation, not in every graph privacy system.
The research
When a graph release mechanism claims that its outputs protect changes to one vertex, how can an auditor check that claim when a local change may affect many connected structures? The answer depends on which neighboring graphs are compared and which features of the released graphs are examined.
The authors separate the choice of neighboring graph pairs from output statistics, then statistically test whether released graphs contradict a mechanism’s privacy claim.
When a graph privacy mechanism releases a network, a small input change may affect many connected structures. Auditors therefore need to choose both neighboring graphs to compare and output features that could expose a difference.
The authors tested their released PrivDPR implementation on six such pairs. Using edge count, they found a statistically certified violation of its claimed ε=0.1 privacy level at δ=10⁻⁵ for every pair, with 99% confidence per test; this falsifies the claim for that implementation.
The case study covers one graph privacy mechanism and does not systematically measure how canary structure affects audit power. Because the method tests only selected pairs and statistics, an audit that finds no violation is inconclusive and cannot certify privacy.
Analysis
Deep
- Original paper authors
- Nicholas D'Silva, Surya Nepal, Salil S. Kanhere
- Submitted to arXiv
- License
- arXiv non-exclusive