2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ From what you posted, it's not entirely clear to me how they're using the "static noise". It would be good to include a citation and link to the original paper. $\endgroup$ – user20160 May 3 '18 at 5:25
  • $\begingroup$ Regarding how they generate the static noise: The paragraph says they take the literal string "age=34" and run it through a hash function. They combine the hash output with salt using the bitwise exclusive or function. Salt is a fixed, random sequence of bits. The xor output is used as the seed for a pseudorandom number generator, which is used to generate the noise. $\endgroup$ – user20160 May 3 '18 at 5:25
  • $\begingroup$ Hi, I've added an answer to your question. Let me know if anything is not clear :) $\endgroup$ – aerdna91 May 10 '18 at 12:39
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great! I've also added the link to our blog post where we give a simplified explanation of the attack. $\endgroup$ – aerdna91 May 10 '18 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.