Secure Shortest Path Search over Encrypted Graph Supporting Synonym Query in Cloud Computing

摘要

As cloud computing become popular, cloud outsourcing service has attracted widespread attention. Many data owners outsource amounts of graph data to the cloud for cost savings. As the cloud server may not be fully trusted, the outsourced graph data are usually encrypted before outsourcing to the cloud for the security. The shortest path search is a common query and has wide use in graph operations. The shortest path search supporting synonym query is a more general operation which takes the synonyms of the query vertices as new query tokens to perform the shortest path search and could improve the query range. As the outsourced graph data are stored on the cloud server in an encrypted form, the shortest path search supporting synonym query becomes a very challenging task. In this paper, we propose a solution to perform the shortest path search supporting synonym query over encrypted graph data in cloud computing (SPSQ). We use a stemming algorithm and an encryption mechanism to achieve shortest path search supporting synonym query. We formally prove the security of the proposed scheme. The experiment results with a real graph data set demonstrate the efficiency of our scheme.