Verifiable Subgraph Matching With Cryptographic Accumulators in Cloud Computing

Yixiao Zhu, Hui Li, Jiangtao Cui, Yong MaIEEE Access 2019 · OpenReview

Abstract

Due to the rapid development of social networks, bio-informatics, and the Internet-of-Things, subgraph matching queries have become essential across various applications. As data graphs grow in scale, outsourcing query processing to remote Cloud Service Providers (CSPs) has become common practice. However, the integrity of results in this scenario is not guaranteed, as a CSP may be malicious, compromised, or prone to software errors. Existing generic verifiable computation (VC) schemes are often too impractical for real-world implementation due to high computational costs and significant local storage requirements. This paper proposes both public and designated verification schemes tailored for subgraph matching. By utilizing a modified cryptographic accumulator, the framework achieves fast verification, low local storage overhead, and supports dynamic graph updates. Rigorous security proofs and efficiency analyses demonstrate that the proposed schemes are secure and satisfy the requirements of general VC protocols.

Introduction

Subgraph matching—the process of finding all instances of a small query graph within a larger data graph—is a fundamental task in modern data analysis. Because these data graphs are often massive, clients frequently outsource storage and computation to the cloud. However, Cloud Service Providers are not always "honest-but-curious"; they may omit edges to reduce search costs or return partial results due to unintended system bugs.

Example of a data graph G and a query graph Q used in subgraph matching.

Traditional Verifiable Computation (VC) methods, such as those based on Fully Homomorphic Encryption, are mathematically robust but computationally heavy, making them impractical for large-scale graph processing. Furthermore, many existing schemes require clients to store significant auxiliary data locally. This research introduces a novel framework that leverages cryptographic accumulators to provide a lightweight, verifiable solution for outsourced graph data.

System Framework and Methodology

The proposed framework involves three primary entities: the Data Owner, the Cloud Service Provider (CSP), and the Authenticated User. The Data Owner commits the graph's edges into a compact cryptographic value before outsourcing the data to the CSP.

The system model for verifiable subgraph matching, illustrating the exchange of keys, query results, and cryptographic witnesses.

The core innovation is the application of Cryptographic Accumulators, which compress a large set of elements into a single, constant-size value. The authors propose two main constructions:

  1. SQ1 (Publicly Verifiable): Uses a bilinear map-based accumulator, allowing any entity with a public verification key to check the results.
  2. SQ2 (Designated Verifier): A more restrictive version where only authorized clients with a secret key can perform verification.

When a user submits a query, the CSP returns the matching subgraphs along with a "witness"—a cryptographic proof that the edges in the result exist in the original accumulated set. The user then verifies this witness against a tiny local accumulator value (typically 128 bytes). The system also supports Dynamic Updates (DQ), allowing for the addition or deletion of edges without a full re-computation of security parameters.

Experimental Evaluation and Results

The performance of the proposed schemes was evaluated using simulated graphs with edge counts ranging from 1,000 to 10,000 on a standard workstation (Intel Xeon E5-1650, 256GB RAM).

  • Verification Efficiency: In the SQ1 scheme, it takes approximately 2.5ms to verify a single edge in the result graph, while SQ2 takes roughly 3.9ms. This allows clients to verify hundreds of results per second.
  • Storage Savings: While traditional schemes might require $O(n^2)$ local space, SQ1 requires only a constant 128 bytes. Even the more complex SQ2 scheme requires only about 19.58 KB for a graph with 10,000 edges.
  • Update Speed: For dynamic graphs, updating the local accumulator value after an edge modification takes only 0.01ms.

The security of the scheme is mathematically grounded in the Square Computational Diffie-Hellman (Square-CDH) assumption, ensuring robust protection against malicious CSPs.

Conclusion and Future Work

This paper presents a tailored VC framework that significantly reduces the overhead associated with verifiable subgraph matching. By focusing on edge membership through cryptographic accumulators, the authors provide a practical solution for cloud-based graph processing. Future research will explore extending the framework to support isolated vertices and implementing privacy-preserving mechanisms to protect the content of the graph data from the CSP.

Summary updated

Abstract

Due to the rapid development of social networks, bio-informatics, internet-of-things etc., subgraph matching query can be found in various applications. Meanwhile, the increasing popularity of storing graph data in the cloud drives demands for graph query processing on a remote cloud server. However, the query results in this scenario may not be guaranteed to be correct, especially when the cloud service provider (CSP) is malicious or compromised by some adversaries, for example, a CSP might omit some edges of the graph so that its search cost would be substantially reduced. Besides, various software bugs and unintended errors are also inevitable. All current generic verifiable computation (VC) schemes applied in this scenario are not only too impractical to be implemented but also need a lot of space to locally store their auxiliary data. To that end, we have put forth both public and designated verification schemes which focus on subgraph matching problems for outsourced graph data. They utilize a modified cryptographic primitive called accumulator to realize fast verification and low local storage overhead. In addition to the two main constructions, we have proposed an optimization to make the scheme more applicable, namely, supporting dynamic updates of the graph. At last, rigorous security proofs and efficiency analysis are given, which justify that our proposed schemes are secure and efficient, satisfying the requirements of general verifiable computation protocols.
BibTeX
@inproceedings{zhu2019verifiable,
  author = {Yixiao Zhu and Hui Li and Jiangtao Cui and Yong Ma},
  title = {{Verifiable Subgraph Matching With Cryptographic Accumulators in Cloud Computing}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=cW6YArfKKW},
}
Figure