Lowering the cost of anonymization

3.3.1  Preliminaries ✿

Many data analysis applications must count the number of distinct records in a large stream with repetitions. These applications include network monitoring [142], online analytical processing [309, 346], query processing, and database management [387]. A variety of algorithms, which we call cardinality estimators, have been developed to do this efficiently, with a small memory footprint. These algorithms include PCSA [154], LogLog [120], and HyperLogLog [152]. They can all be parallelized and implemented using frameworks like MapReduce [95]. Indeed, their internal memory state, called a sketch, can be saved, and sketches from different data shards can be aggregated without information loss.

Using cardinality estimators, data owners can compute and store sketches over fine-grained data ranges, for example, daily. Data analysts or tools can then merge (or aggregate) existing sketches, which enables the subsequent estimation of the total number of distinct records over arbitrary time ranges. This can be done without re-computing the entire sketch, or even accessing the original data.

Among cardinality estimators, HyperLogLog [152] and its variant HyperLogLog++ [195] are widely used in practical data processing and analysis tasks. Implementations exist for many widely used frameworks, including Apache Spark [18], Google BigQuery [48], Microsoft SQL Server [203], and PostgreSQL [318]. The data these programs process is often sensitive. For example, they might estimate the number of distinct IP addresses that connect to a server [369], the number of distinct users that perform a particular action [21], or the number of distinct devices that appeared in a physical location [286]. To illustrate this point, we present an example of a location-based service, which we will use throughout this section.

Fine-grained location data is inherently sensitive: it is extremely reidentifiable [171], and knowing an individual’s location can reveal private information. For example, it can reveal medical conditions (from visits to specialized clinics), financial information (from frequent visits to short-term loan shops), relationships (from regular co-presence), sexual orientation (from visits to LGBT community spaces), etc. Thus, knowing where a person has been reveals sensitive information about them.

As the above example suggests, an organization storing and processing location data should implement risk mitigation techniques, such as encryption, access controls, and access audits. The question arises: how should the sketches be protected? Could they be considered sufficiently aggregated to warrant weaker security requirements than the raw data?

To answer this question, we model a setting where a data owner stores sketches for cardinality estimation in a database. The attacker can access some of the stored sketches and any user statistics published, but not the raw data itself. This attacker model captures the insider risk associated with personal data collections where insiders of the service provider could gain direct access to the sketch database. In this paper, we use this insider risk scenario as the default attacker model when we refer to the attacker. In the discussion, we also consider a weaker attacker model, modeling an external attacker that accesses sketches via an analytics service provided by the data owner. In both cases, we assume that the attacker knows the cardinality estimator’s internals.

The attacker’s goal is to infer whether some user is in the raw data used to compute one of the accessible sketches. That is, they pick a target user, They choose a sketch built from a stream of users, and must guess whether their target is in this stream. The attacker has some prior knowledge of whether their target is in the stream, and examining the sketch gives them a posterior knowledge. The increase from prior to posterior knowledge determines their knowledge gain.

Consider Example 10. The attacker could be an employee trying to determine whether their partner visited a certain restaurant on a given day, or saw a medical practitioner. The attacker might initially have some suspicion about this (the prior knowledge), and looking at the sketches might increase this suspicion. A small, bounded difference of this suspicion might be deemed to be acceptable, but we do not want the attacker to be able to increase their knowledge too much.

Thus, our goal is to understand whether a realistic attacker could gain significant knowledge about a target by looking at a HyperLogLog sketch; or any other output from a different cardinality estimator.

Related work

Prior work on privacy-preserving cardinality estimators has been primarily focused on distributed user counting, for example to compute user statistics for anonymity networks like Tor. Each party is usually assumed to hold a set $X_i$ of data, or a sketch built from $X_i$, and the goal is to compute the cardinality of ${\bigcup }_i{X}_i$, without allowing the party $i$ to get too much information on the sets $X_j$ with $j\iff i$. The attacker model presumes honest-but-curious adversaries.

In [369], the authors propose a noise-adding mechanism for use in such a distributed context. In [279], each party encrypts their sketch, and sends it encrypted to a tally process, which aggregates them using homomorphic encryption. In [21], the authors propose a multiparty computation protocol based on Bloom filters to estimate cardinality without the need for homomorphic encryption, and in [136], this approach is shown to be vulnerable to attacks, and a more secure variant of the protocol is presented.

Some cardinality estimation protocols who achieve differential privacy have been proposed, based either on Bloom filters [9], FM-sketches [374]. However, these sketches cannot be aggregated without significant accuracy loss, or using secure aggregation methods in a multiparty setting; this last option is explored in [77] using LogLog sketches. Another line of research focuses on counting distinct elements in a scalable way, and making only the output differentially private, not the sketches itself [72].

Our attacker model, based on insider risk, is fundamentally different to these models: the same party is assumed to have access to a large number of sketches; they must be able to aggregate them and get good estimates. We claim that cardinality estimators must necessarily make a hard choice: the sketches can be made private, or they can be aggregated without catastrophic accuracy degradation, but both properties are mutually exclusive.

Our privacy definition for cardinality estimators is a variant of differential privacy, presented in Definition 6 (Section 2.1.6). It uses a data-generating probability distribution to capture the attacker’s uncertainty, in a similar way of variants introduced in Section 2.2.5. We explain in Section 3.3.1.0 why we need a custom privacy definition for our setup and how it relates to differential privacy and Pufferfish privacy (Definition 35, in Section 2.2.5.0). Some deterministic algorithms, which do not add noise, have been shown to preserve privacy under this assumption [36, 46, 176].

Our setting has some superficial similarities to the local differential privacy model, where the data aggregator is assumed to be the attacker. This model is often used to develop privacy-preserving systems to gather statistics [38, 40, 141, 146]. However, the setting and constraints of our work differ fundamentally from these protocols. In local differential privacy, each individual sends data to the server only once, and there is no need for deduplication or intermediate data storage. In our work, the need for intermediate sketches and unique counting leads to the impossibility result.

Finally, some work has been done on the security properties of HyperLogLog sketches, in particular their resistance to adversarial manipulation [330], this direction of research is largely orthogonal to the one studied in this work.

Cardinality estimators

In this section, we formally define cardinality estimators, and prove some of their basic properties. The notations introduced below, and used throughout this section, are summarized on page 35.

Cardinality estimators estimate the number of distinct records in a stream. The internal state of a cardinality estimator is called a sketch. Given a sketch, one can estimate the number of distinct records that have been added to it (the cardinality).

Cardinality estimator sketches can also be aggregated: two sketches can be merged to produce another sketch, from which we can estimate the total number of distinct records in the given sketches. This aggregation property makes sketch computation and aggregation embarrassingly parallel. The order and the number of aggregation steps do not change the final result, so cardinality estimation can be parallelized using frameworks like MapReduce.

We now formalize the concept of a cardinality estimator. The records of the multiset are assumed to belong to a large but finite set $T$.

These axioms state that $\mathrm{add}$ ignores duplicates and that the order in which records are added is immaterial. Ignoring duplicates is a natural requirement for cardinality estimators. Ignoring order is required for this operation to be used in frameworks like MapReduce, or open-source equivalents like Hadoop or Apache Beam. Since handling large-scale datasets typically requires using such frameworks, we consider commutativity to be a hard requirement for cardinality estimators.

We denote by $S_{t_1,\dots ,t_n}$ the sketch obtained by adding $t_1,\dots ,t_n$ successively to $S_{\text{∅}}$, and we denote by $S$ the set of all sketches that can be obtained inductively from $S_{\text{∅}}$ by adding records from any subset of $T$ in any order. Note that $S$ is finite and of cardinality at most $2^{\left|T\right|}$. Order and multiplicity do not influence sketches: we denote by $S_E$ the sketch obtained by adding all records of a set $E$ (in any order) to $S_{\text{∅}}$.

Later, we give several examples of deterministic cardinality estimators, all of which satisfy Definition 64.

In practice, cardinality estimators also have a $\mathrm{merge}$ operation. We do not explicitly require the existence of this operation, since $\mathrm{add}$’s idempotence and commutativity ensure its existence as follows.

Note that this construction is not computationally tractable in general, even though in practical scenarios, the $\mathrm{merge}$ operation must be fast. This efficiency requirement is not necessary for any of our results, so we do not explicitly require it either.

Note that these properties of the merge operation are important for cardinality estimators: when aggregating different sketches, we must ensure that the result is the same no matter in which order the sketches are aggregated.

Existing cardinality estimators also satisfy efficiency requirements: they have a low memory footprint, and $\mathrm{add}$ and $\mathrm{merge}$ run in constant time. These additional properties are not needed for our results, so we omit them in our definition.

We now define precise cardinality estimators.

Let us give a few examples of cardinality estimators, with their memory usage in bits ($m={\text{ln}}_2\left|S\right|$) and their relative standard error. As a first step, they all apply a hash function to the user identifiers. Conceptually, this step assigns to all users probabilistically a random bitstring of length 32 or 64 bits. Since hashing is deterministic, all occurrences of a user are mapped to the same bitstring.

• K-Minimum Values [29], with parameter $k$, maintains a list of the $k$ smallest hashes that have been added to the sketch. With $32$-bit hashes, it has a memory usage of $m=32\cdot k$, and its unbiased estimator has a RSE of approximately $\frac{1}{\sqrt{k}}\simeq \frac{5.66}{\sqrt{m}}$ [45].
• Probabilistic Counting with Stochastic Averaging [154] (PCSA, also known as FM-sketches) maintains a list of $k$ bit arrays. When an record is added to an FM-sketch, its hash is split into two parts. The first part determines which bit array is modified. The second part determines which bit is flipped to $1$, depending on the number of consecutive zeroes at the beginning. With $k$ registers and $32$-bit hashes, its memory usage is $m=32\cdot k$, and its RSE is approximately $\frac{0.78}{\sqrt{k}}\simeq \frac{4.41}{\sqrt{m}}$.
• LogLog [120] maintains a tuple of $k$ registers. Like PCSA, it uses the first part of the hash to pick which register to modify. Then, each registers stores the maximum number of consecutive zeroes observed so far. Using $k\ge 64$ registers and a $32$-bit hash, its memory usage is $m=5\cdot k$ bits, and its standard error is approximately $\frac{1.30}{\sqrt{k}}\simeq \frac{2.91}{\sqrt{m}}$.
• HyperLogLog [195] has the same structure and add operation as LogLog, only its estimate operation is different. Using $k\ge 16$ registers and a $64$-bit hash, it has a memory usage of $m=6\cdot k$ bits, and its standard error is approximately $\frac{1.04}{\sqrt{k}}\simeq \frac{2.55}{\sqrt{m}}$.
• Bloom filters can also be used for cardinality estimation [310]. However, we could not find an expression of the standard error for a given memory usage in the literature.

All these cardinality estimators have null or negligible ($\ll 1$) bias. Thus, their variance is equal to their mean squared standard error. So the first four are precise, whereas we do not know if Bloom filters are.

All examples above are deterministic cardinality estimators. For them and other deterministic cardinality estimators, bias and variance only come from the randomness in the algorithm’s inputs. We now define probabilistic cardinality estimators. Intuitively, these are algorithms that retain all the useful properties of deterministic cardinality estimators, but may flip coins during computation. We denote by $S$ the set of distributions over $S$.

These properties, like in the deterministic case, are very strong. They impose that an arbitrary number of sketches can be aggregated without losing accuracy during the aggregation process. This requirement is however realistic in many practical contexts, where the same sketches are used for fine-grained analysis and for large-scale cardinality estimation. If this requirement is relaxed, and the cardinality estimator is allowed to return imprecise results when merging sketches, our negative results do not hold.

For example, Tschorsch and Scheuermann proposed a cardinality estimation scheme [369] which adds noise to sketches to make them satisfy privacy guarantees in a distributed context. However, their algorithm is not a probabilistic cardinality estimator according to our definition: noisy sketches can no longer be aggregated. Indeed, [369] explains that “combining many perturbed sketches quickly drives [noise] to exceedingly high values.” In our setting, aggregation is crucial, so we do not further consider their algorithm.

Privacy for cardinality estimators

In this section, we describe our system and attacker model, and present the privacy definition we use in our setting.

Figure 3.7 shows our system and attacker model. The service provider collects sensitive data from many users over a long time span. The raw data is stored in a database. Over shorter time periods (e.g. an hour, a day, or a week), a cardinality estimator aggregates all data into a sketch. Sketches of all time periods are stored in a sketch database. Sketches from different times are aggregated into sketches of longer time spans, which are also stored in the database. Estimators compute user statistics from the sketches in the database, which are published. The service provider may also publish the sketches via an analytics service for other parties.

The attacker knows all algorithms used (those for sketching, aggregation, and estimation, including their configuration parameters such as the hash function and the number of buckets) and has access to the published statistics and the analytics service. They control a small fraction of the users that produce user data. However, they can neither observe nor change the data of the other users. They also do not have access to the database containing the raw data.

In this work, we mainly consider an internal attacker who has access to the sketch database. For this internal attacker, the goal is to discover whether their target belongs to a given sketch. We then discuss how our results extend to weaker external attackers, which can only use the analytics service. We will see that for our main results, the attacker only requires access to one sketch. The possibility to use multiple sketches will only come up when discussing mitigations strategies in Section 3.3.4.0.

Privacy definition

We now present the privacy definition used in our main result. Given the system and attacker just described, our definition captures the impossibility for the attacker to gain significant positive knowledge about a given target. This privacy requirement is very weak: reasonable definitions used for practical algorithms would likely be stronger. Working with a weak definition strengthens our negative result: if a cardinality estimator satisfying our weak privacy definition cannot be precise, then this is also the case for cardinality estimators satisfying a stronger definition.

This notion is a good example of the conclusion of Section 2.2: multiple variants and extensions of differential privacy are combined to find a definition that fits exactly to a specific use case. It has three important characteristics.

1.

No background knowledge: this definition assumes an attacker that has total uncertainty over the data: no record is known, and the input distribution is assumed to be completely uniform. The absence of any partial knowledge makes it a special case of definitions from Section 2.2.5; in Section 3.1.3, we saw that in this specific case, APK-DP and PPK-DP are equivalent. In practice, a realistic attacker might have more information about the data, so a stronger privacy definition would model this prior knowledge by a larger family of probability distributions. More precisely, since the records of $E$ are uniformly distributed in $T$, the prior knowledge from the attacker $P_n\left[t\in E\right]$ is exactly $\left|E\right|∕\left|T\right|$. A realistic attacker would likely have a larger prior knowledge about their target. However, any reasonable definition of privacy would also include the case where the attacker does not have more information on their target than on other users and, as such, would be stronger than $ϵ$-sketch privacy.

2.

Asymmetry: we only consider the positive information gain by the attacker. Following a reasoning to the prior-posterior bound property of DP shown in Section 2.1.6.0, $\epsilon$-sketch privacy imposes an upper bound on the probability that notion of knowledge gain is similar to the one in $t\in E$ given the observation $S$, but no lower bound. In other words, the attacker is allowed to deduce with absolute certainty that $t\notin E$. In practice, both positive and negative information gains may present a privacy risk. In our running example (see Example 10), deducing that a user did not spend the night at their place of residence could be problematic.

3.

Minimum cardinality: we only require a bound on the information gain for cardinalities larger than a parameter $N$. In practice, $N$ could represent a threshold over which it is considered safe to publish sketches or to relax data protection requirements. Choosing a small $N$ (like $N=10$) strengthens the privacy definition, while choosing a large $N$ (like $N=500$) limits the utility of the data, as many smaller sketches cannot be published.

The first characteristic is a variant of DP alongside our dimension B (Section 2.2.5), while the former two are reducing the scope of the definition in a similar way than variants from dimension N (Section 2.2.3). Later, in Section 3.3.3, we consider even weaker privation notions, by combining our definition with variants from dimensions Q (Section 2.2.2) and V (Section 2.2.4).

$\epsilon$-sketch privacy is trivially strictly weaker than differential privacy, and can almost be expressed as an instance of pufferfish privacy (Definition 35), except its asymmetry. It is immediate to show that $\epsilon$-sketch privacy satisfies both privacy axioms (Definition 9).

We emphasize again that these characteristics, which result in a very weak definition, make our notion of privacy well-suited to proving negative results. If satisfying our definition is impossible for an accurate cardinality estimator, then a stronger definition would similarly be impossible to satisfy. For example, any reasonable choice of distributions used to represent the prior knowledge of the attacker would include the uniform distribution.