SUGAR: SecUre GrAph QueRy Services*
Graphs are powerful tools for a wide range of real applications, from biological and chemical databases, social networks, citation networks to information networks. Large graph data repositories have been consistently found in recent applications. Due to the high complexity of graph queries, e.g., subgraph query, and the lack of IT expertise, hosting efficient graph query services for the owners of graph data has been a technically challenging task. And hence, they may prefer to outsource their services to third-party service providers (SPs) for scalability, elasticity and performance.
Unfortunately, SPs may not always be trusted. Security, typically the confidentiality and integrity of the data, has been recognized as one of the critical attributes of Quality of Services (QoS). This directly influences the willingness of both data owners and query clients to use SP's services. To address these concerns, this project proposes techniques to support privacy-preserving and authenticated graph query services, respectively.
Confidentiality [1, 2, 4, 5]: To protect the privacy of query graphs and/or data graphs, specifically the topological structure (i.e., the adjacency matrices) of the graphs, this project proposes efficient privacy-preserving subgraph isomorphism query and reachability query. In particular, novel encryption schemes and algorithms were carefully designed by adopting classical cryptographic schemes and seminal query evaluation algorithms. Optimization strategies have been proposed to enhance performance. Moreover, the privacy analysis shows the security guarantees. Our experimental results show that the proposed techniques are efficient and the optimizations are effective.
Data Integrity [3, 6]: To ensure data integrity, this project proposes efficient authenticated subgraph isomorphism and similarity queries, to guarantee the correctness (soundness and the completeness) of query answers. Specifically, the project proposes several novel methods derived from classical verifiable data structures, in particular, Merkle Hash Tree (MHT). Several indexing techniques and properties are proposed to optimize authentication performance. Theoretical analysis and experiments show that the proposed algorithms guarantee data integrity and return the query answers correctly and efficiently.
[Relevant US Patent]
Choi Koon Kau (Byron) and Zhe Fan. Structure-Preserving Subgraph Queries. No. 62170122. Filed on 2 June 2015. (Provisional)
* This project is supported by the following grants:
Adaptive Filtering for Efficient Subgraph Isomorphism in Graph Databases
General Research Funds (GRF), HKBU210510
Trusted Subgraph Similarity Query Services
Faculty Research Grant FRG2/12-13/079
Structure-preserving Subgraph Query Services
Faculty Research Grant FRG2/13-14/073
Created on 17th March 2015.