SUGAR: SecUre GrAph QueRy Services*

[Abstract]

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]

  1. Choi Koon Kau (Byron) and Zhe Fan. Structure-Preserving Subgraph Queries. No. 62170122. Filed on 2 June 2015. (Provisional)

[Relevant Publications]

  1. J. Jiang, P. Yi, B. Choi, Z. Zhang, X. Yu. "Privacy-Preserving Reachability Query Services for Massive Networks". ACM International Conference on Information and Knowledge Management (CIKM). 2016, pages 145-154. [pdf]
  2. Z. Fan, B. Choi, Q. Chen, J. Xu and S. Bhowmick. "Structure-Preserving Subgraph Isomorphism Query Services". IEEE Transactions on Knowledge and Data Engineering (TKDE). 2015. [pdf]
  3. Z. Fan, B. Choi, J. Xu and S. Bhowmick. "Asymmetric Structure-Preserving Subgraph Queries for Large Graphs". IEEE International Conference on Data Engineering (ICDE). 2015. [pdf]
  4. Y. Peng, Z. Fan, B. Choi, J. Xu and S. Bhowmick. "Authenticated Subgraph Similarity Search in Outsourced Graph Databases". IEEE Transactions on Knowledge and Data Engineering (TKDE). 2014. [pdf]
  5. P. Yi, Z. Fan, and S. Yin. "Privacy-Preserving Reachability Query Services for Sparse Graph". IEEE International Conference on Data Engineering (ICDE GDM Workshop) . 2014. [pdf]
  6. S. Yin, Z. Fan, P. Yi, B. Choi, J. Xu and S. Zhou. "Privacy-Preserving Reachability Query Services". International Conference on Database Systems for Advanced Applications (DASFAA). 2014. [pdf]
  7. Z. Fan, Y. Peng, B. Choi, J. Xu and S. Bhowmick. "Towards Efficient Authenticated Subgraph Query Service in Outsourced Graph Databases". IEEE Transactions on Services Computing (TSC). 2013. [pdf]

[Implementation]

  1. Download here!

* 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

For further information, please contact Zhe Fan, Byron Choi, Sourav S Bhowmick or Jianliang Xu.

Created on 17th March 2015.