The Circle Game: Scalable Private Membership Test Using Trusted Hardware

Sandeep Tamrakar, Jian Liu, Andrew Paverd, Jan-Erik Ekberg, Benny Pinkas, N. Asokan

TL;DR

The researchers propose a "carousel" design pattern for Private Membership Testing (PMT) that uses trusted hardware (TEEs) to protect user privacy. By continuously cycling an entire malware dictionary through a secure enclave, the system can answer thousands of simultaneous queries in a single pass, significantly outperforming traditional ORAM-based solutions in high-traffic cloud environments.

What Problem Does This Paper Address?

Cloud-based malware checking (like Google’s Verify Apps) creates a massive privacy risk: the service provider can see every application a user queries, allowing them to infer sensitive traits like age, religion, or relationship status.

While cryptographic solutions like Private Set Intersection (PSI) exist, they are computationally expensive and don't scale. Newer approaches using Oblivious RAM (ORAM) within Trusted Execution Environments (TEEs) like Intel SGX offer better performance for single queries but struggle with "batching." In a real-world scenario with millions of users, the $O(m \log n)$ cost of ORAM (where $m$ is the number of queries and $n$ is the dictionary size) becomes a bottleneck. The authors aim to find a PMT solution that prioritizes throughput—the ability to handle a high volume of simultaneous queries—without sacrificing privacy.

Methods

The authors introduce the Carousel Approach. Instead of the TEE fetching specific items from a database (which leaks access patterns), the untrusted server continuously "circles" the entire dictionary through the TEE.

Key technical components include:

  • Batch Processing: Queries are collected and held in the TEE for exactly one full carousel cycle. This ensures that the time taken to respond is independent of the query's value or its position in the dictionary.
  • Data Structures: To minimize the time it takes to "spin" the carousel, the authors evaluated three representations:
  • Sequence of Differences: Storing the gaps between sorted malware hashes to save space.
  • Bloom Filters: A probabilistic structure that is very fast but has higher memory overhead.
  • 4-ary Cuckoo Hashing: The most effective method, allowing for $O(m + n)$ processing time.
  • Hardware Implementation: The system was built and tested on both ARM TrustZone (common in mobile) and Intel SGX (common in servers).
  • Oblivious Memory Management: For Intel SGX, which lacks the "private memory" found in TrustZone, the authors implemented "oblivious pages" to prevent side-channel attacks from observing memory access patterns at the page level.

Datasets

The paper uses a synthetic dictionary modeled after real-world malware statistics:

  • Dictionary Size: $2^{26}$ entries (~67 million signatures), reflecting a 10-year growth estimate for mobile malware.
  • Query Load: Simulated query arrival rates ranging from 0 to over 4,000 queries per second.
  • False Positive Rate (FPR): Targeted at $2^{-10}$ (approx. 0.1%), a threshold deemed acceptable by anti-malware vendors because users can always perform a secondary, non-private check for positive hits.

Key Insights and Ideas

  • Throughput vs. Latency: While ORAM provides very low latency for a single query (milliseconds), it hits a "breakdown point" quickly under heavy load. The Carousel approach has higher baseline latency (around 1 second) but maintains that latency even as the number of simultaneous users grows significantly.
  • The Power of the Batch: In the Carousel model, the cost of processing $m$ queries is essentially the same as processing one query, provided $m$ fits within the TEE's memory. This makes it ideal for massive cloud services.
  • Hardware Nuances: The paper highlights that Intel SGX's lack of private memory makes it more vulnerable to side-channel attacks than ARM TrustZone, requiring more careful (and slightly slower) software implementation to ensure privacy.

Key Results

The authors compared their "Cuckoo-on-a-Carousel" (CoaC) method against a state-of-the-art Path ORAM implementation:

  • Sustainable Throughput: On Intel SGX, the Carousel approach supported 3,720 queries/second, which is 2.75x more than Path ORAM. On ARM TrustZone, it supported 1,025 queries/second, nearly 10x more than ORAM.
  • Breakdown Point: ORAM-based systems saw their response times skyrocket once they hit a few hundred queries per second, whereas the Carousel remained stable until its hardware limits were reached.
  • Efficiency: Using 4-ary Cuckoo hashing allowed the dictionary to be represented in roughly 98 MB, fitting efficiently into the memory constraints of modern TEEs.

Limitations and Future Work

  • Dictionary Scaling: If the malware dictionary grows beyond what a single server can cycle efficiently, the authors suggest splitting it into subsets handled by multiple TAs, though this adds complexity to the dispatcher.
  • Side-Channels: While they defend against deterministic page-level attacks, the authors acknowledge that more sophisticated probabilistic cache-timing attacks remain a threat, suggesting future integration with frameworks like Sanctum.
  • Newer ORAMs: The study used Path ORAM as a baseline; the authors suggest that future work could compare the Carousel against even newer, more optimized ORAM variants.

Summary updated

Abstract

Malware checking is changing from being a local service to a cloud-assisted one where users' devices query a cloud server, which hosts a dictionary of malware signatures, to check if particular applications are potentially malware. Whilst such an architecture gains all the benefits of cloud-based services, it opens up a major privacy concern since the cloud service can infer personal traits of the users based on the lists of applications queried by their devices. Private membership test (PMT) schemes can remove this privacy concern. However, known PMT schemes do not scale well to a large number of simultaneous users and high query arrival rates. We propose a simple PMT approach using a carousel: circling the entire dictionary through trusted hardware on the cloud server. Users communicate with the trusted hardware via secure channels. We show how the carousel approach, using different data structures to represent the dictionary, can be realized on two different commercial hardware security architectures (ARM TrustZone and Intel SGX). We highlight subtle aspects of securely implementing seemingly simple PMT schemes on these architectures. Through extensive experimental analysis, we show that for the malware checking scenario our carousel approach surprisingly outperforms Path ORAM on the same hardware by supporting a much higher query arrival rate while guaranteeing acceptable response latency for individual queries.
BibTeX
@inproceedings{tamrakar2017circle,
  author = {Sandeep Tamrakar and Jian Liu and Andrew Paverd and Jan-Erik Ekberg and Benny Pinkas and N. Asokan},
  title = {{The Circle Game: Scalable Private Membership Test Using Trusted Hardware}},
  booktitle = {AsiaCCS},
  year = {2017},
  url = {https://openreview.net/forum?id=1Lw1inpSlTG},
}

Loading related content...

Figure