# Matching Noisy Keys for Obfuscation

Charlie Dickens  Yahoo!
<EMAIL_ADDRESS>Eric Bax  Yahoo!
<EMAIL_ADDRESS>
###### Abstract

Data sketching has emerged as a key infrastructure for large-scale data
analysis on streaming and distributed data. Merging sketches enables efficient
estimation of cardinalities and frequency histograms over distributed data.
However, merging sketches can require that each sketch stores hash codes for
identifiers in different data sets or partitions, in order to perform
effective matching. This can reveal identifiers during merging or across
different data set or partition owners. This paper presents a framework to use
noisy hash codes, with the noise level selected to obfuscate identifiers while
allowing matching, with high probability. We give probabilistic error bounds
on simultaneous obfuscation and matching, concluding that this is a viable
approach.

###### Index Terms:

data sketches, big data, privacy, information theory

##  I Introduction

Large data sets are now used across a variety of domains, including
biosciences, language processing, and online advertising. Despite the variety
of applications, data analysis at scale often requires answering a common set
of similar queries for different data sets [1, 2, 3, 4]. For example,
estimating the number of unique identifiers in a dataset is called the _count
distinct_ problem. Another canonical problem is the _frequency estimation
problem_ – estimating the distribution of item frequencies over items in a
data set. For small data sets, these queries are simple to evaluate.

However, streaming and/or distributed data sets are much more challenging. For
them, there are a range of useful algorithms, known as _sketching_ algorithms
or _data sketches_ , that make a single pass through the data, in parallel for
distributed data sets, maintaining a small data structure in memory, called a
_sketch_. Sketches from multiple data sets can be merged to form a single
sketch for the combined data set, and sketches maintain data sufficient to
compute estimates that are accurate, with high confidence. Such mergeable
sketches have seen widespread use in industry, for example in Google’s
BigQuery engine [5] and in the open-source Apache DataSketches library [6].
After processing, a merged sketch can be stored independently of the sketches
from which it was built, and it can be used to answer multiple queries about
the entire data set.

Conceptually, traditional mergeable sketches operate in a paradigm where the
entity sketching the data is the same as the entity merging the sketches.
However, with changing privacy regulations [7], this assumption may be
invalid. For example, a multinational company may own data warehouses in
jurisdictions with differing privacy regulations which could prevent data-
sharing across geographies even within the same organization. Rather than
sending raw data, which could contravene regulation (and is slow at scale),
organizations can send sketches to efficiently answer queries over data from
multiple locations, if the data sketches can be shown to preserve privacy.
More generally, entities holding data may differ from the entity wishing to
answer a query. For example, an online advertising broker that runs campaigns
across different vendors needs to estimate statistics for advertising
campaigns over multiple vendors, yet the vendors want to avoid revealing
sensitive statistics or data to the broker or other vendors. As a solution,
vendors can send data sketches with sufficient noise to obfuscate each
vendor’s contribution to query results over the combined data. This has
prompted novel multiparty computation and communication models for aggregating
statistics, as presented in [8, 9, 10].

One challenge in developing such combined estimates is that merging many
sketches relies on a key feature of hashing: that the same input always maps
to the same output. Some sketches hash identifiers to produce hash codes, then
transmit hash code-value pairs as the sketch, where the value is a count or
some other number, for example Bottom-$k$–type sketches [11, 12, 13]. But
using the hash codes as keys to compare allows parties with the hash function
to hash identifiers and compare them to the hash codes transmitted in data
sketches. If they match, then the party can infer, with high probability, that
the identifier was contained in the data that generated the sketch. We address
the issue of key obfuscation in this paper which is necessary in sketches that
rely on key matching in the merge step such as [10, 13]. Data privacy research
more often addresses obfuscation of the values [14, 15] but both are important
in practice.

Our work addresses how to merge based on keys among _untrusted parties_ , to
understand how sketches with non-matching hashes can be merged. In particular,
we assume that entities sketching the data and merging the sketches do not
trust each other. This invalidates the approach of [16] who assume that the
hash function seed is a secret shared among those parties, and do not add
noise to the hash codes. While we use noise to achieve obfuscation, another
option is to encrypt the sketch prior to merging, but this is time- and
resource-intensive [10]. Our contribution is to design a noisy hashing scheme
that permits matching among noisy hashes and only has a small, controllable
probability of revealing any true hash code shared by two non-trusting
entities.

We achieve this by using a hash function with a seed shared among the parties,
but then having each party flip hash code bits uniformly at random with some
probability to add noise to each hash code. In general, distinct items tend to
have hash codes that disagree in about half their bits. We show that, given a
sufficient hash code bit-length and an appropriate probability of flipping
each bit when adding noise, all hash codes that did not originally match are
likely to maintain sufficient Hamming distance as noisy keys that considering
clusters of close noisy keys as matching sets is likely to have few or no
matching errors. Also given a sufficient hash code bit-length and bit-flipping
probability, we show that there is sufficient noise that the center of a
cluster of noisy keys is unlikely to match the hash code for the identifier
represented by the noisy keys. Finally, we complement the theoretical analysis
with a suite of characterizations showing how the performance varies depending
on practical considerations such as the noise probability over bits in the
hash code and the hash code length.

###  I-A Related Work.

For distinct counting, there is a variety of work focusing on obfuscation and
adding noise to obtain weak privacy [17, 18]. If sketches do _not_ have added
noise and use only a single, public hash function, then a series of merge
operations can identify the presence of an identifier with high confidence,
which is clearly undesirable from a privacy perspective [19]. If the hash
function seed can be kept secret and cryptographic hash functions are used,
then a wide class of practical sketches can be published under a strong
differential privacy guarantee [16, 14, 15]. When secretly seeded private
noise is combined with a public hash function strong differential privacy
guarantees are possible in some cases. These methods apply when sketch
contributors and the merger all trust one another.

Applying noise by using randomized response [20] bit-flipping permits merging
for the class of sketches [21] that store only bitmaps; including the
Flajolet-Martin sketch [22]. Other types of mergeable sketches that benefit
from strong differential privacy guarantees include linear sketches for
frequency estimation by adding noise to entries in the sketch [23, 24]. This
differs from simply adding noise to the estimator, as seen in [25, 8, 26],
which is not sufficient in the setting where merging sketches is required
because merging requires access to the sketch data structure.

Using a single public hash function is not a serious problem if sketches keep
only a single bit [21] or maintain additive increments in each bucket [23,
24], in which buckets can only increase in value by at most one based on an
update from a new or previously seen identifier hashing to that bucket. This
property, known as _low sensitivity_ , enables certain noise mechanisms to be
applied to the sketches prior to merging.

In addition to low sensitivity, the bitmap-style sketches of [21] and
frequency estimator sketches of [23, 24] benefit from another property: their
performance is not degraded by multiple identifiers hashing to the same
bucket. In [21], a bit is set from $0$ to $1$ if the corresponding bucket is
occupied by at least one item in the stream. The estimator needs the total
number of set bits and, crucially, does not depend on how many items have
caused a particular bit to be set. Similarly, the counting arrays in [23, 24]
rely on the Count(Min) arrays of [27, 28]. These arrays have an independent
hash function for each row to determine which rows in the array to increment.
Even if distinct items land in the same bucket in one row of the array, they
are unlikely to do so in further rows, enabling the estimate to compensate for
them easily. So keys are not required in the data sketch.

A mergeable sketch to estimate both frequency histograms111Note that frequency
_histogram_ and frequency _estimation_ differ in the sketching literature. The
latter asks us to estimate the frequency of any identifier in the data stream
while the former asks us to estimate the number of identifiers with a given
count in the stream. and distinct count in small space has been proposed by
[10]. The sketch maintains a one-dimensional array of counters whose buckets
are incremented by all items landing in that location and a hash function that
places exponentially more mass on low-index buckets. These buckets must be
resolved from those that have only a single identifier land there for later
estimation, unlike in the sketches listed previously. One issue with this
approach is that low-indexed buckets with a high probability of being occupied
have artificially large counts because multiple items are hashed to them. The
second issue is that their collision-resolution uses homomorphic encryption to
generate the keys that indicate which items are in each bucket. That requires
a further hashing step per update and suffers from the computational overhead
of encrypted arithmetic.

##  II Notation and Goals

Suppose we have a set of data sources, and each has a set of values. For each
value, the data source applies a hash function to get a hash code, then adds
noise to the hash code by randomly selecting whether to flip the bit (change
its value), independently for each bit in the hash code. The result is a noisy
key. Hash codes are generated by a public hash function accessible to and
computable by all sources. The noisy key is generated using independent,
private randomness for every source.

Next, all data sources transmit their noisy keys to a merge process. The merge
process clusters the noisy keys into clusters having zero or one noisy keys
from each data source. Informally, one goal is for the merge process to place
all noisy keys resulting from the same value into a cluster with no other
noisy keys, for each distinct value. If only one data source has a value, then
the goal is to place its noisy key into a “singleton cluster” with only that
noisy key. Another goal is for it to be difficult to infer the hash code for
any noisy key, even if each data source supplies a noisy key for the same
value.

Before formalizing those goals, we introduce some notation. For any pair of
values $v_{a}$ and $v_{b}$ from different data sources, let $a$ and $b$ be the
hash codes, and let $a^{\prime}$ and $b^{\prime}$ be the noisy keys. All data
sources use the same public hash function, so if $v_{a}=v_{b}$ then $a=b$.
Also, assume that if $v_{a}\not=v_{b}$, then each bit position in $a$ and $b$
has probability (over hash functions) one half of having equal bit values. Our
probabilities are over the choice of hash function as well as over random bit
flips.

We use $d(a,b)$ and $d(a^{\prime},b^{\prime})$ to represent Hamming distance –
the number of bit positions with unequal bit values. Informally, we say that
$d(a,b)$ is the number of disagreements between sequences $a$ and $b$. We
refer to the number of bit positions that have equal bit values as the number
of agreements. For example, $00011$ and $00110$ has Hamming distance 2,
because it has two disagreements (in the third and fifth positions).

Let $(a^{\prime},b^{\prime})$ be a pair of noisy keys with $a^{\prime}$ from a
different data source than $b^{\prime}$. Let $t$ be a matching threshold, and
declare $(a^{\prime},b^{\prime})$ a match if $d(a^{\prime},b^{\prime})<t$ and
unmatched otherwise. Define two types of events we wish to avoid or minimize:

  * •

$M$: $d(a^{\prime},b^{\prime})<t$ and $v_{a}\not=v_{b}$ – noisy keys match for
unequal values.

  * •

$U$: $d(a^{\prime},b^{\prime})\geq t$ and $v_{a}=v_{b}$ – noisy keys for equal
values are unmatched.

Given a set of noisy keys from the same value and the hash code for the value,
define the median key to be bit sequence with each position’s bit value equal
to the majority bit value in that position over the set of noisy keys, with a
tie broken in favor of the value in that position in the hash code.
Specifically, if $a_{i}^{\prime}=x$ and there are an equal number of bits $x$
and $1-x$ collected, then the value $x$ is reported as the median in position
$i$. Obfuscation fails if the median key is the same as the hash code. For
each noisy key, define event $R$ to be that the set of noisy keys that shares
its hash code has median key the same as that hash code.

In the following sections, we will analyze probabilities and expectations of
the undesirable events $M$, $U$, and $R$. Then we examine key lengths and
noise levels (in terms of bit-flipping probabilities) required for to control
the probabilities of those events.

##  III Mismatches and Missed Matches

Let $s$ be the number of data sources, and let $m_{i}$ be the number of noisy
keys from data source $i$ for $1\leq i\leq s$. Assume noisy keys from the same
data source result from distinct values. We are concerned with matching among
pairs of noisy keys from different data sources. Let $Q$ be the set of those
pairs. Since $Q$ is all pairs of noisy keys except those from the same data
source:

$|Q|={{\sum_{i=1}^{s}m_{i}}\choose{2}}-\sum_{i=1}^{s}{{m_{i}}\choose{2}}.$ (1)

Let $n$ be the length of each hash code and each resulting noisy key. Let
$p_{f}$ be the probability of flipping each bit while transforming a hash code
into a noisy key. Let $p_{\Delta}$ be the probability that bit-flipping alters
one bit but not the other in some position in a pair of noisy keys. Since
there are 2 choices for which bit to flip, and one must flip but not the
other,

$p_{\Delta}=2p_{f}(1-p_{f}).$ (2)

###  III-A Mismatches

Recall the binomial distribution’s probability mass function (pmf):

$b(k,n,p)={{n}\choose{k}}p^{k}(1-p)^{n-k}.$ (3)

And use $B(k_{o},k_{f},n,p)$ to denote the probability of a binomial random
variable having value in $[k_{o},k_{f}]$:

$B(k_{o},k_{f},n,p)=\sum_{k=k_{o}}^{k_{f}}{{n}\choose{k}}p^{k}(1-p)^{n-k}.$
(4)

Recall that $M$ is the event that for a pair $(a^{\prime},b^{\prime})\in Q$,
noisy keys $a^{\prime}$ and $b^{\prime}$ match, but they come from different
values.

######  Lemma 1.

Let

$p_{M}=\hbox{Pr}\left\\{d(a^{\prime},b^{\prime})<t|v_{a}\not=v_{b}\right\\}$
(5)

be the probability of a match given different values. Then

$p_{M}=B\left(0,t-1,n,\frac{1}{2}\right).$ (6)

###### Proof.

Recall that our probabilities are over selection of a hash function, and we
assume that assigns each bit either 0 or 1 with probability $\frac{1}{2}$ for
each value, independently over bits and between hash codes for
$v_{a}\not=v_{b}$. If the bit-flip probability $p_{f}$ is independent of
whether a bit has value 0 or 1, then, by symmetry, the probability of value 0
or 1 remains $\frac{1}{2}$ after random bit-flipping. To see this, the
probability of 0 is the probability of starting with 0 and not flipping the
bit plus the probability of starting with 1 and flipping the bit:
$\frac{1}{2}(1-p_{f})+\frac{1}{2}p_{f}=\frac{1}{2}$. ∎

###  III-B Missed Matches

Recall that $U$ is the event that $(a^{\prime},b^{\prime})\in Q$ are unmatched
and they come from the same value.

######  Lemma 2.

Let

$p_{U}=\hbox{Pr}\left\\{d(a^{\prime},b^{\prime})\geq t|v_{a}=v_{b}\right\\}.$
(7)

Then

$p_{U}=B(t,n,n,p_{\Delta}).$ (8)

###### Proof.

Since $v_{a}=v_{b}$, their hash codes are equal: $a=b$. So adding noise must
introduce at least $t$ disagreements to get $d(a^{\prime},b^{\prime})\geq t$.
For each bit position, the probability of introducing disagreement is
$p_{\Delta}$. ∎

###  III-C Matching Errors Over All Pairs

Since mismatches and missed matches are disjoint, the probability of either
happening is at most the maximum of their probabilities:

######  Lemma 3.

Let $p_{W}$ be the probability that a pair of noisy keys
$(a^{\prime},b^{\prime})\in Q$ has a mismatch or a missed match. Then

$p_{W}\leq\max(p_{M},p_{U}).$ (9)

###### Proof.

Note that

$p_{W}=\hbox{Pr}\left\\{M\lor U\right\\}.$ (10)

Since $M$ requires $v_{a}\not=v_{b}$ and $U$ requires $v_{a}=v_{b}$, they are
disjoint events and
$p_{W}=\hbox{Pr}\left\\{M\right\\}+\hbox{Pr}\left\\{U\right\\}$. Note that

$\displaystyle\hbox{Pr}\left\\{U\right\\}$
$\displaystyle=\hbox{Pr}\left\\{d(a^{\prime},b^{\prime})\geq t\land
v_{a}=v_{b}\right\\}$ (11)
$\displaystyle=\hbox{Pr}\left\\{d(a^{\prime},b^{\prime})\geq
t|v_{a}=v_{b}\right\\}\hbox{Pr}\left\\{v_{a}=v_{b}\right\\}$ (12)
$\displaystyle=p_{U}\hbox{Pr}\left\\{v_{a}=v_{b}\right\\}.$ (13)

Similarly,

$\hbox{Pr}\left\\{M\right\\}=p_{M}\hbox{Pr}\left\\{v_{a}\not=v_{b}\right\\}.$
(14)

So

$\displaystyle p_{W}$
$\displaystyle=\hbox{Pr}\left\\{M\right\\}+\hbox{Pr}\left\\{U\right\\}$ (15)
$\displaystyle=p_{M}\hbox{Pr}\left\\{v_{a}\not=v_{b}\right\\}+p_{U}\hbox{Pr}\left\\{v_{a}=v_{b}\right\\}$
(16)

But
$\hbox{Pr}\left\\{v_{a}\not=v_{b}\right\\}=1-\hbox{Pr}\left\\{v_{a}=v_{b}\right\\}$,
so

$p_{W}=p_{M}(1-\hbox{Pr}\left\\{v_{a}=v_{b}\right\\})+p_{U}\hbox{Pr}\left\\{v_{a}=v_{b}\right\\}.$
(17)

Since this is a convex combination,

$p_{W}\leq\max(p_{M},p_{U}).$ (18)

∎

Consider the expected number of matching errors of either type:

######  Theorem 1.

Let $w$ be the number of mismatches and missed matches over all pairs in $Q$.
Then

$\displaystyle\operatorname{\mathbb{E}}w$ $\displaystyle=p_{W}|Q|$ (19)
$\displaystyle\leq\max(p_{M},p_{U})|Q|$ (20)
$\displaystyle=\max(p_{M},p_{U})\left[{{\sum_{i=1}^{s}m_{i}}\choose{2}}-\sum_{i=1}^{s}{{m_{i}}\choose{2}}\right].$
(21)

###### Proof.

By linearity of expectations, the expectation over $Q$ is the probability for
each pair, $p_{W}$, times $|Q|$. For the second and third lines, apply Lemma 3
for $p_{W}$ and Expression 1 for $|Q|$. ∎

Now consider the distribution of the number of matching errors:

######  Corollary 1.

$\forall h\geq 0:\hbox{Pr}\left\\{w\geq
h\right\\}\leq\frac{\max(p_{M},p_{U})|Q|}{h}.$ (22)

###### Proof.

Apply Markov’s inequality to nonnegative random variable $w$, using Theorem 1
for the expectation. ∎

For the probability of no matching errors:

######  Corollary 2.

$\hbox{Pr}\left\\{w=0\right\\}\geq 1-\max(p_{M},p_{U})|Q|.$ (23)

###### Proof.

Apply Corollary 1, with $h=1$. ∎

##  IV Obfuscation

Recall that the median key for a set of noisy keys and a hash code that was
used to generate the noisy keys is defined as the bit sequence that agrees
with the majority of the noisy keys in each position, and agrees with the
original hash code in positions with a tie over the noisy keys. It is the
“best guess” for which hash code generated the noisy keys, with ties broken in
favor of guessing correctly, to be conservative. Also recall that event $R$
occurs for a noisy key if and only if the set of noisy keys with the same hash
code as the noisy key has median key equal to that hash code.

######  Lemma 4.

Let $p_{R}(z)$ be the probability that, for a set of $z$ noisy keys that have
the same hash code, for all $n$ positions, the median bit value is the same as
the bit value for that position in the hash code.

$p_{R}(z)=B\left(0,\left\lfloor\frac{z}{2}\right\rfloor,z,p_{f}\right)^{n}.$
(24)

###### Proof.

If there are at most $\lfloor\frac{z}{2}\rfloor$ bit flips, then the median
bit value remains the same as the hash code bit value. This is independent
among positions. ∎

For the expected number of noisy keys with hash codes “revealed” by median
keys: let $r$ be the number of noisy keys for which $R$ occurs.

######  Theorem 2.

Let $r$ be the number of noisy keys for which $R$ occurs. Then

$\operatorname{\mathbb{E}}r\leq\max_{z\in\left\\{1,\ldots,s\right\\}}p_{R}(z)\sum_{i=1}^{s}m_{i}.$
(25)

###### Proof.

Each noisy key may be in a set of from $1$ to $s$ noisy keys with the same
hash code. So $p_{R}(z)$ is its probability of $R$ for some
$z\in\left\\{1,\ldots,s\right\\}$. Relying on linearity of expectation, we can
sum those $p_{R}(z)$ values over the number of noisy keys. ∎

##  V Empirical Results

###  V-A Numbers and Figures

We now provide a series of plots illustrating the bounds derived in Section
III. Figure 1 shows key lengths sufficient to ensure 95% confidence that all
pairwise matches are correct (based on Corollary 2), given 95% confidence that
each median of matched noisy keys is not equal to its original key – so on
average 95% obfuscation (by Theorem 2). Each plotted value is for the worst-
case arrangement of matching values over the $s$ data sources (generally,
having full sets of $s$ matches) and for optimal bit-flip probability $p_{f}$
and matching threshold $t$. Noisy key lengths grow slowly in the number of
keys per data source ($m$), and somewhat aggressively in the number of data
sources contributing keys for matching ($s$). The key lengths are similar for
even $s$ values and the next odd values, because we assume that a median noisy
key with a tied number of zero and one values for a bit position is the same
as the original key’s bit value for the position, to be conservative.

Figure 1: Number of bits per noisy key ($n$) sufficient to achieve at least
95% confidence of no pairwise matching errors while maintaining a 95%
probability that the median of matched noisy keys does not match the original
key. In general, the key length grows with the number of data sources $s$. Key
lengths are nearly equal for each even $s$ and $s+1$, because we define each
median noisy key bit to have the bit value of the original key in case of a
tie in bit values over the set of noisy keys.

Figures 2 to 7 give a sense of the scales of probabilities of events $M$
(incorrectly matching different values), $U$ (incorrectly not matching two
keys of the same value), and $R$ (the median key reveals the true hash code),
and numbers of pairs of potential matches among noisy keys $|Q|$. Note that
most of the plots are logarithmic on the $y$-axis.

Figure 2 presents probabilities of $R$ – the event that the median key of a
set of noisy keys from the same value may reveal the hash code that generated
the key. That would allow anyone with the hash function and a value of
interest to test whether the value hashes to the revealed hash code. More
noise (higher bit-flip probability $p_{f}$) makes revelation less likely, as
does using more bits in the noisy keys, as it allows more opportunities for
some bit position to be flipped in the majority of the noisy keys from the
same value. Inspecting the pairs of curves for $p_{f}=0.09,p_{f}=0.18$ and
$p_{f}=0.12,p_{f}=0.24$ we see that the magnitude of the gradient increases by
roughly a factor five. This means that doubling the noise probability
increases the exponential rate parameter describing the probabilities by a
factor of roughly five. The plot is for 2 data sources.

Figure 2: Upper bound on probability that the median key for a noisy keys set
of matched noisy keys is equal to its hash code. More noise (higher bit-flip
probability $p_{f}$) makes this possibility to identify a noisy key’s hash
code less likely, and more bits in the noisy key ($n$) make it exponentially
less likely. (The values are for $s=2$ data sources.)

Figure 3 presents bit-flip probabilities $p_{f}$ required to achieve low
revelation probabilities as the bit sequence length varies. The probabilities
range from about a fifth to a third for $n=50$ bits per noisy key (on the
left) to about 5% to 10% for $1000$ bits per noisy key. The numbers presented
are for 2 data sources – they would increase with more data sources. Using
less noise makes correct matching more likely.

Figure 3: Minimum bit-flip probability to ensure the upper bound on revelation
probability ($p_{R}$) is at most some selected values. Achieving a revelation
probability bound less than 0.05 with fewer than 400 bits per noisy key
requires bit-flip probabilities at least 0.05. For 50 bits per noisy key (the
leftmost data points), a bit-flip probability of about 0.25 is required for a
revelation probability bound of 0.05. (The values are for a pair of data
sources.)

Figures 4 and 5 show probabilities of the incorrect matching events $M$ and
$U$ for each pair of noisy keys from different data sources. Event $M$ is an
incorrect match – matching noisy keys that result from different values, put
another way: failure to separate a pair of noisy keys that should not be
matched. Event $U$ is failure to match a pair of noisy keys that should be
matched. Failure to separate is independent of bit-flip probability $p_{f}$,
but failure to match depends on it. The $p_{f}$ values used for Figure 5 are
the minimums necessary to bound the revelation probability $p_{R}$ by 5% for 2
data sources.

Figure 4: Probabilities $p_{M}$, for each pair of noisy keys, that they are
matched, given that they should not be, that is, given that they are produced
from different values. Each line is for a procedure that declares a match if
fewer than the specified fraction of bits disagree. For each fraction, the
probability decreases exponentially in $n$ – the number of bits per noisy key.
Figure 5: Probabilities $p_{U}$, for each pair of noisy keys, that they are
left unmatched, given that they should be matched, since equal values produce
them. Each line is for a procedure that declares a non-match if at least a
specified fraction of bits disagree. For each number of bits in each noisy key
($n$), the probabilities shown are based on using the bit-flip probability
$p_{f}$ that required for a revelation probability ($p_{R}$) upper bound of
0.05, with a pair of data sources. Decreases in $n$ are super-exponential
because that $p_{f}$ value decreases with $n$, as shown in Figure 3.
Nonetheless, over 300 bits are needed per noisy key to make this probability
less than one in a billion, even if noisy keys match if they agree on only
three-quarters or more of their bits.

Figure 6 shows the probabilities of event $M\lor U$ – either type of matching
error – for each pair of noisy keys from different data sources, given that
bit-flip probability $p_{f}$ is large enough to ensure revelation probability
$p_{R}\leq 0.05$. The results shown are for the optimal choices among those
bit flip probabilities and matching threshold $t$ – the choices that minimize
the maximum of $p_{M}$ and $p_{U}$. Each line corresponds to a number of data
sources; as that number grows, the probabilities of matching errors increase
substantially, because $s$ data sources allows up to $s$ noisy keys for the
same value, making it more likely that the median of those keys is the same as
their (pre-noise) hash code, so forcing a higher bit-flip probability to
achieve a low revelation probability.

Figure 6: Probabilities $p_{W}$, for each pair of noisy keys, that they are
incorrectly matched – either matched though they have different values or left
unmatched though they have the same values. Each point is for the optimal
choice of bit-flip probability $p_{f}$ among those great enough to produce
revelation probability $p_{R}\leq 0.05$ and the optimal choice of matching
threshold $t\in\left\\{1,...,n\right\\}$. Each line shows results for a
different number of data sources $s$.

Figure 7 shows how the number of pairs of noisy keys from different data
sources grows as the number of keys per data source $m_{i}$ and the number of
data sources $s$ increase. The growth is sub-exponential in the number of keys
per data source, as it is O($ms^{2}$). In contrast, the values for $p_{M}$ and
$p_{U}$ decrease exponentially and super-exponentially, respectively, in the
number of bits per noisy key. This is promising as problem sizes increase,
since the product of these numbers bounds the expected number of matching
errors of any type (by Theorem 1) and the probability of any matching error
(by Corollary 2).

Figure 7: Numbers of pairs of noisy keys from different data sources. The
base-10 logarithm of the expected number of matching errors for 2 data sources
is at most the numbers plotted here plus the numbers on the line for $s=2$ in
Figure 6, according to Theorem 1. As an example, for 2 data sources and
$m_{1}=m_{2}=64\,000$ noisy keys (the point on the right of the lowest line in
this figure), the number of pairs $|Q|$ is between $10^{9}$ and $10^{10}$. For
noisy key length $n=400$ and $s=2$, Figure 6 shows that the error probability
for each pair is less than $10^{-13}$. So that gives an expected number of
matching errors on the order of $10^{-3}$, implying (via Corollary 2) about a
99.9% probability of correct matching.

###  V-B Discussion of Empirical Results

The empirical results show that noisy key lengths required for correct
matching with high probability while achieving 95% obfuscation grow slowly in
the number of keys per data source $s$ but aggressively in the number of
contributors $s$ wishing to protect their data from each other. At the high
end of the number of keys per source plotted (about $2^{16}$), the accuracy
compares favorably with LiguidLegions [10], which counts frequencies up to
about $10^{10}$ using $2^{16}$ keys with relative error about $2.5\%$. (As far
as we know, that is the only comparable method that merges noisy sketches for
frequency histogram estimation.) Although LiquidLegions uses $256$ bits per
key, their matching scheme relies on cryptographic functions that are slow to
evaluate. Regarding the number of contributors, sketches that offer privacy
consistently have performance degradation in the number of parties sharing
data [19, 10, 21], with noticeable losses in accuracy as the number of
contributors progresses from $2$. The amount of computation required for
merging with privacy can also increase substantially, for example if a
method’s cryptographic communication protocol requires computation that is
quadratic in the number of contributors [10]. Finally, the method of noisy
keys presented in this paper can be applied to key-based methods such as
Bottom-$k$ sketches [29, 11, 12] and the related Theta sketches [13, 6] that
use a fixed number of keys, which is convenient since it allows implementors
to determine sketch sizes a priori.

##  VI Conclusions and Future Work

We have examined how random bit flips can obfuscate hash codes and still allow
effective matching. We found that an upper bound on the probability that the
median of noisy keys from the same hash code reveals the hash code – the
revelation probability – implies a lower bound on the bit-flip probability
required, and that bound grows with the number of data sources and shrinks
with more bits per key. For matching error, selecting a threshold number of
bit positions that must agree to declare a match mediates a tradeoff between
two types of matching error – matching noisy keys that have different values
or failing to match those with the same value. The probabilities of both types
of errors decrease exponentially as key length (in bits) increases. And bit-
flip probability also plays a role in the probability of failing to match keys
from equal values.

There are two ways to view error probabilities – on a per-key or per-pair
basis, or as a probability that no such errors occur over all keys or pairs.
For revelation probabilities, we imposed per-key limits, meaning, for example,
an upper bound of 5% for revelation probability, which implies that, on
average, fewer than 5% of keys agree with their median keys. For matching
error probabilities, we analyzed per-pair probabilities and probabilities over
all pairs. For per-pair probabilities, the data for Figure 6 show that the
per-pair probability of either type of matching error is less than 5% (for
revelation probability at most 5%) for 100-bit keys for up to 5 data sources,
and 200-bit keys manage it for up to 10 data sources. However, achieving a low
probability that no noisy key pair has a matching error of either type
requires longer keys. For 2 data sources, achieving 95% confidence that
matching (or separation) is correct over all pairs requires about 300 bits for
a few thousand noisy keys per data source, about 350 bits for about 10,000
keys per data source, and about 400 bits for 40 to 60,000 keys per source.

Since one goal of sketching is to use data summaries that only require small
memory footprints, using many bits per key may be a concern. In practice, some
sketches use as few as 64 bits per key without noise and privacy [6, 13, 30].
However, it is known that more bits per key are needed for privacy deployments
and both [16, 10] use $256$ bits per key. Hence, there can be a cost (in bits)
for the obfuscation achieved through noise. On the other hand, the numbers of
bits detailed in this paper are total bits per key – not additional bits, so
any implementation using the number of bits detailed here or more would not
need to add bits per key.

Also, achieving high confidence that there are no pairwise matching or
separation errors may be a conservative requirement for achieving correct
matching, especially for greater numbers of data sources, which require longer
noisy keys. With several data sources, it should be possible to recover from
some matching errors. For example, with 5 data sources, if there are five
noisy keys resulting from the same value, then there are ${{5}\choose{2}}=10$
pairs among the noisy keys. If there are one or two errors, it may be possible
to infer that the five should match on the strength of the evidence that eight
or nine of the pairs match; and it is likely that the non-matching pairs would
have Hamming distances close to the threshold value $t$. More research is
needed to understand how different levels of pairwise errors affect the
accuracy of different matching methods.

## References

  * [1] A. Goyal and H. Daumé III, “Approximate scalable bounded space sketch for large data nlp,” in _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , 2011, pp. 250–261.
  * [2] A. Goyal, H. Daumé III, and G. Cormode, “Sketch algorithms for estimating point queries in nlp,” in _Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language learning_ , 2012, pp. 1093–1103.
  * [3] W. P. Rowe, “When the levee breaks: a practical guide to sketching algorithms for processing the flood of genomic data,” _Genome biology_ , vol. 20, no. 1, pp. 1–12, 2019.
  * [4] C. Kockan, K. Zhu, N. Dokmai, N. Karpov, M. O. Kulekci, D. P. Woodruff, and S. C. Sahinalp, “Sketching algorithms for genomic data analysis and querying in a secure enclave,” _Nature methods_ , vol. 17, no. 3, pp. 295–301, 2020\.
  * [5] “Bigquery: Hyperloglog++ functions.” [Online]. Available: https://cloud.google.com/bigquery/docs/reference/standard-sql/hll_functions
  * [6] “Apache datasketches.” [Online]. Available: https://datasketches.apache.org/
  * [7] R. Cummings and D. Desai, “The role of differential privacy in gdpr compliance,” in _FAT’18: Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 2018, p. 20.
  * [8] B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker, “On the power of multiple anonymous messages,” _arXiv preprint arXiv:1908.11358_ , 2019.
  * [9] H. Corrigan-Gibbs and D. Boneh, “Prio: Private, robust, and scalable computation of aggregate statistics,” in _14th USENIX symposium on networked systems design and implementation (NSDI 17)_ , 2017, pp. 259–282.
  * [10] B. Ghazi, B. Kreuter, R. Kumar, P. Manurangsi, J. Peng, E. Skvortsov, Y. Wang, and C. Wright, “Multiparty reach and frequency histogram: Private, secure, and practical.” _Proc. Priv. Enhancing Technol._ , vol. 2022, no. 1, pp. 373–395, 2022.
  * [11] Z. Bar-Yossef, T. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan, “Counting distinct elements in a data stream,” in _International Workshop on Randomization and Approximation Techniques in Computer Science_. Springer, 2002, pp. 1–10.
  * [12] E. Cohen and H. Kaplan, “Summarizing data using bottom-k sketches,” in _Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing_ , 2007, pp. 225–234.
  * [13] A. Dasgupta, K. Lang, L. Rhodes, and J. Thaler, “A framework for estimating stream expression cardinalities,” _arXiv preprint arXiv:1510.01455_ , 2015\.
  * [14] C. Dwork, “Differential privacy,” in _International colloquium on automata, languages, and programming_. Springer, 2006, pp. 1–12.
  * [15] C. Dwork, A. Roth _et al._ , “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [16] C. Dickens, J. Thaler, and D. Ting, “Order-invariant cardinality estimators are differentially private,” in _Advances in Neural Information Processing Systems_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35. Curran Associates, Inc., 2022, pp. 15 204–15 216. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2022/file/623307df18da128262aaf394cdcfb235-Paper-Conference.pdf
  * [17] S. N. von Voigt and F. Tschorsch, “RRTxFM: Probabilistic counting for differentially private statistics,” in _Conference on e-Business, e-Services and e-Society_. Springer, 2019, pp. 86–98.
  * [18] F. Tschorsch and B. Scheuermann, “An algorithm for privacy-preserving distributed user statistics,” _Computer Networks_ , vol. 57, no. 14, pp. 2775–2787, 2013.
  * [19] D. Desfontaines, A. Lochbihler, and D. Basin, “Cardinality estimators do not preserve privacy,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2019, no. 2, pp. 26–46, 2019.
  * [20] S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” _Journal of the American Statistical Association_ , vol. 60, no. 309, pp. 63–69, 1965.
  * [21] J. Hehir, D. Ting, and G. Cormode, “Sketch-flip-merge: Mergeable sketches for private distinct counting,” in _International Conference on Machine Learning_ , 2023.
  * [22] P. Flajolet and G. N. Martin, “Probabilistic counting algorithms for data base applications,” _Journal of computer and system sciences_ , vol. 31, no. 2, pp. 182–209, 1985.
  * [23] F. Zhao, D. Qiao, R. Redberg, D. Agrawal, A. El Abbadi, and Y.-X. Wang, “Differentially private linear sketches: Efficient implementations and applications,” in _Advances in Neural Information Processing Systems_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35. Curran Associates, Inc., 2022, pp. 12 691–12 704. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2022/file/525338e0d98401a62950bc7c454eb83d-Paper-Conference.pdf
  * [24] R. Pagh and M. Thorup, “Improved utility analysis of private countsketch,” in _Advances in Neural Information Processing Systems_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35. Curran Associates, Inc., 2022, pp. 25 631–25 643. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2022/file/a47f5cdff1469751597d78e803fc590f-Paper-Conference.pdf
  * [25] D. Mir, S. Muthukrishnan, A. Nikolov, and R. N. Wright, “Pan-private algorithms via statistics on sketches,” in _Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 2011, pp. 37–48.
  * [26] L. Melis, G. Danezis, and E. De Cristofaro, “Efficient private statistics with succinct sketches,” _arXiv preprint arXiv:1508.06110_ , 2015.
  * [27] M. Charikar, K. Chen, and M. Farach-Colton, “Finding frequent items in data streams,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2002, pp. 693–703.
  * [28] G. Cormode and S. Muthukrishnan, “An improved data stream summary: the count-min sketch and its applications,” _Journal of Algorithms_ , vol. 55, no. 1, pp. 58–75, 2005.
  * [29] K. Beyer, R. Gemulla, P. J. Haas, B. Reinwald, and Y. Sismanis, “Distinct-value synopses for multiset operations,” _Communications of the ACM_ , vol. 52, no. 10, pp. 87–95, 2009.
  * [30] S. Heule, M. Nunkesser, and A. Hall, “Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm,” in _Proceedings of the 16th International Conference on Extending Database Technology_ , 2013, pp. 683–692.