Privacy-preserving Reachability Query Services

Due to the massive volume of graph data from a wide range of recent appli-cations, such as social network, bioinformatics and XML data. At the same time, much more efficient and powerful resources required to process numerous queries. It is becoming economically appealing to outsource graph data to a third-party service provider (SP) to provide query services. However, SP cannot always be trusted. Hence, data owners and query clients may prefer not to expose their data graphs and queries.Reachiablity query is one of the most fundamental query in database area. This paper studies privacy-preserving query services for reachability query where both clients’queries and the structural information of the owner’s data are pro-tected. According to different types of graph data, we propose two different index method base on 2-hop labeling, named privacy-preserving 2-hop labeling (pp-2-hop) and privacy-preserving minimum unified intesection 2-hop (ppm-2-hop). In these two methods, the reachability queries are computed in an encrypted domain and the input and output sizes of any queries are indistinguishable. We analyze the security of these two method with respect to ciphertext only and size based at-tacks. We verify the performance of pp-2-hop and ppm-2-hop with an experimental study on both synthetic and real-world datasets.