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.
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 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:
- SQ1 (Publicly Verifiable): Uses a bilinear map-based accumulator, allowing any entity with a public verification key to check the results.
- 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