Policy-Compliant Cloud Storage Systems

Verifying Privacy in an Untrusted Cloud

How can an organization prove to a regulator that it is following strict privacy laws when the underlying cloud infrastructure is fundamentally untrusted? Modern data processing relies heavily on key-value stores (KVS)—simple, high-speed databases used for everything from caching to IoT pipelines—but these systems are built for speed, not for the complex legal requirements of regulations like the GDPR.

Currently, ensuring compliance often requires engineers to rewrite application logic or deeply modify database engines. Both tasks are expensive and prone to error. Furthermore, if a cloud provider's privileged software is compromised, they could potentially tamper with the very audit logs meant to prove compliance. A new study introduces GDPRuler, a middleware system designed to automate and verify GDPR compliance without requiring any changes to the existing database code.

The compliance gap in high-speed storage

Key-value stores are prized for their simplicity. They map unique keys to specific values, much like a dictionary maps words to definitions. However, this flat data model lacks the inherent "awareness" needed for privacy regulation. Under the GDPR, data must be handled according to specific "purposes"—for example, using a user's email for shipping but not for unsolicited marketing. Data must also be deleted when a user exercises their "right to be forgotten."

As illustrated in, the GDPR ecosystem involves multiple actors: data owners (individuals), controllers (organizations), processors (services), and regulators.

In a standard cloud deployment, the controller's responsibility to enforce "purpose limitation" or "storage limitation" is difficult to guarantee. This is because the cloud operator's hypervisor (the software that manages virtual machines) or operating system could observe or alter the data and the audit trails. Existing solutions typically fall into two traps. They are either too invasive, requiring a complete overhaul of the database, or they are too weak, assuming the cloud environment is inherently trustworthy.

A trusted proxy for untrusted clouds

The authors propose solving this by interposing a trusted middleware layer between the application and the database. Instead of modifying the database, GDPRuler acts as a transparent proxy. The core of this architecture is the deployment of a "GDPR monitor" inside a Confidential Virtual Machine (CVM). A CVM is a hardware-isolated environment—supported by technologies like AMD SEV-SNP or Intel TDX—that prevents even the cloud provider from accessing the memory or logic running inside it.

The system functions through several coordinated stages. This is detailed in the architecture in and the operational flow in .

First, the system uses a declarative policy language to translate legal requirements into machine-executable rules. When an application sends a request, the "Policy Compiler" merges the user's default privacy settings with the specific intent of the query.

Next, the "Trusted GDPR Monitor" validates the request against these rules. For instance, if a service tries to access data for "marketing" but the user has an "objection" to that purpose, the monitor blocks the operation. To keep the database fast, the monitor doesn't just scan everything. It uses specialized in-memory indexes, such as B+ trees or hash maps, to jump directly to the relevant metadata .

Finally, the "Data I/O Subsystem" handles the heavy lifting. It encrypts the data payloads, attaches compact metadata to the records, and maintains a "tamper-evident" audit log. These logs use a monotonically increasing counter (a software-based number that only goes up) protected within the CVM. This ensures that an attacker cannot delete or roll back history without detection.

Measuring the cost of compliance

The primary engineering concern with any security layer is the performance tax. The authors report that GDPRuler achieves approximately 61% of the throughput of a native, unmodified KVS (like Redis or RocksDB). When breaking down this overhead, the paper finds that the CVM environment itself accounts for 28% to 32% of the performance degradation. Adding the GDPRuler compliance logic adds only about 8.6% more overhead.

The impact on storage is also manageable. The authors report that embedding compliance metadata directly within the KV records results in a storage overhead of less than 20%. One of the most significant findings involves the efficiency of privacy-specific queries. Without specialized indexing, searching for all data belonging to a specific user would require a slow, full-database scan. However, the authors demonstrate that by using dedicated metadata indexes, GDPR queries see a speedup of 13× to 182× . Furthermore, the authors note that the asynchronous, batched logging system is highly efficient. It reduces the impact on overall throughput to less than 2%.

Limits of the trusted boundary

While GDPRuler provides a robust defense, it is not a universal panacea. The authors explicitly state that the system does not protect against "rollback attacks" on the database data itself. A rollback attack occurs when an attacker restores an older, valid version of the database to undo a recent change, such as a deletion. Preventing this would require an intrusive redesign of how the database manages versions. Such a redesign would contradict the paper's goal of being a "drop-in" solution.

Additionally, the security guarantees are bounded by the hardware. The authors do not explore side-channel attacks (subtle leaks of information through physical phenomena like power consumption or timing). Nor do they address denial-of-service attacks. For a practitioner, this means that while GDPRuler secures the logic and integrity of your privacy policies, it does not replace the need for standard network security and DDoS protection.

The verdict: A practical retrofit

If you are looking for a way to bring regulated data into a public cloud without re-engineering your entire stack, GDPRuler is a highly compelling candidate. The research proves that you can decouple compliance from the database engine. You can achieve verifiable enforcement with a manageable 40% performance penalty.

The decision to use this depends on your workload. For latency-sensitive, high-throughput applications where every microsecond counts, the 61% throughput ceiling might be a dealbreaker. However, for most enterprise applications, the priority is meeting legal mandates. Providing auditable proof to regulators is a significant practical advantage. Code is reportedly available; see the paper for the canonical link.

Figures from the paper