Release Timing as a Leak in Temporal Differential Privacy

A recent line of privacy work releases sensitive time series without adding noise to the values. It hides when things happened instead. It delays readings, dispatches them to later time slots, or swaps values between nearby timestamps, so that an observer cannot tell exactly when a reading occurred. The formal guarantee concerns the released sequence. A live system, however, also reveals when each released item leaves the machine. If a value swapped out of slot $t$ can only be emitted once its swap partner arrives, or if some time steps take longer to process than others, the wall-clock emission times can reveal the true timestamps the mechanism was meant to hide. We propose to measure this timing leak in streaming implementations of temporal local differential privacy. We also propose to close it with a tool borrowed from real-time data structures: de-amortization, meaning the practice of spreading expensive reorganization work into a small fixed quota per operation so that no single step is slow.

The core observation is simple. If every output slot is emitted on a fixed, data-independent schedule, the timing channel carries no information, and the formal privacy proof covers the whole observable transcript. Hitting a fixed schedule at low cost requires constant worst-case work per slot, which is exactly what de-amortization provides. This turns a latency engineering technique into a privacy requirement. The idea mirrors how de-amortized oblivious memory hides access patterns, but here it is applied to the timing of temporally privatized streams.

Core Claim

Temporal local differential privacy (TLDP) was formalized in Beyond Value Perturbation: Local Differential Privacy in the Temporal Setting. That paper defines two streams as neighbors if values can be exchanged within a window of $k$ steps, and it proposes threshold dispatch mechanisms (TM, ETM) that avoid slot collisions. Stateful Switch replaces one-way delays with atomic value swaps between two timestamps inside the window. Its stateful variant, StaSwitch, tracks each item's accumulated delay, which yields an exact permutation with no lost or duplicated values. As summarized in our file, both papers analyze the adversary's view of the output sequence $o = (o_1, o_2, \dots)$. Neither models the emission times $\tau_s$ at which each $o_s$ becomes visible.

Our claim has three parts. First, natural streaming implementations make $\tau_s$ depend on the data. One example is a "publish when filled" design, where a slot is emitted as soon as its value is known. Another is any implementation whose per-step compute varies with the mechanism's internal state. In such implementations an adversary can recover displacement information from timing alone. Second, if $\tau_s$ is a fixed function of $s$, the transcript inherits the output's guarantee. Formally, if $\tau_s = s + k + c$ for a constant $c$, then

$$ \Pr[(o,\tau) \mid x] \le e^{\epsilon} \Pr[(o,\tau) \mid x'] \quad \text{whenever} \quad \Pr[o \mid x] \le e^{\epsilon} \Pr[o \mid x'], $$

where $x, x'$ are neighboring input streams, $\epsilon$ is the privacy parameter, and the inequality holds because $\tau$ is a deterministic function independent of the data (post-processing). Third, such a schedule can be met cheaply only if the privatizer does bounded, constant work per slot. Padding every step to an $O(k)$ worst case is expensive. De-amortized bookkeeping makes the padded worst case small.

The idea differs from the closest work in specific ways. Towards Practical Oblivious Map uses de-amortized ORAM (DAORAM) to remove eviction spikes when hiding memory access patterns in key-value stores. It does not treat differential privacy over time series or emission timing. Mitzenmacher et al. similarly spread oblivious shuffles across accesses. We take their insight that uniform per-operation work hides information and apply it to a different object: the emission schedule of a temporal privacy mechanism.

Why we did not pursue the obvious intersection

The research file's leading candidate gap is a worst-case sliding-window aggregator for "out-of-order" privatized streams. It would combine DABA from In-order sliding-window aggregation in worst-case constant time with the out-of-order FiBA from Optimal and General Out-of-Order Sliding-Window Aggregation. On inspection, the premise does not hold up.

A swap or dispatch mechanism releases values in slot order, so a downstream consumer already sees an in-order stream and can run DABA unchanged. The only way to make the consumer's stream out of order is to emit slots as they fill. Doing that leaks the true timestamps through arrival time, which is precisely the leak studied here. If one insists on consumer-side disorder anyway, a ring buffer of $k$ slots indexed by timestamp modulo $k$ absorbs it in constant worst-case time. That buffer works because StaSwitch guarantees exactly one value per slot, and it adds none of the sorting spikes the file attributes to reorder buffers. The aggregation gap therefore reduces to a solved engineering step, while the timing question is both open and consequential.

Research Program

The first component is an attack study. We will implement TM, ETM, RanSwitch and StaSwitch in three emission disciplines. In "publish when filled," a slot is emitted the moment its value is determined. In "in-order, best effort," slot $s$ is emitted as soon as all slots up to $s$ are determined and processed. In "fixed schedule," slot $s$ is emitted exactly at $s + k + c$. For each discipline we train an adversary that sees the privatized values and the emission timestamps and predicts each value's true timestamp, or equivalently its displacement. We report how much better it does than an adversary that sees values alone.

The second component is an instrumentation study of per-slot work. We will measure whether the stateful mechanisms do variable work per step, for example when StaSwitch's delay-tracking state forces a switch or when TM's threshold $c_0$ is hit. We do not know from the file whether reference implementations already do constant work. If they do, the contribution narrows to the emission-schedule result and the attack, and we will report that plainly.

The third component is construction. We will build de-amortized versions of the mechanisms in which all window bookkeeping runs as a fixed quota of steps per slot. That bookkeeping includes candidate-partner selection, delay-state updates and threshold accounting. The design follows the fixed-quota queue of Naor et al., which processes cuckoo evictions a constant number of steps per operation, and the constant-per-arrival expiry sweep of Sliding Bloom Filters. Output goes through a slot-indexed ring buffer on the fixed schedule, and any slack is filled with dummy work.

The proof obligation is that the output distribution is identical to the original mechanism's, so all published utility results carry over. We deliberately scope out microarchitectural channels such as cache and branch timing. We will measure coarse residual timing, but we do not claim constant-time code in the cryptographic sense.

The data are the streams on which TLDP was evaluated: U.S. stock prices, taxi trajectories and synthetic series. We add one-minute vital signs from MC-MED and charted observations from MIMIC-III to represent the clinical telemetry setting. MIMIC-III's release relies on a static per-patient date shift that preserves intervals. That shift is safe precisely because it is applied offline in a batch, with no timing channel. EHRCon finds that over 56% of note–table discrepancies in MIMIC-III are time-related, often exactly one hour, and it names date-shifting pipelines as a suspected cause. This motivates treating de-identification timing as a first-class artifact once releases go live, but we do not attempt to reproduce those discrepancies.

Baselines

The naive reference point is "publish when filled" with the unmodified mechanisms. It has minimal latency and, we expect, maximal timing leakage. It anchors the leakage scale and shows the attack is not vacuous.

The strongest existing method on utility is StaSwitch as published. Stateful Switch reports simple-moving-average MSE three to five orders of magnitude lower than value perturbation and a utility gain of more than 20% over RanSwitch. For TM/ETM on taxi clustering, Beyond Value Perturbation reports NMI of 0.6–0.7. We run StaSwitch in its best-effort in-order emission mode on the same streams, window sizes $k$ and privacy budgets $\epsilon$, on the same hardware. Our fixed-schedule construction must match its utility within sampling error and reduce timing-adversary advantage to chance. No reported result on timing leakage for any TLDP mechanism was found on Lacuna, so that baseline number is ours to establish.

The strongest competitor on cost is the naive privatizer padded to its measured worst-case step time with a timer. This is a timing-safe design that uses no de-amortization. We give it the same schedule, hardware and implementation effort. Beating it means the de-amortized version sustains a clearly higher maximum input rate at equal leakage. On latency, In-order sliding-window aggregation in worst-case constant time reports that Two-Stacks shows 99.999th-percentile spikes orders of magnitude above DABA at window size $2^{14}$. This is evidence that amortized worst cases can be large, but it concerns aggregation, not privatization.

Two ablations isolate the key ingredient. The first keeps the fixed emission schedule but uses variable per-slot work, which tests whether the schedule alone suffices when the deadline is generous. The second keeps constant per-slot work but emits in best-effort order, which tests whether constant work alone suffices.

Why not just…?

Why not just pad every step to the worst case with a timer? This is the real threat, and it may win. If the mechanisms' per-step work is already small and nearly constant, padding is simpler and costs little. The padded-baseline comparison settles the question. Our construction earns its place only if the measured worst case of the naive implementation grows with $k$, so that padding caps throughput at roughly one slot per $O(k)$ work. We will report the $k$ at which the two cross, including the case where they never do.

Why not just release in batch, as MIMIC-III and MC-MED do? Offline release has no timing channel, and for archival datasets it is the right answer. It is unavailable for live monitoring or trading feeds, which are the use case TLDP was designed for. The offline pipelines in the file are also slow: PRIPEL takes 4 to 13 minutes per log in PRIPEL.

Why not just add value noise, which keeps timestamps honest? The cited evidence is strong that this destroys utility. StaSwitch's moving-average MSE is three to five orders of magnitude lower than value perturbation, and Laplace noise drives trajectory-clustering NMI to near zero, versus 0.6–0.7 for TM/ETM. We include value-LDP only as a utility floor.

Why not just emit in order after a fixed delay $k$? That is part of our design, not an alternative to it. The open question is whether real implementations meet a fixed deadline for every slot. The "fixed schedule, variable work" ablation measures how often deadline misses reintroduce data-dependent timing.

Decisive Checks

The first check is the attack. On the taxi and stock streams, and on MC-MED vitals, we measure how well the timing adversary under "publish when filled" and "best effort" recovers displacement. We also run a distinguishing test between neighboring streams, which gives an empirical lower bound on the effective $\epsilon$ once timing is included. If the timing adversary does no better than the values-only adversary, the project's premise fails and we stop.

The second check is closure and cost. With the fixed-schedule construction, the distinguishing advantage should fall to chance and utility should match published StaSwitch and TM figures. We will report maximum sustainable input rate, 99.999th-percentile per-slot compute time and the fixed added delay of $k + c$ against the padded baseline across $k$ from 4 to 1024.

The third check is the one we care most about. We look for a regime of $k$ and input rate that is realistic for one-minute clinical vitals or tick data, in which the de-amortized version is timing-safe while the padded baseline cannot keep up. If no such regime exists, the honest conclusion is that timer padding suffices, and the lasting contribution is the attack together with the schedule lemma.