Summary: Protect Edge Privacy in Path Publishing with Differential Privacy

Authors: Zhigang Lu and Hong Shen, in arXiv:2001.01825v1,
January 2020

The summary below was automatically created by Flexudy. Feel free to download the app from your Google Play Store or Apple App Store.

Have fun reading

Differentially private trajectory publishing concerns publishing path information that is usable to the genuine users yet secure against adversaries to reconstruct the path with maximum background knowledge. The exiting studies all assume this knowledge to be all but one vertex on the path, i.e., the adversaries have the knowledge of the network topology and the path but one missing vertex (and its two connected edges) on the path. To prevent the adversaries recovering the missing information, they publish a perturbed path where each vertex is sampled from a pre-defined set with differential privacy (DP) to replace the corresponding vertex in the original path. Under such assumption, the perturbed path produced by the existing work is vulnerable, because the adversary can reconstruct the missing edge from the existence of an edge in the perturbed path whose two ends are close to the two ends of the missing edge. To address this vulnerability and effectively protect edge privacy, instead of publishing a perturbed path, we propose a novel scheme of graph-based path publishing to protect the original path by embedding the path in a graph that contains fake edges and replicated vertices applying the differential privacy technique, such that only the legitimate users who have the full knowledge of the network topology are able to recover the exact vertices and edges of the original path with high probability. We also conduct extensive experimental evaluations on a high-performance cluster system to validate our analytical results. Introduction Paths are pervasive in our daily life, such as, geometric trajectory, internet traffic flow, supply chain, and intelligence exchange network [10, 11]. Publishing a path helps the owners of the path discover more knowledge about the path and obtain the information about their roles on the path. In this scenario, N is a service system of an organisation; V is the set of service suppliers; E is the set of resource transfer links; P is a supply chain; path publishing is the way to ensure every supplier knows how resources are transferred; ”adversaries” are competing organisations which want to know how the target organisation allocates the resources. In this scenario, N is a spy network; V is the set of spies; E is the set of spy communication channels; P is the message exchange path; path publishing is the way to let all spies know whom should be contacted with; ”adversaries” are counter-intelligence units who want to know how a targeted spy exchanges information with others. In a nutshell, existing studies in the differentially private trajectory publishing share a similar idea in two-fold. Specifically, the published trajectory contains fake locations only, which are sampled via ExpDP from a predefined area, to replace the real ones in the target trajectory. In this case, the published (perturbed, privacy-preserved) path by the existing work is vulnerable to preserve the existence of an arbitrary edge of the original path, because the adversary can reconstruct the missing edge by the existence of an edge in the perturbed path whose two ends are close to the two ends of the missing edge. A Running Attack against the Existing Algorithms of Differentially Private Trajectory Publishing To fill the research gap, this paper studies how to protect an arbitrary edge in path publishing. We address the problem of differentially private path publishing in a generalised form against inference attacks from adversaries with more background knowledge than the existing 2 work. In a nutshell, we propose a graph-based path publishing which uses the topology of the original network and the connections between vertices of the path to conceal the edge existence against the adversaries who do not have full knowledge about the edges in the given network. For the edge e = (u, v) ∈ E \\EP , vertex u and v are placed in a same branch in the graph-based path; In this paper, all the unique vertices in the given network N are the base vertices; and all the repeated visited vertices in the path P and the duplicate vertices created by DP are sub-vertices. To overcome the bad placement(s), we record each inserted vertex in a stack. When we have a vertex with an empty possible layers set, the stack enables us to backtrack and reinsert the recently inserted vertices until we can successfully insert all the vertices into the graph. The graph-based path exists, unless ∃u ∈ P , that u breaks the transitive relation in all possible topology of GP . Namely, to insert a vertex u to a GP , after trying all the possible layers of each vertex in the present GP by backtracking the stack in Algorithm 4, we cannot find a good layer to insert u. Note that, the splitting operation in Algorithm 6 is different to the differentially private vertices preprocessing in Algorithm 1. Run Time Figure 7 depicts the run time of our algorithm with acyclic paths over different sizes of the maps and different settings of differential privacy on either vertices or edges. In Figure 8, we study the performance of our graph-based path without both DP injection and the splitting strategy (as Algorithm 6) for different sizes of maps with acyclic path. To evaluate the performance of our algorithm on acyclic paths in the worst case, according to Figure 8a, we select the maps produce the graph-based paths with the minimum opportunity for each a given number of vertices in Figure 9.”

Did you enjoy reading? Follow us on Medium and give us feedback to help us improve our Summarizer.