PSDMQ: A Parallel Method for Shortest Distances Multi-Querying on Encrypted Graph

Searchable symmetric encryption (SSE) enables a client to outsource a set of encrypted data in the cloud and retain the ability to perform retrieval without revealing client's private information. Graph as an import data structure and shortest distance querying as a significant fundamental operations on graph, has been applied a lot in real-life. Although efficient SSE shortest distance querying on graph are known, previous solutions are highly sequential. This is mainly due to the fact that, currently, the method for querying shortest distance on encrypted is usually designed based on 2HCL, which requires the search algorithm to access a sequence of memory locations, each of which is unpredictable and stored at the previous location in the sequence. Motivated by advances in multi-core architectures, we construct a new parallized method for batch shortest distance multi-querying(PSDMQ) on encrypted graph-structured data. Our approach is highly parallel thus can significantly improve efficiency. Both theoretical analysis and experiments are provided. Experiments on 3 real-world data sets demonstrates the effectiveness of our proposed scheme.