# Query sensitivity of time series under differential privacy

I stumbled upon a paper that proposes local DP around this argument:

• A user $$u_i$$ generates a sequence $$s_{i}$$ of observations at certain timestamps:

$$s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))$$

• The authors apply $$(\varepsilon/n, 0)$$-DP to each sequence by adding Laplacian noise
• As widely known, Laplacian must be of scale $$b = \frac{\Delta f}{ \text{budget}}$$

The authors propose budget of $$\varepsilon / n$$, which is IMO correct. But they also define $$\Delta f$$, aka the sensitivity of the query, as simply the range of any value at any timestamp, $$\text{max}(x) - \text{min}(x)$$.

I'm not convinced that this is the true sensitivity. To my understanding, the query output is (ignoring the timestamps) not a single value $$\mathbb{R}$$ but rather the vector of outputs $$\mathbb{R}^n$$, so per definition of sensitivity $$\ell_1$$-sensitivity of a function $$f : \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathbb{R}^k$$:

$$\Delta f = \max_{x, y \in \mathbb{N}; \| x - y\|_1 = 1} \| f(x) - f(y) \|_1$$

and properly computing the $$\ell_1$$ norm as $$\| x - y\|_1 = \sum_{i = 1}^{k} | x_i - y_i |$$, the sensitivity should be

$$(\text{max}(x) - \text{min}(x))^n$$

Is my reasoning correct (and the paper's DP potentially wrong), or am I missing something? (I don't reveal the paper on purpose.)

Update: Claryfing context of the time series.

The health data stream each user is represented as a sequence $$s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))$$

Here, $$(t_d, x_d)$$ represents the $$d$$-th point in the stream where $$x_d$$ denotes the value measured by the wearable health device at timestamp $$t_d$$.

We further assume that $$x_d$$, which is measured by the specific sensor in a wearable health device, is within the predefined range $$[x_{min}, x_{max}]$$.

Their particular use-case is collecting heart rate ($$x$$) over time ($$t$$).

## 2 Answers

I think you should explain what is $$x_i$$ in this time series. I would recommend linking the paper. I think without a strong context we could answer wrongly because maybe you could have understood something wrong as it has happened to me sometimes. Some points:

1. Query output could be $$\mathbb{R}$$ or $$\mathbb{R}^n$$, depends what kind of query you are defining and using.

2. You are right, I suspect they are defining a global sensitivity because maybe is easier to compute. But this depends on the kind of query they are defining on the paper, is a linear query, an only-one query or a non-linear query

• Thanks, I've updated the question, see above. Here's the paper's DOI: 10.1371/journal.pone.0207639 Commented Jan 25, 2021 at 12:38

I don't like answering my questions but it seems I misunderstood it and the authors are indeed correct.

Our query wants to obtain $$N$$ measurements from the database (database of size one but that's not relevant) with overall sensitivity budget $$\varepsilon$$. We can also split the single query into $$N$$ independent queries (more on the dependency below), where each query simply asks "What is the value at point $$n$$". Each of these $$N$$ queries has much smaller budget $$\frac{\varepsilon}{N}$$ which satisfies, by query composition, the overall budget $$\varepsilon$$.

Now each "small" $$n$$-th query has to satisfy $$(\frac{\varepsilon}{N}, 0)$$-DP, for which we need a mechanism and the sensitivity of this "small" query. In our case, the sensitivity is the range of values at point $$n$$, and the mechanism is Laplace as usual.

Regarding dependency between points $$x_n$$ and $$x_{n+1}$$. If we knew they are dependent, for example $$x_{n+1}$$ is simply $$2 \cdot {x_n}$$, we would only need to allocate the privacy budget $$\frac{2 \varepsilon}{N}$$ to $$x_n$$ and $$0$$ to $$x_{n + 1}$$. So the mechanism needs to randomize only $$x_n$$. But we pretend to have no knowledge whatsoever, i.e. the dependency of queries $$n$$ and $$n + 1$$, and expect the worst case by protecting each query independently. So even if $$x_n$$ and $$x_{n+1}$$ are 100% correlated, we add noise to each of them independently.

(I think a helpful visualization are two points in $$\mathbb{R}^2$$ and adding multivariate gaussian to each of them; correlated and uncorrelated, and look at the bounds of these two distribution in any point from the possible range)