Spidey: Secure Dynamic Encrypted Property Graph Search With Lightweight Access Control

Graph databases, which essentially store network nodes and edge relationships between them, offer a promising solution for managing the large and dynamic Internet of Things (IoT) network. However, as data grows explosively, end devices cannot carry it, forcing organizations to outsource storage to cloud servers, bringing privacy risks, such as data leakage. Existing privacy-preserving graph search schemes either fail to support secure and efficient multigranularity updates over encrypted complicated property graph or neglect multiuser access control, greatly limiting their practicability. In this article, we propose a novel dynamic encrypted property graph search system along with three full-fledged constructions, named Spidey. We model the property graph and introduce two well-designed structures: bidirectional index and delete list, which form the foundation of our schemes. The basic scheme <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DGraph</monospace> supports efficient, fine-grained sublinear queries and updates with the complexity of both attribute-grained update and node-grained deletion being <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(1)$ </tex-math></inline-formula>, while ensuring both forward privacy (FP) and backward privacy (BP). Two enhanced schemes <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt {DGraph\_RW}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathtt {DGraph\_Role}$ </tex-math></inline-formula> further incorporate lightweight operation-based and (hierarchical) role-based access control, respectively, while avoiding encrypted index expansion and minimizing the impact on search efficiency. Both theoretical comparison and experiment results demonstrate their usability and scalability. Notably, for attribute-grained update, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DGraph</monospace> is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2.5\times $ </tex-math></inline-formula> faster than ODXT (by Patranabis and Mukhopadhyay), and for node-grained deletion, with each node associated with 12 attributes, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DGraph</monospace> is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$30\times $ </tex-math></inline-formula> faster than ODXT.