Privacy-Preserving Hierarchical Top-k Nearest Keyword Search on Graphs

Graph search techniques are increasingly vital for applications involving labeled or textual content on network vertices. A key task is the top-k nearest keyword (kNK) search on undirected graphs where a query vertex and keywords identify k closest vertices containing the keywords. With cloud storage widely used for outsourcing graph services, ensuring data privacy and security is critical. Existing solutions employ encrypted indexes for privacy-preserving keyword searches but lack fine-grained access control, limiting their ability to accommodate diverse user needs. To address this, we propose privacy-preserving hierarchical top-k nearest keyword search on graphs (PH-kNK), a novel scheme enhancing privacy-preserving top-k keyword searches by integrating hierarchical access control. PH-kNK introduces hierarchical query entry indexes that regulate access at multiple security levels, significantly improving privacy, security and adaptability. The granular query entry indexes established by our approach enables users with higher security levels to query the graph structure and access corresponding vertices while maintaining transparency for lower-level users. The scheme leverages pseudo-random mapping, order-preserving encryption and re-encryption of search indexes to ensure robust data security. Experimental results on real-world datasets demonstrate the scheme’s high efficiency and validate its security.