Privacy-Preserving Approximate Top-k Nearest Keyword Queries over Encrypted Graphs

With the prosperity of graph-based applications, it is increasingly popular for graph nodes to have labels in terms of a set of keywords. The top-k nearest keyword (k-NK) query can find a set of k nearest nodes containing a designated keyword to a given source node. In cloud computing era, graph owners prefer to outsource their graphs to cloud servers, leading to severe privacy risk for conducting k-NK queries. The current studies fail to support efficient and accurate k-NK query under the premise of privacy protection.In this paper, we propose a new graph encryption scheme Aton, which enables efficient and privacy-preserving k-NK querying. Based on the symmetric-key encryption and particular pseudo-random functions, we construct a secure k-NK query index. Aton is built on a ciphertext sum comparison scheme which can achieve approximate distance comparison with high accuracy. Rigorous security analysis proves that it is CQA-2 secure. Experiments with real-world datasets demonstrate that it can efficiently answer k-NK queries with more accurate results compared with the state-of-the-art.