Differential privacy (DP) is a promise that a published result barely changes whether or not any one person's record was used. Each release spends part of a fixed, non-refillable "privacy budget," and once the budget is gone the dataset must be retired. Cluster schedulers now manage this budget across many jobs. They all rest on an unchecked assumption: the analyst's code really adds the right noise, really limits how much each record can influence the answer, and never copies raw data out once it has access. If that code is buggy or malicious, the scheduler's accounting means nothing. A host administrator can also simply restart the accounting service and wipe the record of what has been spent.
This note proposes a small trusted component that holds the only decryption key, adds the DP noise, and keeps a tamper-resistant record of budget spending. The analyst's code becomes untrusted and runs one record at a time inside a sandbox that is wiped after every record, so its output can depend only on that record. The combination ensures that each record's influence is bounded by construction rather than by trust. The trusted component then clips and sums the per-record outputs, adds noise, and charges the budget. In short, we move the DP guarantee from the analyst's program to the narrow gate through which any data-derived number must pass. We then measure whether doing so is cheaper than the main alternative, which is computing on encrypted data.
Core Claim
A trusted execution environment (TEE) is a hardware-isolated region of a processor whose code can be cryptographically verified by a remote party and whose memory the host operating system cannot read. Our claim is that a TEE-hosted release gate, combined with a sandbox that is restored to a clean state between records, can enforce record-level DP for untrusted analysis code. Three properties make this work.
The first is contribution bounding by isolation. The untrusted "map" step runs on exactly one privacy unit in a freshly restored sandbox with no network and no persistent state. The gate then clips each output to a declared norm $C$ and sums the clipped outputs, so the sensitivity is $C$ regardless of what the map code does.
The second is a budget ledger the host cannot roll back. The gate keeps an append-only, signed ledger protected by monotonic counters. An attacker who restarts the gate therefore cannot reset spent budget.
The third is deterministic noise for exact repeats. The gate generates noise with a pseudorandom function keyed by a secret held inside the gate and evaluated on the job's container digest, the data block identifiers, and the query. Resubmitting an identical job returns the identical answer at zero additional cost. As a result, averaging over repeated runs gains nothing, even if the attacker manages a rollback.
The intended result is that the cluster schedulers of Privacy Budget Scheduling and Packing Privacy Budget Efficiently keep their scheduling throughput while dropping the "user code is trusted" assumption. We also expect the overhead of this enforcement to be well below that of fully homomorphic encryption (FHE), meaning computation directly on encrypted data, on the same workloads.
Where This Sits in Prior Work
Several papers motivate the gap. PrivateKube (Privacy Budget Scheduling) treats privacy budget as a Kubernetes resource and gains 14x to 17x more pipelines through Rényi accounting. It also states explicitly that verifying container compliance after data access "is future work." DPack (Packing Privacy Budget Efficiently) packs tasks more tightly under the same trust assumption. We reuse their schedulers unchanged and replace only the enforcement layer beneath them.
Two papers supply the method. Airavat (Airavat: Security and Privacy for MapReduce) already ran untrusted mappers per record, with a trusted reducer that clamps outputs and adds noise. It enforced isolation with a trusted host operating system, used hard-stop accounting, and assumed the operator was honest. We keep its map/reduce split. We replace the trusted operating system with hardware attestation and clean-state sandbox resets of the kind used for agent trials in OpenHands. We replace hard stops with modern schedulers. ROTE: Rollback Protection for Trusted Execution supplies the rollback-protected counter design for the ledger.
The closest TEE-plus-DP work is ODP (An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors). It makes both outputs and memory access patterns DP inside SGX, but only for fixed, trusted algorithms such as histograms and distinct counts. It has no budget management and no support for untrusted user code. CacheDP (Cache Me If You Can) makes repeated exploratory queries free by caching. Our deterministic noise handles exact repeats in a stateless way, so it survives a rollback that would also erase a cache. CacheDP's reuse of near-duplicate queries is complementary and can be layered on top.
On the encrypted-computation side, FHAIM (FHAIM) runs the AIM synthetic-data mechanism on CKKS ciphertexts and relies on a separate decryption oracle. TEEFHE (Toward Scalable Fully Homomorphic Encryption Through Light Trusted Computing Assistance) moves FHE noise refresh into SGX. Neither paper tracks budget across jobs. Both are the natural alternatives we must outperform on cost.
Two lines of work constrain the design. SgxPectre Attacks and the broader side-channel literature imply that untrusted code placed inside an enclave can deliberately signal through page-fault and timing patterns. Earlier attacks only had to cope with accidental leakage. This is the central risk of our design, and the program treats it as a measured quantity rather than assuming it away. Memory limits documented in Memory-Efficient Deep Learning Inference in Trusted Execution Environments push us toward streaming the gate's clip-and-sum, which needs memory proportional to the output dimension and not to the dataset.
Research Program
We will build three pieces. The first is the gate: an attested enclave that holds the data key, performs per-unit clipping, summation and noise addition, keeps the rollback-protected ledger, and exposes PrivateKube's privacy-claim interface so DPF and DPack run on top of it unmodified.
The second is the isolated mapper runtime. It is a version-pinned container that is snapshot-restored before each privacy unit, has no network, and gets a pre-allocated, pre-faulted memory region. Its wall-clock time is padded to a declared maximum, and its output is encrypted to the gate. The pinned image digest serves two purposes: it keys the deterministic noise, and it appears in the ledger for auditing. In this way the provenance logging of Audit-Grade Harness for Agent-driven Scientific Computation Workflows becomes something a third party can check cryptographically, where SciAgent's checks are judged by a language model.
The third is a batching variant. Per-record restores are expensive, so we also test restoring per privacy unit, such as one user's block, which spreads the restore cost over that unit's records. We will quantify how much the choice of privacy unit changes the overhead.
The analysis has two parts. The first is a short proof that the released output satisfies record-level $(\epsilon,\delta)$-DP. The proof rests on two stated assumptions: isolation between restores and the hardware trust model. It should hold for any mapper code and any choice by the host of which ciphertexts to feed which sandbox. The second is a measured bound on leakage through side channels the mapper deliberately creates. We will report it as bits per record for each mitigation setting: no padding, timing padding only, and timing padding plus pre-faulted memory.
Baselines
The naive reference point is PrivateKube as published, in which user containers run in plaintext and are trusted to call a DP library. This gives the performance ceiling, since enforcement adds no cost, and the security floor, since a malicious container leaks everything. On the Amazon Reviews workload it supports 14x to 17x more pipelines under Rényi accounting than under classical accounting (Privacy Budget Scheduling). For the scheduling layer, DPack schedules 1.3–1.7x more tasks than DPF on the Alibaba-DP trace and stays within 23% of the exact optimum (Packing Privacy Budget Efficiently).
We run both schedulers over our gate on the same traces, with the same block configuration and the same tuning. Our success criterion has two parts. Our version must schedule at least 90% of the tasks the unenforced version schedules. It must also hold every privacy claim against the malicious-mapper suite, where the unenforced version fails.
The strongest competitor on enforcement cost is FHE-based input privacy in the style of FHAIM, which needs no hardware trust. On Breast Cancer, COMPAS and Diabetes it matches plaintext AIM utility at $\epsilon=1$ with end-to-end runtimes of 11 to 30 minutes (FHAIM). We run AIM's marginal-measurement step as a mapper on the same datasets, with the same $\epsilon$ and the same hardware class. We count as beating it if we match its synthetic-data utility at an end-to-end runtime at least an order of magnitude lower. A TEEFHE-style hybrid, where FHE runs on untrusted nodes and noise refresh plus DP release happen in the enclave, is the intermediate design point. TEEFHE reports a memory reduction from 50.02 GiB to 225.86 MiB on iDASH, but we found no reported result on Lacuna for TEEFHE on AIM or on any multi-job budget workload. We will therefore implement this point ourselves.
Airavat-on-trusted-OS, with per-record isolation but no TEE and no reset, is run on the same workloads to separate the cost of hardware isolation from the cost of the map/reduce restriction. We found no reported result on Lacuna for Airavat on these benchmarks.
Three ablations isolate the key ingredients. The first removes per-unit restores, letting the mapper see a batch; this should fail the cross-record mixing attack and shows that resets are what make sensitivity hold. The second removes rollback protection; this should fail the restart attack. The third replaces deterministic noise with fresh noise; this should allow averaging over resubmissions after a rollback.
Why not just…?
Why not just attest a vetted DP library inside a confidential container and keep PrivateKube's interface? If every pipeline uses a fixed, audited library such as Opacus, then attesting that binary does enforce DP. In that case our per-record isolation adds cost and no protection, apart from the ledger's rollback resistance. This is a real threat, and we will settle it empirically. We will classify the pipeline types in the Amazon Reviews and Alibaba-DP workloads by whether they fit a fixed library. We will also report the overhead of our design over attested-library execution. If almost all workloads fit a vetted library and our overhead is large, the honest conclusion is to ship the ledger alone and use isolation only for custom code.
Why not just compute on encrypted data and skip trusting the hardware? FHE removes the hardware trust assumption and, unlike our design, also defeats deliberate side channels, because the mapper never sees plaintext. Its costs are severe, however. FHAIM needs 11 to 30 minutes on datasets of at most 7,214 rows and had to change its distance norms for numerical stability. Ciphertext transfer can reach tens of gigabytes per request (A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification). FHE alone also does not stop a host from computing a high-sensitivity function on ciphertexts before release, so a trusted release point is still needed. The head-to-head comparison on the AIM workloads will measure the cost gap directly.
Why not just cache past answers instead of deriving noise deterministically? For exact repeats, a cache and deterministic noise give the same answer. The difference appears under attack: an attacker who rolls back the gate's state erases the cache as well, whereas a pseudorandom function keyed by a secret sealed inside the gate regenerates the same noise without any stored state. The third ablation tests exactly this case. For near-duplicate queries, CacheDP's structured reuse (Cache Me If You Can) does strictly more than our mechanism, and we treat it as complementary.
Why not just isolate the host with standard containers? Namespaces and Kubernetes give reproducibility but offer no confidentiality against a root administrator, who can read mounted data blocks or reset the budget store. PrivateKube concedes this weakness. The restart and memory-inspection attacks will show it on the unenforced baseline.
Proposed Experiments
The scheduling experiment replays the Amazon Reviews pipelines and the Alibaba-DP trace through DPF and DPack under four conditions: unenforced, attested-library, our gate with per-record isolation, and our gate with per-unit isolation. We report tasks scheduled, budget utilization per block, and job latency.
The cost experiment runs AIM on Breast Cancer, COMPAS and Diabetes, and DP-SGD on CIFAR-10. In each case we compare our gate, FHAIM-style FHE, and the TEE-plus-FHE hybrid, reporting wall-clock time, peak enclave memory and downstream accuracy at matched $\epsilon$. For CIFAR-10, Goten's 89% accuracy without DP (Goten) serves only as an upper reference. The per-example restore cost is the quantity most likely to sink the design for training, and we report it directly.
The interactive experiment replays IDEBench exploration sessions on Adult, NYC Taxi and Planes with and without deterministic noise, and with CacheDP layered on top. It reports cumulative budget spent.
The security experiment is the decisive check. A suite of malicious mappers attempts four attacks: cross-record mixing, exfiltration through output scaling, timing covert channels, and page-fault covert channels. The host side attempts gate restarts and resubmission averaging. The design passes only under three conditions. A canary-record membership test against released outputs must stay within the DP bound at the claimed $\epsilon$. Restart and averaging attacks must recover no extra information. The measured covert-channel capacity under full mitigation must be small enough to state as an explicit additive leakage term.
If the page-fault channel cannot be pushed below a useful bound, the proposal narrows to honest-but-buggy analyst code, where the guarantee still closes PrivateKube's open problem. Malicious code would then have to use the FHE path.
References
- Privacy Budget Scheduling
- DPack: Efficiency-Oriented Privacy Budget Scheduling
- Airavat: Security and Privacy for MapReduce
- OpenHands: An Open Platform for AI Software Developers as Generalist Agents
- ROTE: Rollback Protection for Trusted Execution
- An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors.
- Cache Me If You Can: Accuracy-Aware Inference Engine for Differentially Private Data Exploration
- FHAIM: Fully Homomorphic AIM For Private Synthetic Data Generation
- Toward Scalable Fully Homomorphic Encryption Through Light Trusted Computing Assistance
- SgxPectre Attacks: Leaking Enclave Secrets via Speculative Execution
- Memory-Efficient Deep Learning Inference in Trusted Execution Environments
- Audit-Grade Harness for Agent-driven Scientific Computation Workflows
- A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification
- Goten: GPU-Outsourcing Trusted Execution of Neural Network Training