💻 computer science

Gyokuro: Source-assisted Private Membership Testing using Trusted Execution Environments

This paper presents Gyokuro, a Source-assisted Private Membership Testing (SPMT) protocol that leverages Trusted Execution Environments (TEEs) to enable efficient, scalable, and privacy-preserving verification of data item inclusion in large databases by proving server progress rather than generating traditional membership proofs.

Original authors: Yoshimichi Nakatsuka, Nicolas Dutly, Kari Kostiainen, Srdjan Capkun

Published 2026-03-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yoshimichi Nakatsuka, Nicolas Dutly, Kari Kostiainen, Srdjan Capkun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you bought a bottle of medicine, and on the box, there's a QR code. You want to know: "Did the pharmacy actually log this specific bottle's journey in the official government database?"

The problem is, you don't want to tell the government (or the database operator) which bottle you are asking about. If you say, "I'm checking bottle #505," they might realize you have a rare allergy or a specific medical condition. You want to check the record without revealing your secret.

This is the problem Gyokuro solves. It's a new system that lets you verify if something is in a database without telling the database what you are looking for.

Here is how it works, explained through a simple story.

The Cast of Characters

The Source (The Pharmacy): They create the medicine and the QR code.
The Server (The Database): A giant, potentially grumpy librarian who stores all the records. We don't fully trust them; they might hide records or lie.
The Monitor (The Inspector): A third-party watchdog (like a government auditor) who checks the librarian's work to make sure they aren't deleting things.
The Client (You): The person holding the medicine, trying to verify the truth.
The TEE (The Secure Vault): This is the star of the show. Think of it as a magic, unbreakable glass box inside the server's computer. Only the code inside can see what's happening. Even the server owner (the librarian) cannot peek inside or tamper with the box.

The Old Way (Why it was hard)

Previously, to check if your medicine was logged, you had to ask the librarian, "Is bottle #505 here?"

The Problem: The librarian now knows you care about bottle #505. If you are a spy or have a secret, you've just been exposed.
The Alternative: Some systems tried to hide your question using complex math (like asking for every bottle in the library to see if yours was there), but that was incredibly slow and expensive.

The Gyokuro Solution: The "Time-Stamp" Trick

Gyokuro changes the game. Instead of asking "Is my item here?", you ask, "Has the Secure Vault processed enough items to guarantee mine is in there?"

Here is the step-by-step analogy:

Step 1: The Drop-Off (Upload)

The Pharmacy (Source) hands the medicine to the Secure Vault (TEE).

The Vault takes the medicine, puts it in a temporary holding area (a buffer), and gives the Pharmacy a receipt.
The Receipt (POR): This receipt says, "I received this medicine at Counter #100." It is signed by the Vault so no one can fake it.
Crucial Point: The Vault doesn't put the medicine in the big database immediately. It waits until it has a full box of medicines, then dumps them all in at once.

Step 2: The Big Dump (Storage)

Once the Vault has 100 medicines, it dumps them into the Database.

The Vault then turns a Counter from 100 to 101.
It also updates a Master Ledger (a hash chain) that proves, "I have processed everything up to this point."

Step 3: You Check In (Testing)

You buy the medicine and get the Receipt (from Step 1). You see it says Counter #100.
You want to know if it's in the database. You don't ask the librarian about your medicine. Instead, you ask the Secure Vault:

"Hey Vault, what is your current Counter number?"

The Vault replies with a Proof of Processing (POP): "My current Counter is 105."

Step 4: The Logic (The "Aha!" Moment)

You do the math:

My receipt says 100.
The Vault says it is now at 105.
Conclusion: Since 105 is greater than 100, the Vault must have processed my medicine and dumped it into the database. I don't need to know which slot it's in; I just know it's in there because the counter moved past it.

Step 5: The Safety Net (Consistency Check)

What if the Vault is lying? What if the Vault says "105" but actually deleted your medicine?

You ask the Monitor (Inspector) what their Counter is.
The Monitor downloads the whole database and calculates its own Counter.
If the Vault's Counter and the Monitor's Counter match, you know for a fact that the database is honest and your medicine is inside.

Why is this a Big Deal?

Total Privacy: You never told the database "I care about bottle #505." You only asked for a number. The database operator has no idea what you are checking.
Super Fast: Because you aren't searching through millions of records, and the Vault doesn't have to look up your specific item, the check happens in 7 milliseconds. That's faster than a human blink.
Scalable: It doesn't matter if the database has 100 items or 10 billion items. The time it takes to check is always the same. It's like checking a counter on a wall; it takes the same time whether the wall is 1 foot tall or 1 mile tall.

The "Magic Box" (TEE)

The whole system relies on the Secure Vault (TEE). We trust that the Vault is honest because it's a piece of hardware designed to be unbreakable. Even if the server owner tries to hack it, the Vault won't let them.

The Catch: If someone invents a way to break these magic boxes in the future, the system might be vulnerable. But for now, it's the best way to get speed and privacy together.

Real-World Examples

Certificate Transparency: Checking if a website's security certificate is valid without the website knowing you are checking.
Drug Safety: Verifying a drug's supply chain without revealing your medical condition.
Fake News: Checking if a photo was logged by a fact-checker to prove it's real, without revealing which photo you are suspicious of.

In short: Gyokuro is like checking if your package was delivered by looking at the delivery truck's odometer. If the truck has driven further than the point where your package was loaded, you know it's delivered—without ever telling the driver exactly what you were waiting for.

1. Problem Statement

The paper addresses Source-assisted Private Membership Testing (SPMT), a specific variant of Private Membership Testing (PMT).

Goal: Enable a client to verify if a specific data item exists in a database without revealing the item's identity to the database operator (server) or external parties.
Context: Unlike standard PMT where the client queries the server directly, SPMT assumes the client possesses "source-assisted information" (e.g., a digital signature or receipt) issued by the data source when the item was first submitted.
Applications: Certificate Transparency (CT) log auditing, supply-chain auditing (e.g., verifying drug provenance), data provenance verification, and public document auditing.
Challenges: Existing solutions struggle to balance efficiency, scalability, and privacy.
- Cryptographic approaches (PIR, PSI, ORAM, Homomorphic Encryption) often suffer from high computational/communication costs that scale with database size or require complex client-side storage.
- Trusted Execution Environment (TEE) approaches often require the client to send the query to the TEE, making it vulnerable to side-channel attacks, or rely on expensive protocols like ORAM to hide access patterns.
- Timeliness vs. Integrity: A naive solution relying on "time passage" (assuming the server stores data by a deadline) fails because a malicious server can delay execution, and current TEEs cannot guarantee execution timeliness (only integrity).

2. Methodology: The Gyokuro System

Gyokuro proposes a novel approach that leverages TEE execution integrity combined with third-party monitors and monotonically increasing counters to prove data inclusion without revealing the client's interest.

Core Architecture

The system involves five entities:

Data Source: Generates data and issues source-assisted info.
Server (Untrusted): Hosts the database.
TEE (Trusted): Runs on the server but is isolated (e.g., AMD SEV, Intel SGX). It holds the logic for processing data and maintaining counters.
Monitor (Honest-but-Curious): An external entity that periodically downloads the full database to verify consistency.
Client: Wants to verify if a specific item is in the database.

Key Protocols

The system operates via two main phases: Upload and Testing.

A. Upload Protocol (Data Submission)

Submission: The Data Source sends a data item ( $d$ ) and a signature to the TEE.
Buffering: The TEE appends $d$ to an internal buffer.
Proof of Reception (POR): The TEE signs the data item and the current counter value ( $cnt_{POR}$ ), returning a POR to the Data Source. This serves as the "source-assisted information" passed to the client later.
Storage & Accumulation: When the buffer is full, the TEE flushes data to the external database.
- It updates a Hash Chain Accumulator ($HCT$) with the buffer contents.
- It increments the Counter ($cnt$).
- It records the tuple $(HCT, cnt)$ in a local list ( $List_{HCT}$ ).
- It waits for an ACK from the database before incrementing.

B. Testing Protocol (Membership Verification)

Client Input: The client holds the data item ( $d'$ ) and its corresponding POR (containing $cnt_{POR}$ ).
Monitor Sync: The Monitor downloads the database, reconstructs its own Hash Chain ($HCM$), and signs it.
Proof of Processing (POP):
- The client sends the Monitor's signed Hash Chain ($HCM$) to the TEE.
- The TEE looks up $HCM$ in its $List_{HCT}$ to find the corresponding counter value ( $cnt_{POP}$ ).
- The TEE signs $cnt_{POP}$ and returns it as a Proof of Processing (POP).
Verification: The client verifies:
- The TEE's attestation report (ensuring it is a genuine TEE).
- The POR and POP signatures.
- The Critical Check: Is $cnt_{POR} < cnt_{POP}$ $c n t_{P O R} < c n t_{P O P}$ ?
  - If Yes: The TEE has processed the batch containing $d'$ and the Monitor has verified the database state consistent with that batch. The item is in the database.
  - If No: The item has not been processed yet, or the Monitor is out of sync.

Privacy Mechanism

Zero-Knowledge of Interest: The client never sends the data item $d'$ to the TEE or the server. The TEE only sees the Monitor's Hash Chain and the current counter.
Side-Channel Resistance: Since the query does not depend on the specific data item, side-channel attacks (e.g., cache timing) on the TEE cannot leak which item the client is checking.
Scalability: Communication and computation are constant ( $O(1)$ ) regardless of database size, as the TEE does not traverse the database during testing.

3. Key Contributions

Problem Identification: Highlighted the gap in efficient, scalable SPMT protocols for applications like CT logs and supply chains.
Novel Solution (Gyokuro): A TEE-based scheme that replaces "proof of inclusion" (which requires real-time processing) with "proof of sufficient progress" (using counters and hash chains).
Privacy Guarantee: Achieves strong client privacy by ensuring the membership query is independent of the client's specific interest, mitigating side-channel risks inherent in other TEE-based PMT solutions.
Performance: Demonstrated that the system achieves constant-time complexity for both upload and testing, independent of database size.

4. Experimental Results

The authors implemented Gyokuro using Go and AMD SEV on Azure Cloud (16-core VM).

Latency:
- Upload (Data Submission): ~6.5 ms (averaged over 1024 concurrent sources).
- Membership Testing: ~7 ms (averaged over 1024 concurrent clients).
- Note: Latency is dominated by network RTT and cryptographic verification, not database size.
Throughput:
- Upload: ~1,021 requests/sec/core.
- Testing: ~1,432 requests/sec/core.
Scalability: The system successfully handled a database of 3.3 million certificates (simulating a CT log) with no degradation in performance.
Real-world Feasibility:
- CT Logs: Can handle ~128 certs/sec (current real-world load is ~128/sec), well within the 1,000+ capacity.
- Supply Chain: Can handle thousands of consumer checks per second.

5. Significance and Limitations

Significance:

Efficiency: Solves the scalability bottleneck of previous PMT schemes (like PIR/ORAM) which scale poorly with database size.
Privacy: Offers a robust defense against side-channel attacks by decoupling the query from the data item.
Practicality: Provides a viable solution for high-volume, privacy-sensitive auditing tasks like Certificate Transparency, where current browser implementations often skip auditing due to performance costs.

Limitations:

Trust Assumption: Relies on the integrity of the TEE hardware. If the TEE is compromised (e.g., future hardware vulnerabilities), the system's guarantees fail. Purely cryptographic solutions do not have this single point of failure.
Timeliness: The system assumes the TEE makes "sufficient progress" but cannot strictly guarantee when a specific item is stored if the server delays the TEE (though the counter mechanism detects if progress has stalled).
Monitor Dependency: Requires the existence of honest monitors to verify database consistency and prevent "split-view" attacks.

Conclusion

Gyokuro represents a significant advancement in Private Membership Testing by shifting the paradigm from "proving inclusion of a specific item" to "proving the system has progressed far enough to include the item." By leveraging TEEs for integrity and monitors for consistency, it achieves high performance and strong privacy, making it suitable for large-scale, real-world auditing applications.