  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 only 1.1-2$\times$ overheads and
lower relative overheads for larger datasets and complex DP queries.
