# Local Differentially Private Fuzzy Counting in Stream Data using
Probabilistic Data Structures

Dinusha Vatsalan, Raghav Bhaskar, and Mohamed Ali Kaafar Dinusha Vatsalan is
with the Faculty of Science and Engineering, Macquarie University, Sydney,
Australia,
Email<EMAIL_ADDRESS>Raghav Bhaskar is with AppsPicket, New
Delhi, India,
E-mail<EMAIL_ADDRESS>Mohamed Ali Kaafar is with the Faculty of
Science and Engineering, Macquarie University, Sydney, Australia,
<EMAIL_ADDRESS>Manuscript received May 03, 2022; revised August
09, 2022.

###### Abstract

Privacy-preserving estimation of counts of items in streaming data finds
applications in several real-world scenarios including word auto-correction
and traffic management applications. Recent works of RAPPOR [1] and Apple’s
count-mean sketch (CMS) algorithm [2] propose privacy preserving mechanisms
for count estimation in large volumes of data using probabilistic data
structures like counting Bloom filter and CMS. However, these existing methods
fall short in providing a sound solution for real-time streaming data
applications. Since the size of the data structure in these methods is not
adaptive to the volume of the streaming data, the utility (accuracy of the
count estimate) can suffer over time due to increased false positive rates.
Further, the lookup operation needs to be highly efficient to answer count
estimate queries in real-time. More importantly, the local Differential
privacy mechanisms used in these approaches to provide privacy guarantees come
at a large cost to utility (impacting the accuracy of count estimation).

In this work, we propose a novel (local) Differentially private mechanism that
provides high utility for the streaming data count estimation problem with
similar or even lower privacy budgets while providing: a) fuzzy counting to
report counts of related or similar items (for instance to account for typing
errors and data variations), and b) improved querying efficiency to reduce the
response time for real-time querying of counts. Our algorithm uses a
combination of two probabilistic data structures Cuckoo filter and Bloom
filter. We provide formal proofs for privacy and utility guarantees and
present extensive experimental evaluation of our algorithm using real and
synthetic English words datasets for both the exact and fuzzy counting
scenarios. Our privacy preserving mechanism substantially outperforms the
prior work in terms of lower querying time, significantly higher utility
(accuracy of count estimation) under similar or lower privacy guarantees, at
the cost of communication overhead.

###### Index Terms:

Local Differential privacy, fuzzy counting, real-time querying, Cuckoo filter,
Bloom filter, data streams.

##  1 Introduction

The growing demand for real-time and faster analytics of continuously
generated big volumes of data brings tremendous interest in streaming data
technologies. However, privacy concerns in sharing or revealing personal
information require privacy preserving techniques to be designed for such
technologies. Privacy preserving counting of frequency of items in the data is
useful in several real-time streaming data applications.

An example application is word auto-correction that requires learning the
frequency counts of word entries by many different users such that when a user
enters a common/frequent word (e.g. LOL, according to a frequency threshold),
it will not be auto-corrected [2]. Another example is Web data obfuscation
application for privacy preserving Web browsing, which requires counting the
uniqueness of data entry or click path entered by all users in order to
calculate privacy risks and obfuscate accordingly in real-time [3]. In such
applications, data entries need to be continuously monitored from many users
111note that the frequency needs to be calculated across multiple users, i.e.
how many users have entered a certain data, not the frequency of a single user
and the auto-correction or auto-obfuscation function needs to query for the
frequency count information from many users in real-time and on-the-fly when a
user actively enters/types a data/word in an application. However, users’
individual data entries may identify their private and sensitive information,
for example, personal interests, occupation, health, or location, thereby
necessitating the use of privacy preserving techniques in the counting task.

There have been few methods proposed for the count-frequency problem in
streaming data including the two state-of-the-art methods with provable
privacy guarantees: RAPPOR (Randomized Aggregatable Privacy-Preserving Ordinal
Response) proposed by Google for collecting statistics from end-user client
software [1] and the count-mean sketch-based approach introduced by Apple to
discover frequency of words or emojis used by users [2]222From now onwards, we
may refer to the count-mean sketch-based approach introduced by Apple in [2]
as Apple’s algorithm. However, these methods are developed for offline
processing of count querying functions used for analytics purposes and not
tailored for real-time or online query processing. We aim to improve real-time
processing for count querying functions where the count queries need to be
answered in real-time and online. For example, in the auto-spelling correction
and privacy-aware Web data obfuscation applications (described above), the
decision to auto-correct words and obfuscate data needs to be retrieved by the
corresponding applications in near real-time when a user types a word in a
mobile App or enters data in the Web (e.g. a search query) [3].

Given sufficient time and resources, calculating frequency of items is a
simple task, i.e. just keeping a count of observations for each item in the
data to obtain that item’s frequency. However, in the context of high-scale,
low-latency, and online data processing, counts of items need to be calculated
instantly as the query comes in. The naive approach of randomly sampling the
observations for estimating the counts with the assumption that the sample
generally reflects the properties of the whole is not effective, as ensuring
true randomness is a difficult task. That is where probabilistic data
structures come in to estimate the approximate counts of items in an efficient
way [4, 5, 6]. Probabilistic data structures generally trade space and
computational efficiency for accuracy (false positive rate) of data
processing.

Google’s RAPPOR and Apple’s algorithm use the probabilistic data structures,
counting Bloom filter and count-mean sketch, respectively, for efficient
privacy preserving counting [1, 2]. For real-time count querying applications,
the lookup operational time is most crucial in order to answer the queries in
near real-time. The lookup operations in these probabilistic data structures
are dependent on the number of hash functions used and the size of the
probabilistic data structures. Reducing the number of hash functions and the
size of these probabilistic data structures can improve the lookup operation
in terms of query response time and space, however, it comes at a cost of
utility loss. Further, continuous insertion of data into these probabilistic
data structures leads to increasing probability of collisions of different
items and therefore impacts the false positive rate that eventually reaches to
$1.0$. In fact, our experimental results on large English words datasets show
that the false positive rate with the RAPPOR and CMS methods reaches to $1.0$
when approximately $100,000$ records are inserted (as presented in Section 4).

Moreover, in the example applications (described above), the same data
entered/typed by different users might have different variations or forms
(e.g. lemma) or errors (e.g. typos), and therefore exact counting does not
provide good utility of count estimation in these applications. Existing works
in privacy preserving counting allow only exact matching of items when
querying for frequency counts of items [2, 1]. Both [1] and [2] achieve local
Differential privacy guarantees for the data items contributed by the clients
by using variants of the Randomized Response [7] techniques. A key challenge
of using Differential privacy technologies is achieving a good balance between
privacy and utility guarantees.

In this paper, we propose a novel Differentially private counting algorithm
for real-time streaming applications that addresses all the above-described
limitations or shortcomings of the existing methods.

Contributions:

  1. 1.

We propose a Differentially private Cuckoo filter for efficient counting. The
lookup operation with cuckoo filter does not depend on the number of hash
functions nor the size of the filter, and thus is more efficient than other
probabilistic data structures in terms of lookup time and space [4].

  2. 2.

We overcome the issue of the impact of velocity of data on the utility (false
positive probability) by extending the cuckoo filter to be adaptive to large
volume of data that keeps the false positive rate bounded regardless of the
number of items inserted.

  3. 3.

Our algorithm allows efficient and effective fuzzy counting. We combine Bloom
filters [8] with cuckoo filters to allow fuzzy matching for counting of values
that are similar to each other or in a similar range.

  4. 4.

In order to reduce the loss in utility due to noise addition, i.e., to achieve
better trade-off between privacy and utility, we propose a novel local
Differential privacy mechanism for our method that instead of perturbing the
Bloom filter (encoded item) itself, adds noise to generate ”artificial” Bloom
filters as noise such that an adversary is unable to distinguish a real Bloom
filter from ”artificial” ones. In our method, noise is introduced to clients’
input via two steps: choosing the bucket positions of the cuckoo filter and
then choosing the corresponding Bloom filters that need to be sent for each of
those buckets. At most one of these Bloom filters comes from the real item and
all others correspond to “artificial” items. We provide formal proofs for the
privacy and utility guarantees of our method.

  5. 5.

Using real and synthetic English word frequency datasets, we conduct an
experimental study of our method and compare it to two state-of-the-art
methods, Google’s RAPPOR [1] and Apple’s algorithm [2]. Our experimental
results show that our method outperforms RAPPOR and Apple’s algorithm by a
large margin in terms of significantly higher accuracy of count estimation
with both exact and fuzzy counting cases (around 60% higher) and lower
querying time (more than one order magnitude lower cumulative time) with
similar privacy guarantees and insertion/update time. Since answering count
queries instantly and more accurately in online count querying applications
(e.g. word auto-correction or privacy-aware data obfuscation applications) is
critical, our method highly outperforms the state-of-the-art methods for such
applications.

Outline: We provide preliminaries in the following section and describe our
methodology in Section 3. In Section 4 we present the results of our
experimental study and in Section 5 we review the literature of privacy
preserving counting and Cuckoo filter techniques. Finally we conclude and
provide directions to future research in Section 6.

Figure 1: Fuzzy counting of string values (left) and numerical values (middle)
using Bloom filter encoding [6, 9], and fuzzy matching of Bloom filter
segments (right) used in our proposed fuzzy counting method described in
detail in Section 3.3.

##  2 Preliminaries

In this section, we describe some preliminaries of probabilistic data
structures in use, fuzzy counting, and the two state-of-the-art methods that
use probabilistic data structures and local Differential privacy for privacy
preserving counting.

###  2.1 Probabilistic data structures

In the context of high-scale, low-latency and online data processing
(virtually, there is never sufficient time nor resources), counts of items
need to be calculated instantly as the data streams in, regardless of its
scale. Hence, instead of accurately keeping track of each item, we estimate
the frequency using probabilistic data structures [4, 5, 6]. Probabilistic
data structures, such as Bloom filters and variants, sketches, and Cuckoo
filters, have recently received much attention, as they are highly efficient
for storing, processing, and computing [2, 1, 4, 5, 6].

Bloom filters: Bloom filters are bit vectors that initially contain $0$ in all
the bit positions. $k$ independent hash functions $h_{i}(\cdot)$ (with $1\leq
i\leq k$) are used to hash-map an element $x$ by setting the corresponding bit
positions in the Bloom filter $b$ to $1$ (i.e. $\forall_{i}~{}b[h_{i}(x)]=1)$.
A Bloom filter allows a tunable false positive rate $fpr$ so that a query
returns either “definitely not” (with no error), or “probably yes” (with
probability $fpr$ of being wrong). The lower $fpr$ is, the better utility is,
but the more space the filter requires. The false positive probability for
encoding $n$ elements into a Bloom filter of length $l$ bits using $k$ hash
functions is $fpr=(1-e^{-kn/l})^{k}$, which is controllable by tuning the
parameters $k$ and $l$.

######  Definition 2.1 (Exact vs. fuzzy counting:)

Given a list of items $X$ and a query item $x$, exact counting of $x$ is
$|\forall_{i\in X}~{}if~{}i==x|$, whereas fuzzy counting is $|\forall_{i\in
X}~{}if~{}sim(i,x)\geq s_{t}|$, where $|\cdot|$ denotes the cardinality of the
given set, $sim(\cdot)$ is a similarity function and $s_{t}$ is the minimum
similarity threshold.

The main feature of Bloom filter encoding that makes it applicable to
efficient fuzzy counting is that it preserves the similarity/distance between
an item and a queried item in the Bloom filter space (with a negligible
utility loss) [6, 9]. For example, with string values the $q$-grams (sub-
strings of length $q$) of string values can be hash-mapped into the Bloom
filter $b$ using $k$ independent hash functions [6], while for numerical
values, the neighbouring values (within a certain interval to allow fuzzy
matching) of values can be hash-mapped into the Bloom filter [9]. Figure 1
illustrates an example of fuzzy counting of string and numerical values using
Bloom filters [6, 9].

The similarity between Bloom filters can be calculated using a token-based
similarity function, such as Jaccard, Dice, or Hamming [10]. For example,
Dice-coefficient is used in Figure 1, which is calculated as
$2\times\frac{\sum(b_{1}\cap b_{2})}{\sum(b_{1})+\sum(b_{2})}$, where $b_{1}$
and $b_{2}$ are the two Bloom filters. Due to collision of different elements
being mapped to the same bit position that occurs during the hash-mapping
(depending on the parameter setting), the Bloom filter-based matching might
result in false positives. With appropriate parameter settings, Bloom filters
have shown to be successful in providing high matching results [6, 11, 9].
However, Bloom filters don’t allow storing the counts of items.

Counting Bloom filter is a variation of conventional Bloom filters which
allows storing counts as well as adding, deleting or updating of items. The
filter comprises an array of $t$-bit buckets. When an item is added, the
corresponding counters are incremented, and when it’s removed, the counters
are decremented. Consequently, a counting Bloom filter takes $t$-times more
space than a conventional Bloom filter, and it also has a scalability limit.
Count query for an element $x$ from a counting Bloom filter $cbf$ returns
$min(\forall_{i}~{}cbf[h_{i}(x)])$.

Figure 2: An overview of the proposed system for privacy preserving fuzzy
online counting in stream data.

Sketches: A sketch is an array that consists of $D$ rows and $W$ cells in each
row, initialized to 0, where $W$ and $D$ indicate the width and depth of the
sketch, respectively. Given a pair of parameters $(\theta,\delta)$, the sketch
parameters can be set as $W=\big{\lceil}e/\theta\big{\rceil}$ and
$D=\big{\lceil}ln(1/\delta)\big{\rceil}$, where $e$ is Euler’s number, and
$\theta$ and $\delta$ mean that the error in answering a query is within a
factor of $\theta$ with probability of $1-\delta$. In a count-min sketch, each
element is hashed by randomly chosen pairwise independent hash functions and
the corresponding cell values are incremented by the count of that element.
The maximum probability of any two different elements being hash mapped to the
same position is $1/W$ for each hash function, where $W$ is the width of the
sketch or the number of cells. The false positive probability $fpr$ for count-
min sketch is therefore, $fpr=[1-(1-1/W)^{n}]^{D}$, where $n$ is the number of
distinct elements stored in the sketch. Count query for an element $x$ from a
sketch $M$ returns $min(\forall_{i}~{}M[i][h_{i}(x)])$. Several methods based
on count-min sketch for the heavy-hitter problem were proposed [12, 13, 14].
The heavy-hitter problem is about identifying frequent elements from data, for
example IPs flooding in a network or over-consumed drugs to monitor disease
outbreak.

Cuckoo filter: The Cuckoo filter consists of a Cuckoo hash table that stores
the “fingerprints” of items inserted. The fingerprint of an item is a bit
string derived from the hash of that item. A Cuckoo hash table consists of an
array of buckets where an item to be inserted is mapped to two possible
buckets based on a hash function $h(\cdot)$. Each bucket can be configured to
store a variable number of fingerprints. To insert an item $x$ into the Cuckoo
filter, two indices need to be derived from the item based on hashing the item
and its fingerprint:

$\displaystyle i1=h(x),$ (1) $\displaystyle i2=i1\oplus h(fp(x)),$

where $h(\cdot)$ and $fp(\cdot)$ are the hash and fingerprint functions,
respectively.

On obtaining these indices, the item’s fingerprint ($f=fp(x)$) is inserted
into one of the two possible buckets that correspond to the derived indices.
$fp(\cdot)$ is used for space efficiency of the Cuckoo filter (depending on
the fingerprint size) [4]. As the Cuckoo hash table begins to fill up, it
encounters a situation where the two possible indices that an item can be
inserted has been filled. In this case, items currently in the Cuckoo hash
table are swapped (until the maximum number of swaps is met) to their
alternative indices to free up space for inserting the new item. Querying the
count of an item requires checking the two possible buckets for the
fingerprint of the item.

###  2.2 State-of-the-art methods

The two state-of-the-art methods for probabilistic privacy preserving counting
are: (1) Google’s RAPPOR that uses Bloom filter and counting Bloom filter for
collecting statistics about end-user software [1], and (2) Apple’s algorithm
presented in [2] that uses Count-mean Sketches (CMS) to learn frequency of
words, or web domains or emojis to e.g. determine the most popular emoji used
by individuals or to identify high energy and memory usage in Apple’s web
browser. Both of these methods only allow offline and exact count querying.
Cuckoo hashing/Cuckoo filter has been used in several private set intersection
applications [15, 16, 17, 18, 19] due to its significant space and time
efficiency compared to other probabilistic data structures [4]. However,
Cuckoo filter has not been studied for privacy preserving counting.

###  2.3 Differential Privacy

Differential privacy [20, 21, 22] guarantees for each individual in a dataset
that any information that could be discovered about an individual with their
data in the dataset could also, with high probability, be discovered without
their data in the dataset. That is, the output of any query $f$ performed on
dataset $x$ will be indistinguishable from the output of the same query $f$
performed on dataset $y$, where $y$ differs from $x$ by at most one record
(the record of any individual).

######  Definition 2.2 (Differential Privacy [20])

A randomized function $\mathcal{A}$ (i.e. a function with a randomized
component) is $\epsilon$-Differentially private if for all outputs $y\subseteq
Range(A)$ and for all data $x$, $x^{\prime}\in\mathcal{D}^{n}$ such that
$||x-x^{\prime}||_{1}\leq 1$:

$Pr(\mathcal{A}(x)=y)\leq e^{\epsilon}\times Pr(\mathcal{A}(x^{\prime})=y).$
(2)

The general differential privacy notion is defined for algorithms with input
databases of size larger than 1. Local differential privacy (LDP) is a
differential privacy model developed specifically to provide guarantees such
that even if an adversary has access to the individual records/data in the
dataset, the adversary is still unable to learn additional information about
the individual from the individual data with high probability [23]. It ensures
differential privacy guarantees for each individual’s inputs by processing
(perturbing) the data locally on-device rather than processing in the central
server. LDP has become the de-facto privacy standard around the world in
recent years, with the technology companies Google and Apple implementing LDP
in their latest operating systems and applications [1, 2, 24].

Assume two adjacent streams of data where the two data streams differ at most
by one record or item:

######  Definition 2.3 (Local Differential Privacy [20])

Let $\mathcal{A}:\mathcal{D}\rightarrow\mathcal{Y}$ be a randomized algorithm
mapping a data entry in $\mathcal{D}$ to $\mathcal{Y}$. The algorithm
$\mathcal{A}$ is $\epsilon$-local differentially private if for data entry
$x,\neg x\in\mathcal{D}$ and all outputs $y\in\mathcal{Y}$,

$-\epsilon\leq\frac{Pr[\mathcal{A}(x)=y]}{Pr[\mathcal{A}(\neg
x)=y]}\leq\epsilon$ (3)

RAPPOR uses the randomized response method to achieve $\epsilon$-LDP by
flipping bits in the Bloom filters of encoded items sent by the data clients
to the server for updates. Apple’s count mean sketch aggregation proposes to
flip the bits in vectors with probability $1/(e^{\epsilon/2}+1)$ to meet
$\epsilon$-LDP guarantees.

##  3 Methodology

In this section, we describe our proposed method for privacy preserving real-
time and fuzzy counting in stream data using Cuckoo filter and Bloom filter.
The proposed system overview is shown in Figure 2. At the client-side, new
items are encoded, perturbed, and sent to the server, while at the server-side
the (perturbed) items are stored in Cuckoo filter which allows fuzzy matching
for count querying (similar) items. We first describe the space and time-
efficient probabilistic data structure, Cuckoo filter, for enhanced efficiency
for processing streams of data, and we make the filter adaptive to continuous
flow of data. We then propose a novel local Differentially private algorithm
for cuckoo hashing of encoded (into Bloom filters) items, and finally, we
describe how Bloom filters can be combined with Cuckoo filters to allow fuzzy
matching for querying of counts in the presence of data errors and variations.
Algorithm 1 outlines the insertion step, Algorithm 2 presents the steps of
local Differential privacy mechanism, while Algorithm 3 outlines the querying
step (lookup operation) using fuzzy matching. Algorithms 1 and 3 are used by
the server while Algorithms 1 and 2 are used by the users/data custodian
before sending the items to the server for insertion/update.

###  3.1 Efficient and Adaptive Filter

Cuckoo filter consists of an array of buckets where an item $x$ is hash-mapped
by inserting the fingerprint ($fp(\cdot)$) of $x$ into one of two possible
buckets based on a hash function $h(\cdot)$, which are $h(x)$ and $h(x)\oplus
h(fp(x))$. In our proposed method, we insert Bloom filter encoding of the item
into the Cuckoo filter (i.e. $x^{\prime}=bf(x)$, where $bf(\cdot)$ is the
Bloom filter encoding function as described in Section 2). Bloom filter
encoding preserves the distances/similarities between items in the original
space, and therefore allows fuzzy matching (as will be discussed in Section
3.3) as well as enables adding noise to perturb data in the differential
privacy mechanism without significant impact on utility loss (as will be
described in Section 3.2). Our method hashes segments of Bloom filters into
the Cuckoo filter (as shown in lines 1-3 in Algorithm 1), such that more
similar items will have more number of similar Bloom filter segments hashed
into the Cuckoo filter.

Algorithm 1: Insertion (Client-side and server-side)
---
Input:
\- $x$: A data/element
\- $m$: Number of Bloom filter segments
\- $bf(\cdot)$: Bloom filter encoding function
\- $h(\cdot)$: Hash function
\- $fp(\cdot)$: Fingerprint function
\- $max\\_num\\_kicks$: Maximum number of kicks to relocate items
Output:
\- $\mathbf{C}$: Updated Cuckoo filter
Client-side: |
1: | $x^{\prime}=bf(x)$ | // Bloom filter encoding
2: | $bf\\_segs=x^{\prime}.segment(m)$ | // Split into m segments
3: | $send\\_to\\_server(bf\\_segs)$ | // Send to server
Server-side: |
4: |  for $bf\\_seg\in bf\\_segs$ do: | // Iterate segments
5: |  $f=fp(bf\\_seg)$ | // fingerprint
6: |  $i1=h(bf\\_seg)$ | // First bucket index
7: |  $i2=i1\oplus h(f)$ | // Second bucket index
8: |  if $\mathbf{C}.bucket[i1]~{}not~{}full$ then |
9: |  $\mathbf{C}.bucket[i1].add(f)$ | // Add to first bucket
10: |  else if $\mathbf{C}.bucket[i2]~{}not~{}full$ then |
11: |  $\mathbf{C}.bucket[i2].add(f)$ | // Add to second bucket
12: |  else |
13: |  $i=random(i1,i2)$ |
14: |  for $n=0;n\leq max\\_num\\_kicks$ do | // Relocate items
15: |  $f^{\prime}=random(\mathbf{C}.bucket[i])$ |
16: |  $f,f^{\prime}=f^{\prime},f$ | // Swap values
17: |  $i=i\oplus h(f)$ |
18: |  if $\mathbf{C}.bucket[i]~{}not~{}full$ then |
19: |  $\mathbf{C}.bucket[i].add(f)$ | // Add f to bucket i
20: |  $break$ | // Exit loop
21: |  $insertion=fail$ | // Insertion failed
22: |  if $insertion==fail$ then |
23: |  $\mathbf{C}.bucket\\_size+=\mathbf{C}.bucket\\_size$ | // If full, adaptive filter
24: |  $\mathbf{C}.bucket[i1].add(f)$ | // Add to bucket i1
25: |  return $\mathbf{C}$ |  // Output $\mathbf{C}$

Cuckoo filters have been shown to be more efficient than Counting Bloom
filters and Count-min Sketches in terms of space size and lookup operations
[4]. The space cost, in bits, of storing one item in the Cuckoo filter depends
on the target false positive rate $fpr$ and is given by
$(log_{2}(1/fpr)+2)/\alpha$, where $\alpha$ is the load factor of the filter
which defines the maximum filter capacity. The false positive probability
$fpr$ of Cuckoo filters where an element $x$ has the same fingerprint as
another element $y$ and shares one of $x$’s buckets is $fpr=[2/O\times
1/2^{F}]$, where $O$ is the number of filled/occupied buckets and $F$ is the
fingerprint size. With increasing $O$, the $fpr$ increases.

To account for the impact of continuous flow of data on the false positive
rate $fpr$, we make Cuckoo filter adaptive with regard to the size of the
buckets in the filter. In contrast to Bloom filters and sketches, cuckoo
filters can be adaptive to increasing volume of data insertions. With Bloom
filters or sketches (as used by RAPPOR [1] and Apple’s algorithm [2],
respectively), it is not trivial to increase the size of these data structures
to be adaptive, without re-hashing all the previously stored items in these
data structures, and as a result the false positive rate increases with large
number of items insertion and finally reaches to $1.0$. While with cuckoo
filters, the bucket size can be incrementally increased depending on the
percentage of occupied buckets. If the filter is considered to be mostly
occupied (full), then the length or size of the buckets is increased
adaptively. Upon failure of an element insertion due to $O$ is large and
exceeds $\alpha$ and therefore an empty space is not found until the maximum
number of swaps is performed, we increment the filter’s bucket size by the
default size and continue with the insertion until $O$ remains less than
$\alpha$ (lines 22-24 in Algorithm 1).

The lookup operation for querying an item $x$ in the adaptive Cuckoo filter is
still only in 2 buckets ($h(bf(x))$ and $h(bf(x))\oplus h(f(bf(x)))$), however
the number of lookup items in each bucket increases in the adaptive filter
with the increasing number of records being inserted into the filter.

Algorithm 2: Noise addition for local differential privacy (Client-side)
---
Input:
\- $x$: A data/element
\- $bf(\cdot)$: Bloom filter (BF) encoding function
\- $h(\cdot)$: Hash function
\- $\epsilon$: Privacy budget
\- $s_{t}$: Minimum similarity threshold
\- $p$: Probability to flip bits $p=\frac{1}{1+s.e^{\epsilon}}$ where
$s=\frac{2^{l.(1-s_{t})}.B}{2^{l}}$ (Thm 3.1)
\- $F^{\prime}$: Corresponding fingerprints for each bucket
Output:
\- $V^{\prime}$: Perturbed vector containing fingerprints
1: | $x^{\prime}=bf(x)$ |  //BF of $x$
2: | $i1=h(x^{\prime})$ | //First bucket
3: |  $V=\\{-1\in\mathbb{R}^{B}$} | //Initialize a vector
4: | $V[i1]=+1$ |
5: |  $N\in\\{-1,+1\\}^{B}$, $Pr[n\in N=+1]=1-p$ | //Noise vector
6: | $V=[v_{1}n_{1},\cdots,v_{B}N_{B}]$ | //Flipping bits
8: |  for $v\in V$ do |
9: |  if $v==i1$ then |
10: |  $\tilde{x^{\prime}}=generate\\_similar\\_bf(x^{\prime},s_{t})$ |  //similar BF with $s_{t}$
11: |  $V^{\prime}.add(\tilde{x^{\prime}})$ |  //Add similar BF $\tilde{x^{\prime}}$
12: |  else |
13: |  $x"=randomly\\_choose\\_from(F^{\prime}[r])$ | //Corresponding BF
14: |  $V^{\prime}.add(x")$ | //Add artificial BFs
15: |  return $V^{\prime}$ |  //Send $V^{\prime}$ to server

###  3.2 Privacy Guarantees

Similar to [2], the threat model of this research problem is as follows:
encoded data (Bloom filters) of unique/new items from each client or custodian
are continuously being sent to the (untrusted) server to be stored or updated
in the cloud. Note that, in contrast to the problem addressed in [1], each
client needs to report only unique items (i.e. if the item is not already
reported by that client), and therefore the clients locally keep track of the
unique items reported to the server. When a data consumer/query issuer (for
example, a researcher who wants to identify the most popular emojis used by
many users) queries the frequency counts of the items in the cloud from all
users, the estimated counts are revealed. We assume the server is untrusted
and the server knows the hash function used by data custodians.

The privacy preserving context for this problem requires that the server or
the consumer of the protocol (query issuer) should not learn individual users’
membership information of an item from the data, and an eavesdropper who gets
access to the communication channel or to the server should not be able to
learn the items about any individual users. However, the encoded data (Bloom
filters) sent by custodians/clients can leak some information about individual
users by performing a frequency attack [25] or dictionary attack using the
hash encoding functions on some known values [10].

The domain space of the items is generally well-known and some of the items
are considered to be highly sensitive. For example, if the application is
counting the frequency of words entered by data custodians, some of the words
such as related to cancer illness, are considered to be highly confidential
for data custodians and therefore identifying a certain data custodian has
typed words related to cancer illness raises serious privacy issues. Bloom
filter encoding can be applied on the known (and sensitive/confidential) items
from the problem domain to match the incoming Bloom filter encodings from
different data custodians in order to infer the presence of a sensitive item,
or they can be inferred using the frequency distribution of bit patterns
(known as cryptanalysis attack [25]).

####  3.2.1 Local Differential privacy

Perturbing the bits in the Bloom filter itself incurs significant amount of
utility loss. Even a single bit difference can correspond to completely
different item values. Therefore, in our method clients do not add fake
“artificially-crafted” bits in the Bloom filters, but they send possibly
multiple Bloom filters even when there is a single true item.

Pre-processing: As an offline and one-time pre-processing step, at the client-
side a dictionary $F^{\prime}$ containing corresponding Bloom filters for each
of the $B$ bucket is generated. All the possible bit patterns of length $l$
with random 1’s and 0’s ($2^{l}$ in total) are generated and assigned to the
two corresponding bucket indices ($i1$ and $i2$) based on the $h(\cdot)$ and
$fp(\cdot)$ functions.

Online processing: For every incoming item the real bucket index is first
represented as a one-hot vector containing 1 at the position corresponding to
the real bucket and -1 elsewhere. Randomised response noise mechanism is
applied to this vector using our flipping probability
$P_{flip}=\frac{1}{1+s.e^{\epsilon}}$, where $s=\frac{2^{l.(1-s_{t})}}{t}$,
and $t=2^{l}/B$, derived from Theorem A.1 (as will be detailed below). Clients
then send a Bloom filter corresponding to each bucket which is flipped to 1.
For all the buckets other than the real bucket, a random Bloom filter chosen
from the pre-computed dictionary for that bucket is sent. For the real bucket
though, if the bit is not flipped to 0, a randomly chosen Bloom filter at
distance of minimum similarity threshold $s_{t}$ and maximum $1.0$ is sent.
The steps of our local Differential privacy mechanism are outlined in
Algorithm 2:

  1. 1.

For the actual item x, the Bloom filter $x^{\prime}=bf(x)$ and bucket position
$i1=h(x^{\prime})$ are computed (lines 1-2 in Algorithm 2).

  2. 2.

A one-hot vector $V$ of size $B$ (where $B$ is the number of buckets in the
cuckoo filter) is derived containing $1$ at position $i1$ and $-1$ everywhere
else, and the randomised response noise mechanism is applied to $V$ using our
flipping probability (derived from Theorem A.1).

  3. 3.

A new vector $V^{\prime}$ is constructed from $V$, where all the 1’s are
replaced by Bloom filters chosen as (lines 9-14):

    1. (a)

For all buckets other than $i1$, a random Bloom filter chosen from a pre-
computed list $F^{\prime}$ containing corresponding Bloom filters (using the
$randomly\\_choose\\_from()$ function) is sent (lines 9-11).

    2. (b)

If $i1$ is not flipped (lines 12-14), a similar Bloom filter is generated
(using the function $generate\\_similar\\_bf()$) with a distance $s_{c}$
chosen randomly from the range of $[s_{t},1.0]$ and sent (where $s_{t}$ is the
minimum similarity threshold to allow fuzzy matching). This Bloom filter is
generated by randomly flipping $s_{c}\times l$ bits in the original Bloom
filter, where $l$ is the length of Bloom filter. For example, in the running
example shown in Fig. 1, the original Bloom filter ‘110110011’ is perturbed as
‘110101011’ if $s_{c}=0.9$ chosen from the range $[0.8,1.0]$, as $l\times
s_{c}=9\times 0.9=2$ random bits ($5^{th}$ and $6^{th}$ in this example) need
to be flipped.

  4. 4.

The vector $V^{\prime}$ is sent to the server.

In the following we provide the formal proof of Algorithm 2 being
$\epsilon$-local Differentially private for the adjacency of two neighbouring
streams of data that differ by one item ($x_{1}$) which is present in one
stream and absent in the other. We also provide the proof for the adjacency
items being different items ($x_{1}$ in one stream and $x_{2}$ in the other)
in Appendix A.

######  Theorem 3.1 (Differential privacy of Algorithm 2)

Algorithm 2 is $\epsilon$-local differentially private.

###### Proof 3.2

For an arbitrary output $\tilde{V^{\prime}}$, the ratio of probabilities of
observing the same output given a user reported item $x_{1}$ or not is:

$\frac{Pr[PPCF(x_{1},\epsilon)=\tilde{V^{\prime}}]}{Pr[PPCF(\neg
x_{1},\epsilon)=\tilde{V^{\prime}}]}=\frac{Pr[[b_{1,1},b_{2,1},\cdots,b_{u,1}]=\tilde{V^{\prime}}]}{Pr[[b_{1,2},b_{2,2},\cdots,b_{u,2}]=\tilde{V^{\prime}}]},$
(4)

where $u$ is the number of bits flipped to +1 in the vector $V$, and $b_{i,1}$
denotes the $i^{th}$ Bloom filter sent for item $x_{1}$ and $b_{i,2}$ denotes
the $i^{th}$ Bloom filter sent for item that is not $x_{1}$. At maximum, only
one $b_{i,j}$ (where $i=1$ or $i=2$) in each of the set $V^{\prime}_{j}$ can
correspond to the real item $x_{j}$, while others correspond to artificially
crafted Bloom filters.

The probability of $b_{i,j}$ corresponding to artificial items being the same
in two output sets $V^{\prime}_{1}$ and $V^{\prime}_{2}$ (sent for two items’
$x_{1}$ and $\neg x_{1}$ insertion) is same. Without loss of generality, let’s
assume except the first Bloom filter (i.e. $b_{1,j}$), all the other Bloom
filters are artificial. The above ratio is then maximized when the Bloom
filters of the real items is present in one of the output sets (say
$V^{\prime}_{1}$) (i.e. $b_{1,1}$ is the Bloom filter encoding of real item
$x_{1}$ and $b_{1,2}$ is the Bloom filter encoding of an artificial item).

We denote by $P_{11}$ the probability that a reported Bloom filter $b_{1,j}\in
V^{\prime}_{j}$ is the encoding of the real item (say $x_{1}$) and is equal to
$\tilde{v^{\prime}}$, and by $P_{01}$ the probability that $b_{1,j}\in
V^{\prime}_{j}$ is an artificial item and is equal to $\tilde{v^{\prime}}$.

$\begin{multlined}\frac{Pr[PPCF(x_{1},\epsilon)=\tilde{V^{\prime}}]}{Pr[PPCF(\neg
x_{1},\epsilon)=\tilde{V^{\prime}}]}=\frac{P_{11}\times P_{01}\cdots\times
P_{01}}{P_{11}\times P_{01}\cdots\times
P_{01}}=\frac{P_{11}}{P_{01}}\end{multlined}\frac{Pr[PPCF(x_{1},\epsilon)=\tilde{V^{\prime}}]}{Pr[PPCF(\neg
x_{1},\epsilon)=\tilde{V^{\prime}}]}=\frac{P_{11}\times P_{01}\cdots\times
P_{01}}{P_{11}\times P_{01}\cdots\times P_{01}}=\frac{P_{11}}{P_{01}}$ (5)

We first calculate $P_{11}$. This occurs when item $x_{1}$’s bucket index is
not flipped in the vector $V$, i.e. $h(bf(x_{1}))=+1$ and the random
$s_{t}$-close Bloom filter chosen for this bucket is the same as $bf(x_{1})$.

$\begin{multlined}P_{11}=(1-P_{flip})\times\frac{1}{2^{l\times(1-s_{t})}}\end{multlined}P_{11}=(1-P_{flip})\times\frac{1}{2^{l\times(1-s_{t})}}$
(6)

When $s_{t}==1.0$, $P_{11}$ depends only on the flip probability $P_{flip}$.

Next, let’s calculate $P_{01}$. This can occur due to two reasons:

  1. 1.

An artificial bucket index gets flipped and $\tilde{v^{\prime}}$ is chosen
from the pre-filled set of $t$ Bloom filters for that bucket.

  2. 2.

$\tilde{v^{\prime}}$ gets chosen due to its $s_{t}$-closeness to a real item’s
Bloom filter.

The probability of randomly choosing one Bloom filter from the corresponding
Bloom filters for each bucket is $1/t$, where $t=2^{l}/B$ assuming the Bloom
filters/bit vectors are uniformly distributed across all buckets such that
each bucket is assigned with $2^{l}/B$ corresponding Bloom filters. Then,

$\begin{multlined}P_{01}=[P_{flip}\times\frac{1}{t}]+[(1-P_{flip})\times\frac{1}{2^{l}}].\end{multlined}P_{01}=[P_{flip}\times\frac{1}{t}]+[(1-P_{flip})\times\frac{1}{2^{l}}].$
(7)

Hence, for the maximum ration to be bounded requires:

$\begin{multlined}e^{-\epsilon}\leq\frac{P_{11}}{P_{01}}\leq e^{\epsilon}\\\
e^{-\epsilon}\leq\frac{(1-P_{flip})\times\frac{1}{2^{l\times(1-s_{t})}}}{[P_{flip}\times\frac{1}{t}]+[(1-P_{flip})\times\frac{1}{2^{l}}]}\leq
e^{\epsilon}\\\ \end{multlined}e^{-\epsilon}\leq\frac{P_{11}}{P_{01}}\leq
e^{\epsilon}\\\
e^{-\epsilon}\leq\frac{(1-P_{flip})\times\frac{1}{2^{l\times(1-s_{t})}}}{[P_{flip}\times\frac{1}{t}]+[(1-P_{flip})\times\frac{1}{2^{l}}]}\leq
e^{\epsilon}\\\ $ (8)

Ignoring the $[(1-P_{flip})\times\frac{1}{2^{l}}]$ term, we bound the above
ratio for $P_{flip}\geq\frac{1}{1+s.e^{\epsilon}}$, where
$s=\frac{2^{l(1-s_{t})}}{t}$.

$\begin{multlined}-\epsilon\leq
log(\frac{Pr[PPCF(x_{1},\epsilon)=\tilde{V^{\prime}}]}{Pr[PPCF(\neg
x_{1},\epsilon)=\tilde{V^{\prime}}]}\leq\epsilon\\\
\end{multlined}-\epsilon\leq
log(\frac{Pr[PPCF(x_{1},\epsilon)=\tilde{V^{\prime}}]}{Pr[PPCF(\neg
x_{1},\epsilon)=\tilde{V^{\prime}}]}\leq\epsilon\\\ $ (9)

Algorithm 3: Count querying with fuzzy matching (server-side)
---
Input:
\- $x$: Query data/element
\- $m$: Number of Bloom filter segments
\- $bf(\cdot)$: Bloom filter encoding function
\- $h(\cdot)$: Hash function
\- $fp(\cdot)$: Fingerprint function
\- $s_{t}$: Minimum similarity threshold
Output:
\- $c$: Estimated count of $x$
1: | $x^{\prime}=bf(x)$ | //Bloom filter
2: | $bf\\_segs=x^{\prime}.segment(m)$ | //Segments
3: | $C=[~{}]$ |
4: |  for $bf\\_seg\in bf\\_segs$ do | //Iterate segments
5: |  $f=fp(bf\\_seg)$ | //Fingerprint
6: |  $i1=h(bf\\_seg)$ | //First bucket
7: |  $i2=i1\oplus h(f)$ | //Second bucket
8: |  if $\mathbf{C}.bucket[i1]~{}or$ |
|  $\mathbf{C}.bucket[i2]~{}has~{}f$ then |
9: |  $C.add(count(f))$ |  //Add $f$’s count to $C$
10: |  else |
11: |  $C.add(0)$ |  //Add 0 count to $C$
12: |  $0$-count_segs = $[j\in C~{}if~{}j==0]$ |  // $0$-count segments
13: |  $sim_{max}=(m-|0$-count_segs$|)/m$ | //Max similarity
14: |  if $sim_{max}\geq s_{t}$ then |
15: |  $c=min([j~{}for~{}j\in C~{}if~{}j>0])$ |
16: |  else |
17: |  $c=0$ |
18: |  return $c$ |

###  3.3 Fuzzy Counting

Real-world data often contains variations and errors (e.g. typos or
misspellings in words), and therefore counting of items that differ by small
typos or variations from the queried item is important in many real
applications (e.g. word auto-correction application that counts words entered
by different users even with small typos and errors). Further, range queries
are commonly used in financial applications which require fuzzy counting of
similar items (e.g. similar salary range).

In order to allow fuzzy matching, the data custodians first encode the item
($x$) into a Bloom filter, add noise in terms of artificially crafted Bloom
filters (output set $V^{\prime}$ from Algorithm 2), and then split each of the
Bloom filters in $V^{\prime}$ (both real and artificial) into $m$ segments
(lines 1-2 in Algorithm 1). The larger the value for $m$ is, the more accuracy
the fuzzy matching will be. In Fig. 1 (right), an example fuzzy counting for
the two example pairs of (item, query) values in Fig. 1 (left) and (middle)
using $m=3$ is illustrated. The value for $m$ determines the degree of fault-
tolerance of the method to data errors and variations. A smaller value of $m$
is sufficient for a clean data, however if the data is assumed to be largely
dirty or for range queries with larger range, we need a large value of $m$ to
allow effective fuzzy matching (please see Theorem 3.3).

Then each of the $m$ Bloom filter segments are sent to the server (line 3 in
Algorithm 1) to be inserted into the Cuckoo filter. If the Bloom filter
segments of a querying item matches with a certain number of Bloom filter
segments $s_{m}$ in the Cuckoo filter (depending on the similarity threshold
parameter, $s_{t}$, given by the query issuer), where $s_{m}=m\times s_{t}$,
then the estimated count of the most similar item to the queried item will be
returned to the query issuer. In the example illustrated in Fig. 1, if
$s_{t}=0.65$, then the items need to match in at least $s_{m}=2$ Bloom filter
segments of the queried item in order to be counted. If the similarity
threshold is set to $s_{t}=1.0$, then it allows only exact matching, i.e. the
estimated count of the item that is matching exactly the same as the queried
item (in all $m$ segments) will be returned.

In contrast to the original Cuckoo hashing approach that stores fingerprints
of items, our approach stores fingerprints of Bloom filter segments of items
(lines 4-24 in Algorithm 1). Bloom filter segments preserve distance and
therefore allow fuzzy matching (as discussed in Section 2.1), whereas
fingerprints of items do not, i.e. a single character difference (in string
data) or number difference (in numerical data) returns completely different
fingerprints. Note that the Bloom filters in the output $V^{\prime}$ from
Algorithm 2 are differentially private using our proposed noise addition
algorithm. Bloom filter segmentation is a post-processing function that
enables fuzzy matching. Moreover, the Bloom filter segments of the Bloom
filters (real and artificial) in $V^{\prime}$ can be shuffled to amplify the
privacy guarantees, as similar to the Encode, Shuffle, and Analyze mechanism
proposed by Google [26].

As shown in Algorithm 3, the querying function returns the count value of the
closest value to the querying value. For example, if the query value is
$q=5000$, it will return the count/frequency of $5000$ if available in the
filter (exact matching), otherwise it will return the count/frequency of a
value $v$ that is the closest to $q$ and has a similarity above the similarity
threshold $s_{t}$ (i.e. $sim(v,q)\geq s_{t}$ and that has the highest
similarity with $q$). The algorithm first retrieves the count values
(frequency/number of occurrences as calculated by the $count(\cdot)$ function)
for each of the Bloom filter segments of the query value $q$ (lines 3-11 in
Algorithm 3) and calculates how many segments have a count of $0$, i.e. not
found in the filter (line 12).

Using this, it computes the maximum similarity of the closest value (line 13,
where $|\cdot|$ denotes the cardinality of a given set) and if this similarity
is above the similarity threshold $s_{t}$ (line 14) then the minimum count of
the segments with non-zero counts is returned as the count value of the
closest value of $q$ (lines 15-18).

###  3.4 Utility analysis

We next analyze the utility loss with our proposed method.

######  Theorem 3.3 (Count estimation error bound)

The bound of the estimated count $c^{\prime}$ of an element $x$ using our
method is given as.

$\begin{multlined}c-c\times
max(\frac{1}{1+s.e^{\epsilon}},\frac{s.e^{\epsilon}\times(1-s_{t})^{m\times
s_{t}}}{1+s.e^{\epsilon}})\leq c^{\prime}\\\ \leq c+[\frac{n\times(B-1)\times
2^{l.(1-s_{t})}}{(1+s.e^{\epsilon})\times 2^{l}}],\\\ \end{multlined}c-c\times
max(\frac{1}{1+s.e^{\epsilon}},\frac{s.e^{\epsilon}\times(1-s_{t})^{m\times
s_{t}}}{1+s.e^{\epsilon}})\leq c^{\prime}\\\ \leq c+[\frac{n\times(B-1)\times
2^{l.(1-s_{t})}}{(1+s.e^{\epsilon})\times 2^{l}}],\\\ $ (10)

where $c$ is the actual count of $x$, $n$ is the number of records inserted
into the Cuckoo filter, $l$ is the length of Bloom filters, $m$ is the number
of Bloom filter segments, $B$ is the number of buckets, and
$s=\frac{2^{l.(1-s_{t})}.B}{2^{l}}$ (see Theorem A.1)

###### Proof 3.4

The deviation of the estimated count $c^{\prime}$ of an element $x$ from its
actual count $c$ can occur due to false negatives as well as false positives
leading to lower and higher estimated counts than the true counts:

Lower bound: There are two cases associated with false negatives for an item
$x$ (Bloom filter of $x$ is $x^{\prime}$) resulting from noise addition to
meet differential privacy guarantees.

Case 1: the bit $h(x^{\prime})$ is flipped in $V$. This probability is
$\frac{1}{1+s.e^{\epsilon}}$, i.e. from $c$ records of item $x$,
$c\times\frac{1}{1+s.e^{\epsilon}}$ records would have been placed in wrong
buckets in the Cuckoo filter (not in one of the buckets $h(x^{\prime})$ or
$h(x^{\prime})\oplus h(fp(x^{\prime}))$) and therefore resulting in false
negatives.

Case 2: the bit $h(x^{\prime})$ is not flipped in $V$, however the similar
Bloom filter (similar to $x^{\prime}$) chosen for bucket $h(x^{\prime})$ does
not match to $x^{\prime}$ in the minimum number of segments out of $m$
segments according to the threshold $s_{t}$. The probability that the bit
$h(x^{\prime})$ in the vector is not flipped to $-1$ is
$\frac{s.e^{\epsilon}}{1+s.e^{\epsilon}}$. The minimum number of segments that
need to be matched is $s_{m}=m\times s_{t}$. False positives occur if at least
one bit in each of these segments gets flipped. The probability of a bit in
$x^{\prime}$ being flipped in $\tilde{x^{\prime}}$ is $l(1-s_{t})/l=1-s_{t}$.
Hence, the probability that at least 1 bit in each of the $s_{m}$ segments
being flipped is $(1-s_{t})^{m\times s_{t}}$.

Therefore, the lower bound of the estimated count $c^{\prime}$ is
$c-c~{}\times$ the maximum of the two cases, i.e.
$max(\frac{1}{1+s.e^{\epsilon}},\frac{s.e^{\epsilon}\times(1-s_{t})^{m\times
s_{t}})}{1+s.e^{\epsilon}})$. For example, if $l=20$, $\epsilon=6$,
$s_{t}=0.7$, $m=4$, and $B=10000$, then $s=0.61$, and therefore
$P_{flip}=\frac{1}{1+s.e^{\epsilon}}=0.004$. The lower bound of the estimated
frequency count for an item of true frequency count of $c=100$ is $c-c\times
max(0.004,\frac{0.61\times 403.4288\times(0.3)^{4})}{1+(0.061\times
403.4288)})=c-c\times max(0.004,0.008)=100-100\times 0.008=99.19$. With a
larger number of segments $m=5$, the lower count becomes $c-c\times
max(0.004,0.0002)=99.75$, and with a smaller $m=2$, the lower count becomes
$c-c\times max(0.004,0.089)=91.03$.

Upper bound: On the other hand, false positives could occur due to noise
addition (where bits with -1 in $V$ are flipped to 1) resulting in insertion
of corresponding (artificial) fingerprints into buckets and collision of
fingerprints of different elements. The likelihood of any record being falsely
inserted into the given bucket is $\frac{1}{1+s.e^{\epsilon}}$. Given $n$ is
the number of elements/records that are inserted into the Cuckoo filter,
$n\times(B-1)\times\frac{1}{1+s.e^{\epsilon}}$ records can be falsely inserted
into the (artificial) buckets. Among these, there are $2^{l(1-s_{t})}$
possible bit patterns that could match with the given real item’s Bloom
filter. The probability of choosing one of these potentially matching bit
patterns from the artificial buckets is $\frac{2^{l(1-s_{t})}/B}{2^{l}/B}$.
Therefore, the upper bound of $c^{\prime}$ is
$c+[\frac{n\times(B-1)}{1+s.e^{\epsilon}}\times\frac{2^{l.(1-S_{t})}}{2^{l}}]$.
With the previous example, if the number of records inserted so far is
$n=1000$, then the upper bound of the estimated frequency count of an item
whose real frequency count is $c=100$ is $100+[\frac{1000\times
9999}{1+(0.61\times 403.4288)}\times\frac{2^{6}}{2^{20}}]=100+2.47=102.47$.

###  3.5 Communication and computation overhead

Inserting an item into the Cuckoo filter requires sending $m\times
B\times\frac{1}{1+s.e^{\epsilon}}$ Bloom filter segments of length $l/m$ bits,
where $s=\frac{B.2^{l(1-s_{t})}}{2^{l}}$ (see Theorem A.1). The communication
complexity of insertion step therefore depends on the number of segments $m$,
number of buckets $B$, and the length of Bloom filters $l$. Our method has
higher communication overhead for the insertion step than RAPPOR and Apple’s
CMS algorithm which require only sending a vector of size $l$ bits to the
server followed by vector operation between two vectors (between the received
vector and the aggregated vector stored in the server) for inserting an item.
However, we parallelize the insertion step to reduce the computation
complexity by having multiple cuckoo filter data structures in the server and
dividing the segments and inserting them into different structures. The
querying function therefore needs to be applied on each of these data
structures and the counts are summed to get the total frequency count of a
queried item. This is conceptually similar to using different cohorts in
RAPPOR [1]. Hence, the server-side querying of our method requires $2\times m$
lookup operations at each of the cuckoo filters (in parallel) for every
queried item and therefore querying is efficient than the RAPPOR and Apple’s
algorithm.

In summary, our method provides significantly higher utility guarantees and
querying efficiency with similar privacy guarantees at the cost of
communication overhead for inserting items.

##  4 Experimental Evaluation

In this section we present and discuss the results of experimental study of
our proposed method.

###  4.1 Datasets and Synthetic Dataset Generation

We used two datasets in our experiments. The first one is words dataset that
contains a list of words from the complete work of Shakespeare 333available
from https://data.world/tronovan/shakespeare-word-frequencies. The number of
unique words in this dataset is 23,113. We duplicated these words to generate
1,750,000 records and split across 20 parties and the total number of records
is 583,456. The total number of records is randomly divided into 10,000
disjoint sets for simulating 10,000 parties.

We further generated a synthetic dataset based on this words dataset for fuzzy
counting experiments. For each of the unique values in the dataset, we created
synthetic duplicate records and/or queries by replacing some of the values $v$
with similar values $v^{\prime}$ according to the similarity threshold used
($s_{t}=0.8$). Specifically, the synthetic dataset is generated by replacing
50% of the count of each value with a similar value according to $s_{t}$. To
generate synthetic values $v^{\prime}$ that are similar to $v$ (i.e.,
$sim(v,v^{\prime})\geq s_{t}$), we modified $v$ by including character edits
(inserts with $0.3$ probability, deletes with $0.3$ probability, and swaps
with $0.4$ probability). We use these synthetically generated records for
querying in order to evaluate and compare the performance of counting
algorithms in the presence of data errors and variations.

True count for exact matching of a value in this dataset is the actual
frequency/count of that value, while true count for fuzzy matching of a value
is the count of all values similar to the value according to a similarity
metric and similarity threshold. We use the $q$-gram-based Dice-coefficient
metric for calculating the similarity between (unencoded) string data [9, 27].
Estimated count of a value is the count value returned by the privacy
preserving counting algorithm (Algorithm 2) when querying for that value.

###  4.2 Baseline Methods and Parameter Setting

We compare our proposed method with two state-of-the-art privacy preserving
counting methods proposed by Google (RAPPOR) [1] and Apple (CMS) [2] as these
are closely related to our work. Similar to our approach, these two methods
use probabilistic data structures and local Differential privacy for privacy
preserving counting (however, not specifically developed for real-time
counting in streaming data applications, as described in detail in Section 2).

Figure 3: Comparison of efficiency results in terms of (a) insertion time
(CDF) and (b) querying time (CDF) for all approaches with exact counting (i.e
$m=1$ with Cuckoo filter approach) on the words datasets.

Figure 4: Comparison of (a) fuzzy matching efficiency in terms of querying
time (CDF) for different values of $m$ and (b) the impact of increasing volume
of records insertion on the false positive rates for all approaches on the
synthetic words datasets.

We implemented both our proposed approach and the two competing baseline
approaches in Python 3.5.2, and ran all experiments on a server with four
2-core 64-bit Intel Core I7 2.6 GHz CPUs, 8 GBytes of memory and running
Ubuntu 16.04. Please note that the RAPPOR source code (implemented using R
combined with Python) is publicly available 444available from
https://github.com/google/rappor. In order to perform a fair comparison, we
implemented all three approaches in Python (using Python libraries such as
numpy, bitarray, and sklearn). The programs and test datasets are available
from the authors.

Default parameter setting of our approach is $\epsilon=6$, capacity of Cuckoo
filter $B=10000$, default bucket size $b=4$, maximum number of kicks $500$,
similarity threshold $s_{t}=0.8$, length of Bloom filters $l=30$, number of
segments $m=5$, and number of hash functions $k=2$, as it gave the best
results when validating with a grid search parameter tuning method. We also
evaluated our method against different $\epsilon$, in the range of
$\epsilon=[2,4,6,8,10]$, and $m=[1,3,5]$.

Parameter settings of the state-of-the-art methods are chosen in a similar
range (adjusted according to the number of records used) as used in the
original approaches. For Google-RAPPOR, we used the number of hash functions
$k=2$, length of Bloom filters $l=1000$, number of cohorts $m=32$, and noise
parameters $f=0.5$, $p=0.5$, and $q=0.75$. For Apple-CMS, we set $\epsilon=8$,
length of vectors $l=1024$, and the number of hash functions $k=20000$.

###  4.3 Evaluation metrics

We evaluated our method and compared with Google-RAPPOR and Apple-CMS in terms
of insertion and querying efficiency as well as accuracy of querying results.
Computational efficiency is measured using insertion time (in seconds) and
querying time (in seconds). The accuracy of count estimation is measured as
the absolute error that calculates the variance/difference between true count
and estimated count (i.e. the estimation error). We also evaluated the false
positive rate of the probabilistic data structures against number of records
inserted to evaluate the impact of continuous data insertion on the utility.
Privacy is measured using the privacy budget $\epsilon$ required for providing
Differential privacy guarantees.

Figure 5: Comparison of effectiveness results of exact counting (left) and
fuzzy counting (right) for all approaches on the words (left) and synthetic
words (right) datasets measured as the variance between actual and estimated
counts of queried items.

Figure 6: Ablation study: utility of count estimation of the proposed method
measured as the median of the variance/error between actual and estimated
counts of queried items in 10 iterations against different $\epsilon$ values
on the words datasets (left) and against different number of segments $m$ on
synthetic words datasets (right).

###  4.4 Results and Discussion

s Efficiency results: We compare the insertion time and querying time of our
method with the baselines for exact counting in Figures 3(left) and 3(right),
respectively. Please note that the insertion and querying time are shown in
CDF plots, i.e. the total time required for inserting or querying a certain
number of records (not a single record). The insertion time required for our
method is slightly larger than the baseline approaches. The reason is that it
needs to insert multiple fingerprints for every single item which requires
several lookup operations in the Cuckoo filter even with parallel settings.
This is negligible given the significant increment in utility of both exact
and fuzzy counting with our method compared to the state-of-the-art methods,
as will be discussed next. Moreover, the querying time is highly efficient and
faster than the baselines (Fig. 3 (right)). For real-time querying
applications querying time is more important than insertion time, as the
queries need to be instantly answered in real-time. Therefore, compared to
RAPPOR and CMS, our method is highly applicable to real-time querying.

We next present the querying time for fuzzy counting with our approach for
different number of Bloom filter segments $m=1$, $m=2$, and $m=3$ in Fig. 4
(left) on the synthetic words dataset where the queries contain data errors
(e.g. typos) and variations. As expected, the querying time increases with
larger $m$, as more segments need to be queried with larger $m$. Please note
that parallel processing of insertion can help reducing the insertion time and
hence the insertion time is not impacted with increasing $m$ (due to space
limitation we do not show this results), but still all $m$ segments need to be
queried from all cuckoo filters for a given query. The querying time for fuzzy
counting is the same as for exact counting with RAPPOR and CMS. However, even
with $m=5$, our cuckoo filter-based approach has considerably lower querying
time than these state-of-the-art methods (i.e. faster querying time not only
for exact counting, but also for fuzzy counting with a relatively larger
number of segments). In other words, the querying time required for fuzzy
counting by our method is still lower than the other two methods that only
allow exact counting.

Effectiveness results: The result of the impact of continuous insertion of
records on the utility or effectiveness of counting is illustrated in Figure 4
(right). As can be seen, the false positive rate is not impacted with number
of records inserted into the Cuckoo filter due to adaptively increasing the
bucket size. Our method has significantly lower false positive rate (nearly
$0.0$) compared to RAPPOR and Apple-CMS, and therefore provides higher quality
of hash-mapping into the probabilistic data structure (Cuckoo filter). By
bounding the false positive rate of adaptive Cuckoo filter to a very small
value ($0.002$ in this experiment), the number of false positives that could
occur due to hash-mapping in probabilistic data structures is negligible
(therefore utility is only impacted by the differential privacy noise addition
in our method). Since RAPPOR uses cohorts to reduce the effect of false
positives, it performs better than Apple-CMS until a certain number of records
are inserted. These results reveal that our method can provide higher utility
results with a significantly large margin even with large number of records
inserted (in contrast to the baseline methods) at the cost of computational
efficiency loss by a small margin.

In Figure 5 we evaluate the variance or absolute error of estimated and true
counts of querying data with exact counting on words (left) and with fuzzy
counting on synthetic words (right) datasets. Our results show that our method
significantly outperforms the baselines by resulting in the lowest median of
count estimation error in both cases, exact and fuzzy counting. As expected,
RAPPOR estimates counts with large variance from true counts (due to the large
false positive rate). Reducing the false positive rate by increasing the
length of Bloom filters required extremely longer insertion and querying time
for RAPPOR. The fuzzy counting results in Fig. 5 (right) evaluate the fault
tolerance/robustness of the methods to data errors and variations (using the
synthetic words dataset). The significantly lower variance or error between
estimated and true counts of our method on this dataset compared to the other
two methods that do not support fuzzy counting validates the importance of
fuzzy counting for improved accuracy of count estimation in data with errors
and variations. In summary, our method achieves higher accuracy of count
estimation compared to baselines by a significantly large margin for both
exact and fuzzy counting.

Ablation study: We performed an ablation study of our method with two
important parameters of our method: a) privacy budget $\epsilon$ and b) number
of Bloom filter segments for fuzzy counting $m$. The results are shown in Fig.
6. Fig. 6 (left) shows that the utility of count estimation by our method
decreases with privacy budget ($\epsilon$). The trade-off between privacy and
utility is reflected in these results.

Fig. 6 (right) shows the utility of fuzzy counting measured using the variance
or absolute error between true and estimated counts with different $m$ values.
As shown in the plot, with increasing $m$ the variance or error drops, i.e.
the utility of fuzzy counting increases, as the cost of more querying time (as
presented in Fig. 4 (left). These results validate the trade-off between
effectiveness and efficiency for fuzzy matching.

##  5 Related Work

Several privacy preserving counting or aggregation methods have been proposed
in the literature. They can be categorized into three: 1) cryptographic
methods, 2) sampling and statistics-based methods, and 3) probabilistic
methods.

Cryptographic: Searching on encrypted data for counting operations has been
focused by several works [28, 29, 30]. However, most of these rely on the
computation of very expensive functions (e.g. bilinear pairings) for each
element/item in a dataset, rendering them not practical. An efficient and
somewhat homomorphic encryption method, EPiC, using the MapReduce framework
for cloud counting was proposed in [30]. However, these methods are not
applicable to fuzzy counting or stream data applications.

PRIO is a privacy preserving system for the collection of aggregate statistics
using cryptographic techniques [31]. While the utility of aggregation with
such cryptographic techniques is high, they do not allow fuzzy matching due to
high computational cost required and do not support stream data processing.
Some works considered combining multi-party computation (MPC) with
differential privacy. For example, [32] developed secure aggregation protocols
to add Laplace or Gaussian noise to ensure differential privacy for the
clients, and [33] studied the overhead of adding Laplace noise to MPC.

Sampling and statistics: Another category of methods for privacy preserving
releasing or publishing of stream data considers providing statistics (e.g.
moving average) of local data with local and/or central differential privacy
(LDP or CDP) guarantees [34, 35]. A recent work on answering range queries
under LDP has proposed two approaches based on hierarchical histograms and the
Haar wavelet transform to approximately answer range queries [36]. Relaxed LDP
was studied in [37] that proposes E-LDP where E defines heterogeneous privacy
guarantees for different pairs of private data values for significant utility
gains in answering linear and multi-dimensional range queries. A recent work
used sampling-based frequency estimation with fairness constraints which
provides some level of privacy protection with good utility when the number of
clients is small [38]. A main challenge with these methods is that ensuring
true randomness is a difficult task, so the success of random sampling is
dependent on the data.

Probabilistic: This category of methods received a lot of attention in the
recent literature due to its computational and storage efficiency and provable
privacy guarantees. The two state-of-the-art methods based on probabilistic
methods for approximate aggregation are: (1) RAPPOR proposed by Google for
anonymously collecting statistics about end-user software [1] and (2) count-
mean sketch (CMS) proposed by Apple for identifying frequently used words or
emojis by users without compromising their privacy [2] (described in detail in
Section 2).

Another method proposed by Apple to overcome the communication cost of CMS is
the Hadamard transformation of CMS (HCMS) [2]. Instead of sending over a
vector to the server for inserting or updating an element, HCMS transforms the
vector using Hadamard transformation and sends a single bit that is sampled
from the transformed vector. Despite the improvement in the communication
cost, it is not applicable to streaming data as the Hadamard transformation of
the updated sketch is required upon every single item’s insertion/update,
which is computationally expensive for continuous data insertion and on-the-
fly querying of frequency of items.

Probabilistic data structures and differential privacy have also been used for
other private counting tasks, such as counting of distinct elements [39],
heavy hitters [14, 13], and incidence counting [40], due to their highly
efficient computation, space, and communication costs. Cuckoo filters have
been widely used for private set intersection (PSI) with the purpose of
increasing or optimising the efficiency (similar to blocking or hashing in
record lookup or linkage techniques [27]). For example, a PSI technique was
proposed that utilizes Cuckoo hashing for batching [15]. Similarly, an
efficient circuit-based PSI was proposed using Cuckoo hashing [19]. Cuckoo
filter was used to reduce the amount of data to be exchanged by a
cryptography-based PSI [16]. Cuckoo hashing has been used for reducing the
asymptotic overhead of Oblivious Transfer (OT)-based PSI protocol [17]. This
approach was further improved using permutation-based hashing and 3-way Cuckoo
hashing where 3 instead of 2 hash functions are used to generate a densely
populated Cuckoo table in order to reduce the overall number of OTs [18].

##  6 Conclusion

In this paper we have addressed a novel problem of privacy preserving real-
time counting in stream data, which is increasingly being required in many
real applications, using a hybrid method of Cuckoo filter and Bloom filter
probabilistic data structures. Privacy preserving counting has been studied in
the literature with two notable solutions by Google (RAPPOR) and Apple (CMS).
We have investigated the additional challenges of answering real-time count
querying in stream data and proposed a method that overcomes the limitations
of existing methods for real-time counting in stream data applications.

We have proposed a novel local Differential privacy algorithm with low utility
loss guarantees, and provided formal proof of privacy and utility guarantees
of our method. We have conducted an experimental study of our method using
large real and synthetic datasets. The results show that compared to two
state-of-the-art approaches by Google and Apple, our method achieves
significantly higher utility of count estimation and lower querying time at
the overhead of higher insertion time with similar privacy guarantees.

In the future, we aim to study noise addition according to “local sensitivity”
of the bucket in the Cuckoo filter in order to add noise based on the set of
items the bucket has seen so far which could improve the utility and
efficiency for a given privacy budget. The proposed differential privacy
algorithm requires that clients need to keep track of the items reported to
the server in order to avoid reporting the same item multiple times (i.e. only
unique items are reported to the server). In the future, we aim to address the
local storage/memory efficiency aspect by using efficient probabilistic data
structures, such as HyperLogLog.

Further, investigating other counting tasks in stream data, including counting
of distinct elements, heavy hitters, incidence counting, and estimating
cropped means, is also important in different applications. For example,
count-distinct is required to count views on a video, unique tweets, or unique
customers accessed an online service. More work is required towards the
development of advanced techniques for privacy preserving calculation of other
statistical functions, such as conditional querying and incidence counting, in
stream data. Investigating pan-private algorithms for streaming data
applications is important to guarantee that the intermediate states in dynamic
data are also private, i.e. the state of the algorithm after processing each
iteration’s update and the final output are jointly $\epsilon$-differentially
private [22].

##  Appendix A Differential Privacy Proof for adjacency items being different
items

######  Theorem A.1 (Differential privacy of Algorithm 2)

Algorithm 2 is $\epsilon$-local Differentially private.

###### Proof A.2

We will show that for an arbitrary set $V^{\prime}$, the ratio of
probabilities of observing $V^{\prime}$ as output of Algorithm 2, given
adjacent sets ${\cal D}=\\{x_{1}\\}$ and ${\cal D^{\prime}}=\\{x_{2}\\}$ as
input is bounded by $e^{\epsilon}$. Without loss of generality let
$V^{\prime}=[b_{1},b_{2},\cdots,b_{u}]$ denote the $u$ Bloom filters output by
Algorithm 2. Then we want to show that,

$r=\frac{Pr[Algorithm~{}2(x_{1})=[b_{1},b_{2},\cdots,b_{u}]]}{Pr[Algorithm~{}2(x_{2})=[b_{1},b_{2},\cdots,b_{u}]]}\leq
e^{\epsilon},$ (11)

Note when ${\cal D}=\\{x_{1}\\}$ is the input, at most one Bloom filter in
$V^{\prime}$ is due to item $x_{1}$, and that Bloom filter can be either from
$x_{1}$’s true bucket (say $i_{1}$) or some other bucket $i_{\ell}$. This is
because the $generate\\_similar\\_bf(x_{1})$ function can output a Bloom
filter from either $x_{1}$’s true bucket or some other bucket. Thus, let’s
denote by $b_{i_{1}}$ and $b_{i_{\ell}}$ the respective Bloom filters that are
added to $V^{\prime}$ in those mutually exclusive cases. All other Bloom
filters in $V^{\prime}$ are the result of the flipping of $-1$ to $+1$ due to
the randomized response (with parameter $p_{f}$) and the subsequent choosing
of a random Bloom filter via the $randomly\\_choose\\_from()$ function. Since
the probability of these ’other’ Bloom filters being in $V^{\prime}$ is same
whether the incoming item is $x_{1}$ or $x_{2}$, we only need to analyze the
probability that input ${\cal D^{\prime}}=\\{x_{2}\\}$ results in the same
Bloom filter $b_{i_{1}}$ (or $b_{i_{\ell}}$ as the case may be).

For this analysis, we need to consider three buckets: $i_{1}$ \- the bucket of
item $x_{1}$’s Bloom filter, $i_{2}$ \- the bucket of item $x_{2}$’s Bloom
filter and $i_{\ell}$ \- the bucket of the ’similar’ Bloom filter that is
output by $generate\\_similar\\_bf(x_{1})$.

We will now upper bound the ratio $r$ for the following three cases:

Case 1: $b_{i_{1}}$ is in $V^{\prime}$ due to item $x_{1}$. In this case, when
the incoming item is $x_{1}$ the bit at position $i_{1}$ remains $+1$ and the
bits at $i_{2}$ and $i_{\ell}$ remain $-1$ after the RR mechanism and
$generate\\_similar\\_bf(x_{1})$ returns a Bloom filter from bucket $i_{1}$.
While when the incoming item is $x_{2}$, the bit at position $i_{1}$ is
flipped from $-1$ to $+1$, the bit at position $i_{2}$ is flipped from $+1$ to
$-1$ and the bit at $i_{\ell}$ remains at $-1$ after the RR mechanism. Thus
for this case the ratio $r$ is
$r=\frac{(1-p_{f}).\frac{1}{2^{\ell(1-s_{t})}}}{p_{f}.\frac{1}{t}}.\frac{(1-p_{f})}{p_{f}}.\frac{(1-p_{f})}{(1-p_{f})}$

Case 2: $b_{i_{\ell}}$ is in $V^{\prime}$ due to item $x_{1}$. In this case,
when the incoming item is $x_{1}$ the bit at position $i_{1}$ remains $+1$ and
the bits at $i_{2}$ and $i_{\ell}$ remain $-1$ after the RR mechanism and
$generate\\_similar\\_bf(x_{1})$ returns a Bloom filter from bucket
$i_{\ell}$. While when the incoming item is $x_{2}$, the bit at position
$i_{1}$ remains at $-1$, the bit at position $i_{2}$ is flipped from $+1$ to
$-1$ and the bit at $i_{\ell}$ is flipped from $-1$ to $+1$ after the RR
mechanism. Thus for this case the ratio $r$ is
$r=\frac{(1-p_{f}).\frac{1}{2^{\ell(1-s_{t})}}}{(1-p_{f})}.\frac{(1-p_{f})}{p_{f}}.\frac{(1-p_{f})}{p_{f}.\frac{1}{t}}$

Case 3: $\phi$ is in $V^{\prime}$ due to item $x_{1}$. In this case, when the
incoming item is $x_{1}$ the bit at position $i_{1}$ is flipped to $-1$ and
the bits at $i_{2}$ and $i_{\ell}$ remain $-1$ after the RR mechanism. While
when the incoming item is $x_{2}$, the bit at position $i_{1}$ remains at
$-1$, the bit at position $i_{2}$ is flipped from $+1$ to $-1$ and the bit at
$i_{\ell}$ remains at $-1$ after the RR mechanism. Thus for this case the
ratio $r$ is
$r=\frac{p_{f}}{(1-p_{f})}.\frac{(1-p_{f})}{p_{f}}.\frac{(1-p_{f})}{(1-p_{f})}$

Thus the ratio $r$ is upper bounded by
$\frac{(1-p_{f})^{2}.\frac{1}{2^{\ell(1-s_{t})}}}{p_{f}^{2}.\frac{1}{t}}$.
Thus $r\leq e^{\epsilon}$ implies
$p_{flip}\geq\frac{1}{1+\sqrt{s.e^{\epsilon}}}$

## Acknowledgment

This research was funded by Macquarie University CyberSecurity Hub and
strategic research funds from Macquarie University. Authors Dinusha Vatsalan
and Raghav Bhaskar were affiliated with CSIRO Data61 at the initial submission
of this manuscript.

## References

  * [1] Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in _SIGSAC conference on computer and communications security_. ACM, 2014, pp. 1054–1067.
  * [2] D. P. T. Apple, “Learning with privacy at scale,” _Apple Machine Learning Journal_ , 2017.
  * [3] R. Masood, D. Vatsalan, M. Ikram, and M. A. Kaafar, “Incognito: A method for obfuscating web data,” in _WWW_. International World Wide Web Conferences Steering Committee, 2018, pp. 267–276.
  * [4] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher, “Cuckoo filter: Practically better than bloom,” in _CoNEXT_. ACM, 2014, pp. 75–88.
  * [5] M. Mitzenmacher and E. Upfal, _Probability and computing: Randomized algorithms and probabilistic analysis_. Cambridge University Press, 2005.
  * [6] R. Schnell, “Privacy preserving record linkage,” in _Methodological developments in data linkage_ , K. Harron, H. Goldstein, and C. Dibben, Eds. Chichester: Wiley, 2016, pp. 201–225.
  * [7] N. Holohan, D. J. Leith, and O. Mason, “Optimal differentially private mechanisms for randomised response,” _IEEE TIFS_ , vol. 12, no. 11, pp. 2726–2735, 2017.
  * [8] B. Bloom, “Space/time trade-offs in hash coding with allowable errors,” _Communications of the ACM_ , vol. 13, no. 7, pp. 422–426, 1970.
  * [9] D. Vatsalan and P. Christen, “Privacy-preserving matching of similar patients,” _JBI_ , vol. 59, pp. 285–298, 2016.
  * [10] D. Vatsalan, P. Christen, and V. S. Verykios, “A taxonomy of privacy-preserving record linkage techniques,” _Information Systems_ , vol. 38, no. 6, pp. 946–969, 2013.
  * [11] S. M. Randall, A. M. Ferrante, J. H. Boyd, and J. B. Semmens, “Privacy-preserving record linkage on large real world datasets,” _JBI_ , vol. 50, no. 1, p. 1, 2014.
  * [12] G. Cormode and S. Muthukrishnan, “Approximating data with the count-min data structure,” _IEEE Software_ , vol. 29, no. 1, 2012.
  * [13] D. Karapiperis, D. Vatsalan, V. S. Verykios, and P. Christen, “Large-scale multi-party counting set intersection using a space efficient global synopsis,” in _DASFAA_ , Hanoi, 2015.
  * [14] L. Melis, G. Danezis, and E. De Cristofaro, “Efficient private statistics with succinct sketches,” in _NDSS_ , 2016.
  * [15] H. Chen, K. Laine, and P. Rindal, “Fast private set intersection from homomorphic encryption,” in _ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2017, pp. 1243–1255.
  * [16] A. C. D. Resende and D. F. Aranha, “Faster unbalanced private set intersection,” _FC 2018_ , 2018.
  * [17] B. Pinkas, T. Schneider, and M. Zohner, “Faster private set intersection based on $\\{$OT$\\}$ extension,” in _USENIX Security Symposium_ , 2014, pp. 797–812.
  * [18] B. Pinkas, T. Schneider, G. Segev, and M. Zohner, “Phasing: Private set intersection using permutation-based hashing,” in _USENIX Security Symposium_ , 2015, pp. 515–530.
  * [19] B. Pinkas, T. Schneider, C. Weinert, and U. Wieder, “Efficient circuit-based psi via cuckoo hashing,” in _EuroCrypt_. Springer, 2018, pp. 125–157.
  * [20] C. Dwork, “Differential privacy,” _International Colloquium on Automata, Languages and Programming_ , pp. 1–12, 2006.
  * [21] C. Dwork, “Differential privacy: A survey of results,” in _Theory and Applications of Models of Computation_. Springer, 2008, pp. 1–19.
  * [22] C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin, “Pan-private streaming algorithms.” in _ICS_ , 2010, pp. 66–80.
  * [23] A. Evfimievski, J. Gehrke, and R. Srikant, “Limiting privacy breaches in privacy preserving data mining,” in _ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 2003, pp. 211–222.
  * [24] A. Greenberg, “Apple’s ‘differential privacy’is about collecting your data—but not your data,” _Wired, June_ , vol. 13, 2016.
  * [25] P. Christen, T. Ranbaduge, D. Vatsalan, and R. Schnell, “Precise and fast cryptanalysis for Bloom filter based privacy-preserving record linkage,” _IEEE TKDE_ , 2018.
  * [26] A. Bittau, Ú. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “Prochlo: Strong privacy for analytics in the crowd,” in _Symposium on Operating Systems Principles_ , 2017, pp. 441–459.
  * [27] P. Christen, _Data matching - concepts and techniques for record linkage, entity resolution, and duplicate detection_ , ser. Data-Centric Systems and Applications. Springer, 2012.
  * [28] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryption with keyword search,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2004, pp. 506–522.
  * [29] D. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” _sp_ , p. 0044, 2000.
  * [30] T. D. Vo-Huu, E.-O. Blass, and G. Noubir, “Epic: efficient privacy-preserving counting for mapreduce,” _Computing_ , vol. 101, no. 9, pp. 1265–1286, 2019\.
  * [31] H. Corrigan-Gibbs and D. Boneh, “Prio: Private, robust, and scalable computation of aggregate statistics,” in _USENIX Symposium on Networked Systems Design and Implementation_ , 2017, pp. 259–282.
  * [32] M. Pettai and P. Laud, “Combining differential privacy and secure multiparty computation,” in _Proceedings of the 31st Annual Computer Security Applications Conference_ , 2015, pp. 421–430.
  * [33] V. Bindschaedler, S. Rane, A. E. Brito, V. Rao, and E. Uzun, “Achieving differential privacy in secure multiparty data aggregation protocols on star networks,” in _ACM on Conference on Data and Application Security and Privacy_ , 2017, pp. 115–125.
  * [34] V. Perrier, H. J. Asghar, and D. Kaafar, “Private continual release of real-valued data streams,” _NDSS_ , 2019.
  * [35] T. Wang, J. Q. Chen, Z. Zhang, D. Su, Y. Cheng, Z. Li, N. Li, and S. Jha, “Continuous release of data streams under both centralized and local differential privacy,” _NDSS_ , 2020.
  * [36] T. Kulkarni, G. Cormode, and D. Srivastava, “Answering range queries under local differential privacy,” _VLDB_ , vol. 12, 2018.
  * [37] Z. Xiang, B. Ding, X. He, and J. Zhou, “Linear and range counting under metric-based local differential privacy,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 908–913.
  * [38] M. Yang, I. Tjuawinata, K.-Y. Lam, T. Zhu, and J. Zhao, “Fair and differentially private distributed frequency estimation,” _arXiv preprint arXiv:2104.05974_ , 2021.
  * [39] R. Stanojevic, M. Nabeel, and T. Yu, “Distributed cardinality estimation of set operations with differential privacy,” in _2017 IEEE Symposium on Privacy-Aware Computing (PAC)_. IEEE, 2017, pp. 37–48.
  * [40] M. Alaggan, M. Cunche, and M. Minier, “Non-interactive (t, n)-incidence counting from differentially private indicator vectors,” in _Proceedings of the 3rd ACM on International Workshop on Security And Privacy Analytics_ , 2017, pp. 1–9.

|  Dinusha Vatsalan is a Senior Lecturer in Cyber Security at Macquarie
University. Dinusha received her PhD in Computer Science from Australian
National University and BSc (Hons) from University of Colombo, Sri Lanka. She
was a Research Scientist at Data61, CSIRO. Her research interests include
privacy-preserving technologies for record linkage, data sharing, and
analytics, privacy attacks and defences, and privacy risk quantification. She
has authored over 60 scientific articles in these topics.
---|---
|  Raghav Bhaskar is a Co-founder and CEO at AppsPicket, New Delhi, India with
experience in the building blocks of cryptography (Digital signatures, Zero-
Knowledge Proofs, Anonymous Credentials etc.) and privacy (Differential
Privacy, Noiseless Privacy, Non-Interactive Zero Knowledge etc.) and interests
in solving real life security and privacy challenges. He was a senior research
scientist at Data61, CSIRO.
---|---
|  Mohamed Ali (Dali) Kaafar is a Professor at the Faculty of Science and
Engineering at Macquarie University and the Executive Director of the Optus-
Macquarie University Cyber Security Hub. He is also the founder of the
Information Security and Privacy group at CSIRO Data61. Prior to that, Dali
was the research leader of the Data Privacy and Mobile systems group at NICTA
and Senior principal researcher at INRIA, the French research institution of
computer science and automation. He received his PhD from University of Nice
Sophia Antipolis and INRIA in France where he pioneered research in the
security of Internet Coordinate Systems. Prof. Kaafar is an associate editor
of IEEE Transactions on Information Forensics & Security and serves in the
Editorial Board of the Journal on Privacy Enhancing Technologies. He published
over 300 scientific peer-reviewed papers. He received several awards including
the INRIA Excellence of research National Award, and the Andreas Pfitzman
award from the Privacy Enhancing Technologies symposium in 2011. In 2019, he
has also been awarded the prestigious and selective Chinese Academy of
Sciences President’s Professorial fellowship Award.
---|---