Privacy preserving 2-party queries on bipartite graphs with private set intersection
Sara Ramezanian, Tommi Meskanen, Valtteri Niemi · 2019
In this paper, we study the problem of privately querying a directed bipartite graph. We motivate the problem by a real life scenario where the graph is constructed from a trust relation database, that can be illustrated as a directed graph. We assume that the graph of trust relations has two parts with two owners, A and B. We present a novel protocol that utilizes Private Set Intersection protocol, to privately query such a graph. The goal of our protocol is to determine, whether there is a path from node a (belonging to A) to node b (belonging to B), in a privacy preserving manner. We also present a private set intersection protocol to determine whether the set intersection is non-empty.