Privacy-Preserving Top-K Nearest Keyword Search Queryies over Encrypted Graph Data

Under the cloud storage and cloud computing environment, searchable encryption has been extensively studied over the past years. However, most searchable encryption schemes are focusing on solving keyword search queries over encrypted textual data, and there only exists very few searchable encryption schemes that support top-k nearest keyword search queries for graph structured data. The top-k nearest keyword search is a wildly used query type in many application areas, such as social network and web graphs. Given a graph, a top-k nearest keyword search query can return the k nearest neighbors of the querying vertex with a specific keyword. The existing scheme uses 2-hop labeling and order-preserving encryption to achieve shortest distance computations over encrypted graphs. However, the scheme cannot return the distance between the querying vertex and the k nearest neighbors in the query result. This work solves the above problem using homomorphic encryption and secure integer comparison protocol, and propose a graph encryption scheme supporting top-k nearest keyword search. We provide detailed security analysis for the proposed scheme, and prove that the scheme achieves CQA2 security.