Privacy-preserving graph similarity search with attribute-based access control

Abstract Graph-structured data are integral to applications like social networks, biological systems, cybersecurity, and fraud detection. Outsourcing these data to public clouds offers scalability but raises privacy concerns, as encryption is required before outsourcing, making traditional graph similarity search and access control challenging. This paper presents a novel solution for privacy-preserving full graph similarity search with fine-grained access control in cloud environments. To the best of our knowledge, this is the first work to integrate privacy-preserving graph similarity search in a multi-user/multi-query setting with attribute-based access control (ABAC). This enables scalable and secure access in realistic, collaborative environments. The graph owner leverages the neural Graph2vec model to create feature indexes for encrypted graph data. Simultaneously, a secure transfer learning mechanism enables graph users to generate query feature indexes in the same latent space, ensuring privacy while accurately capturing the user’s query intent. ABAC is employed to enforce flexible, fine-grained access policies. We conduct a formal security analysis under known-ciphertext and known-background threat models, demonstrating strong privacy guarantees. Experimental evaluations on real-world datasets show that our scheme achieves high semantic accuracy, lower search latency, and reduced storage overhead, outperforming existing approaches.