Spidey: Secure Dynamic Encrypted Property Graph Search With Lightweight Access Control
Yingying Wu, Jiabei Wang, Dandan Xu, Yongbin Zhou · IEEE Internet of Things Journal · 2024
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 schemeDGraphsupports efficient, fine-grained sublinear queries and updates with the complexity of both attribute-grained update and node-grained deletion being$\mathcal {O}(1)$, while ensuring both forward privacy (FP) and backward privacy (BP). Two enhanced schemes$\mathtt {DGraph\_RW}$and$\mathtt {DGraph\_Role}$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,DGraphis$2.5\times $faster than ODXT (by Patranabis and Mukhopadhyay), and for node-grained deletion, with each node associated with 12 attributes,DGraphis$30\times $faster than ODXT.