Design of efficient and privacy-preserving query over graph data
Loading...
Date
2023-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of New Brunswick
Abstract
The widespread adoption of the Internet of Things (IoT) has resulted in a vast amount of graph data representing relationships between entities in various applications. As data quantities continue to grow exponentially, data owners are outsourcing their data and services to the cloud to alleviate local storage and computation burdens. However, this outsourcing raises privacy concerns regarding graph datasets and services. Although some schemes were proposed to mitigate privacy issues in graph query services through cryptography and/or anonymization techniques, they cannot simultaneously achieve query privacy, accurate graph queries, and strong privacy preservation for graph datasets. This dissertation focuses on community queries and subgraph matching queries and proposes several efficient and privacy-preserving graph query schemes for different scenarios:
i) Designing a privacy-preserving (α, β)-core query scheme for encrypted bipartite graphs, which utilizes a table-based index to secure the traversal of an encrypted bipartite graph, achieving strong privacy preservation for both the graph and user queries.
ii) Designing a privacy-preserving k-truss community query scheme for outsourced graph datasets, which employs a secure intersection protocol for outsourced sets and stream cipher scheme to reduce computation and storage overhead, improving performance.
iii) Designing a privacy-preserving subgraph matching aggregation query scheme, which includes an iterative algorithm that efficiently extracts subgraphs that closely resemble a user-specified pattern. The underlying homomorphic encryption scheme enables support for a wide range of aggregation functions.
iv) Designing a privacy-preserving aggregate query scheme for public property graphs: By employing function secret sharing and additive secret sharing techniques, this scheme facilitates an efficient and privacy-preserving aggregate query protocol be tween cloud servers holding replicas of the public property graph.
v) Designing a privacy-preserving subgraph matching query scheme for graph federation: In this scheme, data owners collaborate to compute an index, enabling efficient execution of user queries without compromising the privacy of graph datasets and queries.
The dissertation includes a comprehensive analysis of the security of the proposed schemes and extensive experiments to validate their efficiency. The results demonstrate that all schemes are privacy-preserving, protecting datasets and query requests against cloud servers, while also being computationally efficient.