SecGraph: Towards SGX-based Efficient and Confidentiality-Preserving Graph Search

Qiuhao Wang, Yang Xu, Saiyu Qi, Yong QiarXiv 2024 · DOI · arXiv

TL;DR

SecGraph leverages Intel SGX to transform encrypted graph search from a slow, static process into a high-performance, dynamic system. By moving critical operations into a hardware-secured enclave, it achieves up to a 208x improvement in search speed and a 540x reduction in communication overhead compared to previous state-of-the-art methods.

What Problem Does This Paper Address?

As graph data (like social networks or biological databases) grows in scale, organizations increasingly outsource storage and search to third-party cloud providers. However, these providers are often "honest-but-curious," meaning they might snoop on sensitive user connections or interests.

Existing solutions like PeGraph use a technique called Oblivious Cross-Tags (OXT) to allow searching over encrypted data. While secure, OXT-based methods face three major hurdles:

  1. High Communication Latency: They require multiple round-trips between the client and the server to generate search tokens.
  2. Heavy Computation: They rely on expensive modular exponentiation operations to verify if an edge exists in the graph.
  3. Static Nature: Most OXT schemes are designed for static datasets; adding or deleting a "friendship" or "connection" in an encrypted graph is notoriously difficult and inefficient.

Methods

The authors introduce SecGraph, which utilizes Intel SGX (Software Guard Extensions)—a hardware-based "enclave" that protects data even from the server's own operating system—to act as a trusted proxy.

Key technical innovations include:

  • Proxy-Token Generation: Instead of the client managing complex multi-step token exchanges, the client sends search keywords to the SGX enclave via a secure channel. The enclave then generates the necessary tokens locally, reducing the search process to a single round-trip.
  • LDCF-encoded XSet: To avoid slow math (modular exponentiation), SecGraph uses a Logarithmic Dynamic Cuckoo Filter (LDCF) inside the enclave. This turns a heavy cryptographic check into a lightning-fast membership test. Because the enclave has limited memory (128MB), the LDCF structure is designed to load only necessary "sub-filters" on demand.
  • Twin-TSet: To support dynamic updates, the authors designed a dual-map structure. It tracks relationships and update counts privately within the enclave, allowing for secure insertions and deletions without rebuilding the entire index.
  • Optimizations: They further propose SecGraph-G (grouping fingerprints to reduce memory swaps) and SecGraph-P (parallelizing membership checks) to squeeze even more performance out of the hardware.

Datasets

The researchers evaluated SecGraph using three real-world datasets from the Stanford Large Network Dataset Collection (SNAP):

  • Email (Enron): A friendship network with ~36k nodes and 183k edges.
  • Youtube: A social network with ~1.1M nodes and 2.9M edges.
  • Gplus (Google+): A massive sharing network with ~107k nodes and 13.6M edges.

Key Insights and Ideas

  • Hardware as a Performance Catalyst: The "aha moment" here is that SGX isn't just for security; it's a performance tool. By creating a "trusted" space on the server, you can use faster, non-cryptographic algorithms (like Cuckoo Filters) on sensitive data that would otherwise require slow "blinded" math.
  • Communication is the Real Killer: In cloud environments, the time spent sending data back and forth often outweighs the time spent processing it. Reducing the protocol from two round-trips to one is a primary driver of SecGraph's efficiency.
  • The Memory Swap Trap: The authors recognized that SGX's 128MB memory limit is a bottleneck. Their use of LDCF is specifically tailored to handle large graphs by only bringing small, relevant chunks of the index into the protected memory at any given time.

Key Results

The experimental results demonstrate a massive leap over the previous state-of-the-art (PeGraph):

  • Search Speed: SecGraph is up to 208x faster than PeGraph in standard configurations. With parallelization (SecGraph-P), this improvement jumps to over 3,300x.
  • Communication Efficiency: The communication cost in PeGraph is up to 540x larger than in SecGraph, thanks to the proxy-token method.
  • Update Performance: SecGraph can construct an encrypted database up to 58x faster than PeGraph and supports individual insertions/deletions in less than a millisecond (approx. 0.36ms).

Limitations and Future Work

  • Side-Channel Attacks: While SGX provides strong isolation, it is famously susceptible to certain side-channel attacks (like cache-timing attacks). The authors explicitly state that defending against these is outside the scope of this specific paper.
  • Query Complexity: The current system focuses on conjunctive search (finding common neighbors). The authors suggest that future work should expand this to more complex operations like range searches and full boolean logic.
  • Hardware Dependency: The system is tied to Intel SGX. While widely available, it limits the scheme to specific hardware ecosystems. Expanding to other Trusted Execution Environments (TEEs) like ARM TrustZone or AMD SEV could be a future direction.

Summary updated

Abstract

Graphs have more expressive power and are widely researched in various search demand scenarios, compared with traditional relational and XML models. Today, many graph search services have been deployed on a third-party server, which can alleviate users from the burdens of maintaining large-scale graphs and huge computation costs. Nevertheless, outsourcing graph search services to the third-party server may invade users' privacy. PeGraph was recently proposed to achieve the encrypted search over the social graph. The main idea of PeGraph is to maintain two data structures XSet and TSet motivated by the OXT technology to support encrypted conductive search. However, PeGraph still has some limitations. First, PeGraph suffers from high communication and computation costs in search operations. Second, PeGraph cannot support encrypted search over dynamic graphs. In this paper, we propose an SGX-based efficient and confidentiality-preserving graph search scheme SecGraph that can support insertion and deletion operations. We first design a new proxy-token generation method to reduce the communication cost. Then, we design an LDCF-encoded XSet based on the Logarithmic Dynamic Cuckoo Filter to reduce the computation cost. Finally, we design a new dynamic version of TSet named Twin-TSet to enable encrypted search over dynamic graphs. We have demonstrated the confidentiality preservation property of SecGraph through rigorous security analysis. Experiment results show that SecGraph yields up to 208x improvement in search time compared with PeGraph and the communication cost in PeGraph is up to 540x larger than that in SecGraph.
BibTeX
@misc{wang2024secgraph,
  author = {Qiuhao Wang and Yang Xu and Saiyu Qi and Yong Qi},
  title = {{SecGraph: Towards SGX-based Efficient and Confidentiality-Preserving Graph Search}},
  year = {2024},
  eprint = {2403.19531},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.19531},
}
Figure