Constrained top-k nearest fuzzy keyword queries on encrypted graph in road network

Abstract With the gradual growth of road networks, the graphs used to represent road networks have been becoming larger and larger. It is a preferable choice for the user to outsource large-scale graphs for road networks to cloud and allow the cloud to store and query the information from graphs for him. It improves query efficiency greatly and reduces the user’s burden remarkably. To protect the privacy of graph data, the user has to encrypt the graph before uploading it to the cloud. It makes performing query on the encrypted graph become a challenge. In this paper, we propose the first scheme for performing a constrained top- k nearest keyword query on an encrypted graph, even if a typo is made by the user. In the proposed scheme, we construct a new index structure based on the 2-hop cover label index to calculate the constrained shortest distance. In order to support fuzzy keyword query, we generate the fuzzy keyword set to build the keyword index in the graph. The security analysis shows the proposed scheme satisfies CQA-security and the experiments demonstrate the proposed scheme is efficient.