Why does "sticky noise" defy averaging attack?

Question

I have read an interesting paper (pdf) describing how a privacy preserving technique might be breached, but I am having trouble understanding the following paragraph describing one of several layers of noise added to an observation.

Let C be a condition, e.g. "age = 34". The static noise associated with C is a random number drawn from a normal distribution N(0,1). The value is generated by a pseudo-random generator, whose seed is a salted hash of the string literal C:

static_seedC = XOR(hash(C), salt)

This ensures that the static noise associated with C is always the same independently from the query where C appears. The noise is "sticky" thereby preventing an attacker from sending the query many times and averaging the results to obtain a precise estimate of the private value ("averaging attack").

So if I understand correctly, the seed always generates the same number, let's say 0.4, so that C always becomes 34.4 instead of 34. If however C would sometimes be 33.9, 34.1, 34.2 and so forth, given enough trials the attacker would be able to draw a histogram which would be centered around 34 and infer that the age was 34?

If this is correct, can anyone please explain the equation above generating the noise (in this case the number 0.4)? I am not so familiar with the terms.

Answer 1

Full disclosure: I am one of the authors of the linked paper.

Your understanding is partially correct. I will explain more in detail how Diffix generates static noise.

Suppose that Diffix receives a query $Q$:

$$Q \equiv \quad \operatorname{count}(\ \textsf{age = 34} \quad \wedge \quad \textsf{gender = M}\ ).$$

$Q$ counts how many users (i.e. rows) in the database $D$ have age 34 and are male. We denote this number by $Q(D)$. Of course, $Q(D)$ is not necessarily 34 (this is the source of your misunderstanding).

In order to protect privacy, Diffix doesn't output $Q(D)$, but rather $Q(D) + \textit{noise}$. The $\textit{noise}$ is made of different noise layers: for each condition in $Q$, Diffix adds a static noise layer and a dynamic noise layer. $Q$ has two conditions, so the $\textsf{noise}$ will be made of $2 \times 2 = 4$ layers (i.e. noise values). Specifically, the output will be $\newcommand{\static}{\textsf{static}} \newcommand{\dynamic}{\textsf{dynamic}}$

\begin{align*} \widetilde{Q}(D) = Q(D) &+ \static[\textsf{age=34}] + \dynamic_Q[\textsf{age=34}] \\ &+ \static[\textsf{gender=male}] + \dynamic_Q[\textsf{gender=male}]. \end{align*}

To generate the noise value $\static[\textsf{age=34}]$, Diffix draws a number from a normal distribution $N(0,1)$. But Diffix makes sure that the value of $\static[\textsf{age=34}]$ is always the same (this is needed to protect privacy, see the paper for more details). In order to do this, Diffix uses a pseudo-random number generator, seeded essentially with a salted hash of the string $\texttt{'age=24'}$. You can read more about hashes, salts and PRNG on Wikipedia. But apart from technical details, the only thing you need to understand is that $\static[\textsf{age=34}]$ is immutable, meaning that its value stays the same for any query that contains the condition $\textsf{age=34}$. It would be absolutely equivalent to simply use a cache to store every noise value and reuse them every time the same condition is processed by Diffix.

The process to generate $\dynamic_Q[\textsf{age=34}]$ is similar, but here the seed depends also on the query set of $Q$. For details, please refer to the paper.

You can read a simplified version of the paper in our blog post.