Securing Dynamic Data: A Primer on Differentially Private Data Structures

In 2006, Netflix released an anonymized dataset of movie ratings for a public competition. Although names were removed, it was later shown that users could be re-identified by linking the data with publicly available IMDb ratings [39]. This so-called (privacy) attack demonstrated the failure of traditional anonymization techniques, especially when different anonymized datasets are combined. It also highlighted the need for stronger privacy definitions that provide rigorous guarantees even when multiple analyses (or synthetic datasets) based on the same individual’s secret data are published.

This motivated the definition of differential privacy (DP), a privacy requirement for mechanisms introduced by Dwork, McSherry, Nissim, and Smith [17]. A differentially private mechanism¹¹1In theory, a common way to achieve differential privacy is by adding noise drawn from continuous distributions, such as the Gaussian distribution, when computing data analysis. However, exact sampling from continuous distributions is computationally infeasible. For this reason, the differential privacy literature typically avoids the term “differentially private algorithm” and uses the term “mechanism” instead. In practice, discrete approximations of these continuous distributions – implemented with finite precision – are used instead. adds randomness to the output in such a way that, for any two “neighboring” datasets, the resulting output distributions are “close”. Formally, the notion of neighboring datasets is defined as a binary relation on the family of datasets, and closeness of output distributions is defined by the following definition of indistinguishability:

Two datasets are typically considered to be neighboring if they differ by the presence or absence of a single data record. With this definition of neighboring, after observing the output of a differentially private mechanism, an attacker cannot confidently determine whether any specific data record was included in the input dataset. Let $𝒳$ denote the family of data records, and $\text{MS}(𝒳)$ denote the set of all multisets over $𝒳$. A differentially private mechanism is formally defined as follows:

Note that there exist problems that can be solved efficiently and with high accuracy in the non-private setting, but for which no differentially private solution exists. The interior point problem is an instance of this: Suppose the data universe $𝒳$ is totally ordered and datasets are multisets of size $n\in N$ over $𝒳$. An interior point mechanism takes a dataset $D$ as input and its goal is to return an element $y\in 𝒳$ such that $y$ is an interior point in $D$, i.e., ${\min }_{x\in D}x\le y\le {\max }_{x\in D}x$. An interior point mechanism is said to be accurate if for every input dataset, it returns an interior point of the dataset with probability at least $3/4$. Differential privacy for this mechanism is defined with respect to neighboring datasets that differ in exactly one element. Bun, Nissim, Stemmer, and Vadhan [6] showed that for any and , there exists no accurate interior point mechanism that satisfies $(ϵ,\delta )$-DP.

In many real-world applications, data is not available in a single static batch but is collected incrementally over time or the dataset is changing over time. In such settings, it is often necessary to update the output continually in order to provide timely and relevant analysis of the dataset. For example, an online movie platform may collect user interactions, such as who watches which movie, and update its recommendation model accordingly. In this scenario, the platform must ensure that the sequence of recommendations over time does not reveal sensitive information, such as whether a user has watched a specific movie. The problem of dynamically receiving data and updating the output while protecting the privacy of each data point is studied in the continual observation model of differential privacy [18, 10], which has recently become a popular research topic (see e.g. [8, 9, 26, 32, 33, 2, 1, 16, 31, 4, 23] for CMs for various problems on sequences of numbers, [34, 29, 46] for CMs for set cardinality, [11, 40, 14] for CMs for problems in databases, [7, 30] for CMs for various histogram queries, [42, 25, 26, 41, 22] for CMs for various graph problems, [15] for CMs for clustering problems in the Euclidean space, and [45, 5] for CMs for releasing synthetic data).

In the non-private setting, the goal is to design dynamic algorithms that are accurate, memory-efficient, and time-efficient. In the private setting, however, one must additionally ensure the privacy of the input data, which is always in conflict with accuracy. Nonetheless, with the emergence of new algorithmic techniques, several continual mechanisms have been developed that provide meaningful trade-offs between privacy and accuracy. These mechanisms have been shown to be practical and are already deployed in real-world systems [24, 3, 12, 13, 47, 48].

Formally, a mechanism $ℳ$ in the continual observation model is defined by a randomized function $f_{ℳ}$ that maps a current state and an incoming update to a new state and an output. The state represents the internal memory of the mechanism and may, for example, include the current dataset or relevant summary statistics. For simplicity, we assume the mechanism starts from an initial state corresponding to an empty dataset, though this assumption can be relaxed.

The mechanism $ℳ$ processes a sequence of update instructions $\sigma =(x_1,x_2,\mathrm{\dots })$ as follows²²2More generally, $ℳ$ can be an interleaved sequence of updates and (parametrized) queries, but for simplicity we just assume that one unparametrized query is fixed, and $ℳ$ answers that query after receiving each update.: Starting from the (empty) initial state, at each step $t$, the mechanism applies $f_{ℳ}$ to its current state and the incoming update $x_t$, yielding a new internal state and an output value $y_t$. $ℳ$ then returns $y_t$. We denote the sequence of outputs $(y_1,y_2,\mathrm{\dots })$ generated in response to the update sequence $\sigma$ by the random variable $ℳ(\sigma )$. We also refer to such a mechanism as a continual mechanism.

Depending on the problem definition, each update $x_i$ can be a data record in $𝒳$ to be inserted into the dataset or an instruction that arbitrarily modifies the current dataset (e.g., it deletes certain records). For simplicity, in the remainder of this section, we assume that each update $x_t$ is a data record in $𝒳$ to be inserted in the dataset. We note that all the definitions can naturally be extended to non-empty initial datasets and to general update operations.

Recall that in the non-interactive model, the differential privacy guarantee is defined over pairs of neighboring datasets. In the continual setting, on the other hand, the notion of neighboring is defined over sequences of data records. For example, if $𝒳=\{0,1\}$, we can define two sequences of data records $\sigma =(x_1,\mathrm{\dots },x_T)$ and ${\sigma }^{\prime }=(x_1^{\prime },\mathrm{\dots },x_T^{\prime })$ of equal length $T\in \mathbb{N}$ to be neighboring if they differ at exactly one position, i.e., there exists $i\in [T]$ such that $x_j=x_j^{\prime }$ for all $j\ne i$. Using this definition of neighboring in the definition of DP leads to so-called event-level privacy.

In the above definition, the continual mechanism is differentially private against an oblivious adversary. In the adaptive setting, however, an adversary generates neighboring sequences over time, adaptively, based on the previous outputs of the mechanism. Specifically, given a continual mechanism $ℳ$, an adversary $𝒜$ interacts with an oracle holding a secret bit $b\in \{0,1\}$. An oracle is a very limited algorithm that behaves as follows: At each time step, $𝒜$ issues a pair of updates $(u_0,u_1)$, and the oracle forwards $u_b$ to $ℳ$. Observing the corresponding output of $ℳ$, the adversary then adaptively generates the next pair of updates. If, at any time step, the sequences of $u_0$s and $u_1$s does not satisfy the required neighboring relation, the oracle halts the interaction.

We say that the mechanism $ℳ$ is $(ϵ,\delta )$-differentially private against adaptive adversaries if, for every adversary $𝒜$, the distributions of output sequences induced by oracle bits $b=0$ and $b=1$ are $(ϵ,\delta )$-indistinguishable.

The first and most foundational problem studied in the continual observation model is the continual binary counting problem. In this problem, the continual mechanism $ℳ$ receives a bit $x_t$ at each step $t\in \mathbb{N}$ and returns an estimate $y_t$ of the cumulative sum $s_t={\sum }_{i=1}^t{x}_t$. If $x_t$ is an arbitrary real number, the problem is called continual counting problem. Two input sequences of the same length are considered to be neighboring if they are identical except for a single time step. The goal is to guarantee differential privacy while providing accuracy, where accuracy is measured as follows:

First simple mechanism (Laplace mechanism on each output): A trivial design of a continual counting mechanism $ℳ$ is to run $T\in \mathbb{N}$ instances of the static Laplace mechanism to privatize the sums $s_t$ for $t\in [T]$. Specifically, at each step $t\in [T]$, the mechanism $ℳ$ computes $s_t$ and outputs $y_t=s_t+\text{Lap}(1/{ϵ}^{\prime })$, where $\text{Lap}(1/{ϵ}^{\prime })$ is a fresh sample of Laplace noise with scale $1/{ϵ}^{\prime }$. Since changing a single input bit affects each $s_t$ by at most $1$, by Lemma 9, the output at each individual step is ${ϵ}^{\prime }$-DP. Thus, applying basic composition (Lemma 4), the sequence of the first $T$ outputs is $T\cdot {ϵ}^{\prime }$-DP. To guarantee $ℳ$ is $ϵ$-DP, we must therefore set ${ϵ}^{\prime }=ϵ/T$. This implies that for each step $t\in [T]$, with a constant probability, $|y_t-s_t|=|\text{Lap}(T/ϵ)|$ is $\mathrm{\Omega }(T/ϵ)$.

Second simple mechanism (Laplace mechanism on each input) Another trivial approach is to run $T$ instances of Laplace mechanism on the input bits $x_t$ instead of $s_t$. That is, at each step $t\in [T]$, the continual counting mechanism $ℳ$ sets ${\widehat{x}}_t=x_t+\text{Lap}(1/ϵ)$. Since two neighboring input sequences (of length $T\in \mathbb{N}$) differ on at most one coordinate, all but one Laplace mechanism receive the same input for both sequences. Thus, by Lemma 9 and Lemma 4, the sequence $({\widehat{x}}_1,\mathrm{\dots },{\widehat{x}}_T)$ is $ϵ$-DP. Since the output sequence of $ℳ$ is computed as a post-processing of $({\widehat{x}}_1,\mathrm{\dots },{\widehat{x}}_T)$, by Lemma 3, it is distinguishable for two neighboring input sequences. Thus, $ℳ$ is $ϵ$-DP. At step $T$, $|y_T-s_T|$ equals the sum of $T$ i.i.d. samples from $\text{Lap}(1/ϵ)$. By a standard Chernoff bound, this implies that with high probability, $|y_T-s_T|$ is $\mathrm{\Omega }(\sqrt{T})$.

The two naive designs for continual counting illustrate a fundamental trade-off between privacy and accuracy. In the first approach, independent Laplace noise is added to each cumulative sum $s_t={\sum }_{i=1}^t{x}_i$. Since each input bit $x_i$ contributes to up to $T$ such sums, satisfying $ϵ$-differential privacy requires the Laplace scale to be $T/ϵ$. This, however, results in an additive error that grows linearly with $T$. In contrast, the second approach adds Laplace noise to each input bit $x_t$ individually and then sums the noisy inputs in a post-processing step. Here, each input only affects the output of a single Laplace mechanism, allowing for a smaller Laplace scale of $1/ϵ$. However, because the output at step $t\in [T]$ includes $t$ independent noise, the additive error grows polynomially in $t$.

To overcome this, Dwork, Naor, Pitassi and Rothblum [19] and Chan, Li, Shi, and Xu [10] proposed a new approach, the so-called binary (tree) mechanism, where each input bit is used in the input of $O(\log T)$ Laplace mechanisms, and each output is computed by summing $O(\log T)$ noisy values: Instead of adding noise to each individual bit or to every prefix sum, they add noise to sums of subsequences of the form $(x_{(k-1)\cdot 2^i+1},\mathrm{\dots },x_{k\cdot 2^i})$ for every $0\le i\le \log (T)$ and $1\le k\le T/2^i$. More precisely, at time step $k\cdot 2^i$ (i.e., when the complete subsequence is available), they calculate and store the noisy sum ${\sum }_{j=(k-1)\cdot 2^i+1}^{k\cdot 2^i}{x}_j+\text{Lap}(\frac{\log (T)+1}{ϵ})$. Then, to output the noisy cumulative sum at step $t\in [T]$, they partition the input sequence $(x_1,\mathrm{\dots },x_t)$ into at most $\log (T)$ disjoint subsequences of the above form and return the sum of their noisy values.

Another way to view this dynamic data structure is through a binary tree over time steps $1$ to $T$, where each node stores the noisy sum of the corresponding bits in its subtree, i.e., runs the Laplace mechanism on this partial sum. At each level of the tree, the input bits are partitioned between the nodes. Thus, the (parallel) composition of Laplace mechanisms at each level is $\frac{ϵ}{\log (T)+1}$-DP. Composing the $\log (T)+1$ levels and applying the basic composition theorem, we conclude that the joint output of all Laplace mechanisms is $ϵ$-DP. Since the noisy cumulative sum at every step is a post-processing of these noisy partial sums, this implies that the continual counter is $ϵ$-DP.

For the accuracy analysis, note that each output equals the true cumulative sum plus at most $\log (T)$ i.i.d. noise drawn from $\text{Lap}\left(\frac{\log (T)+1}{ϵ}\right)$. Chan et al. [10] showed that the sum of these $\log (T)$ Laplace random variables is $O(\sqrt{\log (T)}\frac{\log (T)+1}{ϵ}\sqrt{\log (1/\beta )})$ with probability at least $1-\beta$. Applying a union bound over all $T$ time steps, the maximum additive error across all steps is $O(\log {(T)}^{3/2}\sqrt{\log (T/\beta )}/ϵ)$ with probability at least $1-\beta$.

Consider a hospital that collected patient records during the Covid-19 pandemic, i.e., it has a static dataset. Over time, researchers may issue a sequence of statistical queries to investigate long-term effects of Covid and its potential correlation with current medical conditions. These queries are parametrized, meaning that they are given one or multiple parameters determining which query is asked, and these parameters are often chosen adaptively, meaning that the parameters for each new query may be chosen based on the responses to previous ones. To protect each patient record, queries must satisfy certain properties, e.g., an analyst cannot ask whether Mr. X had Covid or not.

In the DP literature, a mechanism that holds a static dataset and answers multiple adaptive queries is usually referred to as an interactive mechanism. To formally define differential privacy for the interactive setting, we need to define a view random variable: Let $ℳ$ be an interactive mechanism, and let $𝒜$ be an analyst (or adversary) that adaptively asks queries from $ℳ$. We denote the mechanism $ℳ$ holding dataset $D$ by $ℳ(D)$. The view of the analyst $𝒜$ interacting with $ℳ(D)$, denoted $\text{View}(𝒜,ℳ(D))$, is the sequence $(r_{𝒜},q_1,a_1,q_2,a_2,\mathrm{\dots })$ consisting of the analyst’s internal randomness $r_{𝒜}$ and the sequence of queries $q_i$ and corresponding answers $a_i$ returned by $ℳ$.

A fundamental problem in the interactive setting is threshold testing, where the mechanism holds a static dataset $D\in \text{MS}(\{0,1\})$ consisting of binary values, and receives a sequence of integer thresholds over time. Specifically, at each time step $t\in \mathbb{N}$, the analyst sends a threshold query ${\text{thresh}}_t\in \mathbb{N}$, asking whether the sum ${\sum }_{x\in D}x$ exceeds the given threshold ${\text{thresh}}_t$. The mechanism responds with either $\top$ (yes) or $\perp$ (no). Once the mechanism returns $\top$, it is required to halt. For simplicity, we assume the mechanism continues to return $\top$ indefinitely after it outputs $\top$ for the first time.

Two datasets $D_0,D_1\in \text{MS}(\{0,1\})$ are considered neighboring if they differ in the presence or absence of one element. The goal is to provide accurate answers to threshold queries while preserving privacy, where accuracy is defined as follows:

A well-known continual threshold-testing mechanism is the sparse vector technique (SVT) mechanism [19, 36]. The SVT mechanism allows an analyst to issue adaptive threshold queries on a static dataset while preserving differential privacy. This mechanism is described in Algorithms 1 and 2.

In Algorithm 1, the mechanism is initialized with a dataset $D$ and a privacy parameter $ϵ$. It first computes the true count $s={\sum }_{x\in D}x$ and then draws a sample $Z_0$ from $\text{Lap}(2/ϵ)$. This sample will be repeatedly used in all future comparisons. Upon receiving a threshold query ${\text{thresh}}_t$, the mechanism proceeds as follows (see Algorithm 2): If it has already returned $\top$ in any prior step, it returns $\top$. Otherwise, using the old noise $Z_0$ and a fresh noise $Z_t\sim \text{Lap}(4/ϵ)$, it compares $s+Z_0\ge {\text{thresh}}_t+Z_t$. If the inequality holds, then the mechanism returns $\top$ and sets a flag to indicate that it has exceeded a threshold; otherwise, it returns $\perp$.

In this section, we introduce new composition tools that enable a modular construction of complex continual mechanisms executing not only non-interactive mechanisms (NIMs) but also continual and interactive mechanisms as sub-mechanisms. As we mentioned before, the composition theorems presented in Section 1 only apply to NIMs. This raises a question: can interactive or continual sub-mechanisms always be decomposed into NIMs followed by post-processing, thereby enabling privacy analysis of the complex mechanism using composition theorems for NIMs and the post-processing lemma? We will first show that such a decomposition is not always possible and then present composition tools that simplify the privacy analysis of the mechanism with modular design. Due to complicated dependencies between the outputs and inputs of the sub-mechanisms and their potential influence on each other, analyzing the privacy of these mechanisms from scratch can be challenging.

Roughly speaking, interactive mechanisms can be viewed as a special case of continual mechanisms, where the first input update is a dataset and all subsequent updates are adaptively chosen queries with no effect on the dataset. When modeling an interactive mechanism as a continual mechanism, two input sequences are considered neighboring if their first element (i.e., the dataset) are neighboring, and all subsequent elements (i.e., the queries) are identical. This perspective allows us to unify continual and interactive mechanisms and refer to both of them as continual mechanisms (CMs).

Continual mechanisms are the analogue of dynamic data structures in the differentially private setting. Apart from analyzing their accuracy, time, and space requirements, their privacy properties need to be proven, which can be challenging. New composition theorems for continual mechanisms simplify this task and will hopefully support the design of continual mechanisms for various applications with improved tradeoffs between privacy and accuracy.