# Elephants Do Not Forget: Differential Privacy with State Continuity for Privacy Budget

arXiv: https://arxiv.org/abs/2401.17628 · HTML: https://mlsanity.com/paper/2401.17628/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2024.

## Built on by (most cited first, 5 of 5)

- [Confidential Federated Computations](https://mlsanity.com/paper/2404.10764/) (2024)
- [Position: Certified Robustness Does Not (Yet) Imply Model Security](https://mlsanity.com/paper/2506.13024/) (2025)
- [PAPAYA Federated Analytics Stack: Engineering Privacy, Scalability and Practicality](https://mlsanity.com/paper/2412.02340/) (2024)
- [Securing Private Federated Learning in a Malicious Setting: A Scalable TEE-Based Approach with Client Auditing](https://mlsanity.com/paper/2509.08709/) (2025)
- [ElephantAgent: Contextual State Continuity in Agentic Systems](https://mlsanity.com/paper/2607.01919/) (2026)

## Abstract (arXiv)

Current implementations of differentially-private (DP) systems either lack support to track the global privacy budget consumed on a dataset, or fail to faithfully maintain the state continuity of this budget. We show that failure to maintain a privacy budget enables an adversary to mount replay, rollback and fork attacks - obtaining answers to many more queries than what a secure system would allow. As a result the attacker can reconstruct secret data that DP aims to protect - even if DP code runs in a Trusted Execution Environment (TEE). We propose ElephantDP, a system that aims to provide the same guarantees as a trusted curator in the global DP model would, albeit set in an untrusted environment. Our system relies on a state continuity module to provide protection for the privacy budget and a TEE to faithfully execute DP code and update the budget. To provide security, our protocol makes several design choices including the content of the persistent state and the order between budget updates and query answers. We prove that ElephantDP provides liveness (i.e., the protocol can restart from a correct state and respond to queries as long as the budget is not exceeded) and DP confidentiality (i.e., an attacker learns about a dataset as much as it would from interacting with a trusted curator). Our implementation and evaluation of the protocol use Intel SGX as a TEE to run the DP code and a network of TEEs to maintain state continuity. Compared to an insecure baseline, we observe 1.1-3.2× overheads and lower relative overheads for complex DP queries.