Abstract
We present a cryptographic proof-of-deletion framework designed for ephemeral file storage systems where verifiable data destruction is a core security requirement. The protocol combines commitment schemes with key-encapsulation erasure to produce a non-interactive proof that a stored file has been irrecoverably destroyed. Over 50,000 deletion events across varying file sizes and storage topologies, the system achieved zero false negatives (no deletion event was incorrectly reported as complete when residual data persisted) with a median verification latency of 137ms. This work underpins the deletion guarantees in PrivDrop's ephemeral transfer architecture.
Background
Ephemeral file sharing services operate under an implicit contract: once a file expires or is retrieved, it ceases to exist. Users trust that deletion is real, not merely a pointer dereference or a deferred garbage collection event. Yet traditional storage systems offer no cryptographic guarantee that deletion has occurred. The file's bytes may persist in unallocated sectors, flash translation layer caches, RAID parity stripes, or remote backup replicas long after the application layer reports successful removal.
For privacy-critical applications, this gap between perceived deletion and actual irrecoverability is unacceptable. A determined adversary with physical or administrative access to storage infrastructure could reconstruct files that users believe were destroyed. Regulatory frameworks such as GDPR's "right to erasure" and emerging data sovereignty laws further demand provable deletion rather than best-effort removal.
The challenge is fundamental: proving a negative. How does a system demonstrate that data no longer exists in any recoverable form, across all layers of a storage stack, without requiring the verifier to inspect every bit of underlying media?
The Challenge
Traditional file deletion is an illusion of irrecoverability. When an operating system "deletes" a file, it typically performs one or more of the following operations: removing the directory entry, marking inode metadata as available, and returning allocated blocks to the free list. The actual file content remains physically present on the storage medium until overwritten by subsequent allocations.
This semantic gap compounds across modern storage architectures:
- Solid-state drives employ wear-leveling algorithms that remap logical blocks to different physical NAND cells, making targeted overwrite of specific data unreliable without full-device sanitization.
- Copy-on-write filesystems (ZFS, Btrfs) retain prior versions of data blocks in snapshots, potentially preserving "deleted" content indefinitely.
- Cloud object storage systems distribute data across multiple nodes with replication factors, where deletion of the primary copy does not guarantee erasure of replicas across all availability zones.
- Filesystem journaling may retain fragments of file content in journal logs even after the primary data blocks are released.
Physical media sanitization (e.g., NIST SP 800-88 guidelines) addresses these concerns but requires hardware-level access and is incompatible with the latency requirements of real-time file sharing systems. A cryptographic approach is needed.
Our Approach
Our proof-of-deletion protocol operates on a principle we term cryptographic encapsulation erasure: rather than proving that specific bytes have been overwritten, we prove that the cryptographic keys necessary to reconstruct the plaintext have been irrecoverably destroyed. If the ciphertext persists but the key material does not, the data is computationally irretrievable.
The protocol proceeds in three phases:
- Commitment phase. At file upload time, the system generates a unique encryption key
K, encrypts the file, and produces a cryptographic commitmentC = Commit(K, r)whereris a randomly sampled blinding factor. The commitment is stored independently of the key material and serves as a binding reference to the original key state. - Erasure phase. Upon deletion trigger (expiry, retrieval, or explicit revocation), the system executes a key destruction sequence that zeroes all copies of
Kacross the storage topology. This includes primary key storage, any in-memory caches, and hardware security module slots if applicable. - Verification phase. The system produces a proof-of-deletion token
πthat demonstrates: (a) a valid keyKsatisfying commitmentCexisted at timet0, (b) no value satisfyingCcan be derived from any remaining system state at timet1, and (c) the intervalt1 - t0is within acceptable bounds.
The commitment scheme employed provides both hiding (the commitment reveals nothing about K) and binding (the committer cannot later claim a different key was used). Combined with a verifiable erasure protocol over the key storage substrate, this produces a non-interactive proof that the file's plaintext is irrecoverable.
The specific commitment scheme parameters, key destruction sequencing logic, and erasure verification circuitry referenced in this study are proprietary to topriv. The protocol description above is simplified for publication. Production implementation includes additional countermeasures against rollback attacks and coercion scenarios that are not disclosed here.
Results
We evaluated the protocol across 50,000 deletion events with file sizes ranging from 1KB to 500MB, distributed across three storage backend configurations. The primary metrics of interest were verification latency (time to produce and validate a proof-of-deletion token) and soundness (whether any false negative - a deletion reported as complete when data remained recoverable - was observed).
Verification Latency by File Size
| File Size | Median Latency | p95 Latency | p99 Latency | Events Tested |
|---|---|---|---|---|
| 1 KB | 42 ms | 61 ms | 78 ms | 8,400 |
| 64 KB | 47 ms | 69 ms | 84 ms | 8,200 |
| 1 MB | 63 ms | 91 ms | 112 ms | 9,100 |
| 10 MB | 98 ms | 134 ms | 158 ms | 8,800 |
| 50 MB | 137 ms | 172 ms | 191 ms | 8,300 |
| 500 MB | 184 ms | 196 ms | 198 ms | 7,200 |
Key observation: Verification latency scales sub-linearly with file size. A 500x increase in file size (1KB to 500MB) produced only a 4.4x increase in median verification time. This is because the proof operates over key material and commitment values, not over the file content itself.
Across all 50,000 deletion events, zero false negatives were recorded. Every deletion that produced a valid proof-of-deletion token was independently verified to have rendered the original plaintext irrecoverable through exhaustive key-space search of the storage substrate. Three false positives (deletion reported as failed when data was actually destroyed) were observed, yielding a false positive rate of 0.006% - an acceptable trade-off favoring conservative failure reporting.
Implications for PrivDrop
This proof-of-deletion protocol is integrated into PrivDrop's ephemeral file transfer pipeline at three critical junctures:
- Link expiration. When a PrivDrop share link reaches its configured TTL (default: 24 hours, configurable down to 5 minutes), the system initiates key destruction and generates a proof-of-deletion token. The expired link resolves to a verification page displaying the deletion proof hash.
- Post-retrieval destruction. For single-use transfers, key material is destroyed immediately upon successful decryption by the recipient. The proof-of-deletion token is appended to the transfer receipt.
- Mathematical guarantee. Each deletion event produces a verifiable, timestamped proof that the encryption key has been irrecoverably destroyed. Because PrivDrop employs client-side encryption with keys that never transit to our servers in plaintext, key destruction at the storage layer renders the ciphertext computationally equivalent to random noise. The proof is independently verifiable without access to the original file content.
This architecture allows PrivDrop to make a stronger claim than "we deleted your file." We can prove, with cryptographic certainty, that the file cannot be reconstructed - not by us, not by an attacker who compromises our infrastructure, and not by any entity without the destroyed key material.
The key destruction sequencing, storage topology mapping, and proof token generation parameters used in production PrivDrop are proprietary. The integration points described above are simplified for publication purposes. Actual implementation includes additional safeguards and redundancies not disclosed here.
Limitations
This protocol provides guarantees at the cryptographic layer, not the physical media layer. If an adversary obtains a copy of both the ciphertext and the encryption key before destruction occurs, proof-of-deletion cannot retroactively protect that data. The protocol also assumes that the key storage substrate faithfully executes erasure commands - a property that must be independently verified for each storage backend. Hardware-level key destruction (e.g., via TPM or HSM zeroization) provides stronger guarantees than software-only approaches but introduces latency and cost trade-offs not fully explored in this study.