*latexText page 0 contains only floats [caption] [subfloat] hyperrefToken not allowed in a PDF string

# Frequency Estimation of Evolving Data Under
Local Differential Privacy

Héber H. Arcolezi∗ Inria and École Polytechnique (IPP) heber.hwang-
<EMAIL_ADDRESS>,  Carlos Pinzón∗ Inria and École Polytechnique (IPP)
<EMAIL_ADDRESS>,  Catuscia Palamidessi  Inria and École Polytechnique
(IPP<EMAIL_ADDRESS>and  Sébastien Gambs  Université du Québec
à Montréal, UQAM<EMAIL_ADDRESS>
###### Abstract.

Collecting and analyzing evolving longitudinal data has become a common
practice. One possible approach to protect the users’ privacy in this context
is to use local differential privacy (LDP) protocols, which ensure the privacy
protection of all users even in the case of a breach or data misuse. Existing
LDP data collection protocols such as Google’s RAPPOR (Erlingsson et al.,
2014) and Microsoft’s $d$BitFlipPM (Ding et al., 2017) can have longitudinal
privacy linear to the domain size $k$, which is excessive for large domains,
such as Internet domains. To solve this issue, in this paper we introduce a
new LDP data collection protocol for longitudinal frequency monitoring named
LOngitudinal LOcal HAshing (LOLOHA) with formal privacy guarantees. In
addition, the privacy-utility trade-off of our protocol is only linear with
respect to a reduced domain size $2\leq g\ll k$. LOLOHA combines a domain
reduction approach via local hashing with double randomization to minimize the
privacy leakage incurred by data updates. As demonstrated by our theoretical
analysis as well as our experimental evaluation, LOLOHA achieves a utility
competitive to current state-of-the-art protocols, while substantially
minimizing the longitudinal privacy budget consumption by up to $k/g$ orders
of magnitude.

∗ These are co-first authors that contributed equally to this work.

††copyright: rightsretained††doi: ††isbn: 978-3-89318-092-9††conference: 26th
International Conference on Extending Database Technology (EDBT); 28th
March-31st March, 2023; Ioannina, Greece††journalyear: 2023

##  1\. Introduction

Estimating histograms of evolving categorical data is a fundamental task in
data analysis and data mining that requires collecting and processing data in
a continuous manner. A typical instance of such a problem is the online
monitoring performed on software applications (Bittau et al., 2017), for
example for error reporting (Glerum et al., 2009), to find commonly typed
emojis (Apple Differential Privacy Team, 2017), as well as to measure the
users’ system usage statistics (Ding et al., 2017). However, the data
collected can contain sensitive information such as location, health
information, preferred webpage, etc. Thus, the direct collection and storage
of users’ raw data on a centralized server should be avoided to preserve their
privacy. To address this issue, recent works have proposed several mechanisms
satisfying Differential Privacy (DP) (Dwork, 2006; Dwork et al., 2006, 2014)
in the distributed setting in which an individual can directly randomize her
own profile locally, referred to as Local DP (LDP) (Kasiviswanathan et al.,
2008; Duchi et al., 2013a, b).

One of the strengths of LDP is its simple trust model: since each user
perturbs her data locally, user privacy is protected even if the server is
malicious. For instance, some big tech companies have chosen to operate some
of their applications in the local model, reporting the implementation of LDP
protocols to collect statistics on well-known systems such as Google Chrome
browser (Erlingsson et al., 2014), Apple iOS/macOS (Apple Differential Privacy
Team, 2017), and Windows 10 operating system (Ding et al., 2017)).

Existing LDP protocols for frequency estimation typically focus on one-time
computation (Feldman et al., 2022; Acharya et al., 2019; Wang et al., 2017;
Kairouz et al., 2016a, b; Cormode et al., 2021; Bassily and Smith, 2015;
Bassily et al., 2017). However, considering both evolving data and the
continuous monitoring together, pose a significant challenge under LDP
guarantees. For instance, the naïve solution in which an LDP computation is
repeated, will quickly increase the privacy loss leading to large values of
$\epsilon$ due to the sequential composition theorem in DP (Dwork et al.,
2014). To tackle this issue, most state-of-the-art solutions relies on
memoization (Erlingsson et al., 2014; Ding et al., 2017; Erlingsson et al.,
2020; Arcolezi et al., 2021b, 2022a).

Initially proposed by Erlingsson, Pihur, and Korolova (Erlingsson et al.,
2014), the memoization-based RAPPOR protocol allows a user to memorize
randomized versions of their true data and consistently reuse it when the same
true value occurs. In addition, to improve privacy (_e.g._ , minimize data
change detection and/or tracking), the RAPPOR (Erlingsson et al., 2014)
protocol applies a second round of sanitization to the memoized value.
However, the longitudinal privacy protection of RAPPOR only works if the
underlying true value never or rarely changes (or changes in an uncorrelated
fashion), which is unrealistic for evolving data (_e.g._ , the number of
seconds an application is used) as the privacy loss is proportional to the
number of data changes, _i.e._ , the domain size $k$ in the worst-case.

To address this issue, Ding, Kulkarni, and Yekhanin (Ding et al., 2017) have
proposed a new LDP protocol named $d$BitFlipPM that improved memoization by
mapping several values to the same randomized value. More precisely,
$d$BitFlipPM partitions the original values into $b\leq k$ buckets (_e.g._ ,
with equal widths), which allows close values to be mapped to the same bucket.
Afterwards, each user only samples $d\leq b$ buckets to minimize the number of
bits to be randomized. Note that these two steps contributes to the
information loss. Another limitation of $d$BitFlipPM is the possibility of
detecting data changes (Xue et al., 2022) on the fly since the true value will
fall in a different bucket, there will be a higher probability of changing the
randomization of the $d$ bits. Even if this only indicates that the user’s
value has changed, not what it was or is (Erlingsson et al., 2014; Ding et
al., 2017), there are still some privacy implications with respect to the type
of inference an adversary can perform, especially if there are correlation
patterns to be exploited (Tang et al., 2017; Naor and Vexler, 2020). Finally,
$d$BitFlipPM’s privacy loss can still be proportional to the number of bucket
changes, _i.e._ , the new domain size $b$ in the worst case.

A different line of work has taken into account the infrequent data changes on
the user side, hereafter referred to as data change-based (Joseph et al.,
2018; Erlingsson et al., 2019; Xue et al., 2022; Ohrimenko et al., 2022). For
instance, Joseph et al. (Joseph et al., 2018) have proposed a new LDP protocol
THRESH for monitoring statistics (_e.g._ , frequency) based on two sub-
routines: voting and estimation, which requires splitting the privacy budget.
The main idea of THRESH is to update through voting the global estimate only
when it becomes sufficiently inaccurate. However, privacy budget splitting
under LDP guarantees is sub-optimal (Wang et al., 2017; Arcolezi et al.,
2022a; Wang et al., 2019; Arcolezi et al., 2021b; Nguyên et al., 2016;
Erlingsson et al., 2020; Arcolezi et al., 2021a), which negatively impacts the
data utility. Moreover, the authors in (Erlingsson et al., 2019; Ohrimenko et
al., 2022) proposed the sanitization and report of data changes for frequency
monitoring by assuming a limited number of data changes and longitudinal
Boolean data, though it can be extend to larger domain. This leads to an
accuracy that decays linearly (or sub-linearly) in the number of data changes.
Finally, in a recent work, Xue et al. (Xue et al., 2022) have proposed a new
LDP protocol DDRM (Dynamic Difference Report Mechanism) based on difference
trees. However, DDRM assumes that the user’s private sequence exhibit
continuity (_i.e._ , do not fluctuate significantly) and was mainly designed
for longitudinal Boolean data. Besides, DDRM requires a privacy budget
allocation scheme that depends on the number of data collections as well as to
split the privacy budget when extending to a larger domain (_i.e._ , sub-
optimal).

Main contributions. In this paper, we address the limitations of memoization-
based protocols (Erlingsson et al., 2014; Ding et al., 2017; Arcolezi et al.,
2022a; Erlingsson et al., 2020) without imposing any restriction on the number
of data changes and/or on the number of data collections as in data change-
based protocols (Joseph et al., 2018; Erlingsson et al., 2019; Xue et al.,
2022; Ohrimenko et al., 2022). More precisely, we propose a novel LDP protocol
with formal privacy guarantees for longitudinal frequency estimation of
evolving counter (or categorical) data.

Our protocol, hereafter named LOngitudinal LOcal HAshing (LOLOHA), combines a
domain reduction approach through local hashing (Bassily and Smith, 2015; Wang
et al., 2017) with the memoization solution of RAPPOR using two rounds of
sanitization (Erlingsson et al., 2014; Arcolezi et al., 2022a). The main
strength of LOLOHA is that the longitudinal privacy-utility trade-off is
linear only on the new (reduced) domain size $g$, in which $2\leq g\ll k$ is a
tunable hyper-parameter. This way, the worst-case longitudinal privacy loss of
LOLOHA has a significant $k/g$ or $b/g$ decrease factor in comparison with
RAPPOR and $d$BitFlipPM, respectively.

Indeed, LOLOHA can be tuned for strong longitudinal privacy by selecting $g=2$
(BiLOLOHA protocol). To maximize LOLOHA’s utility, we also find the optimal
$g$ value (OLOLOHA protocol). Experimental evaluations demonstrate the
effectiveness of LOLOHA with respect to the quality of frequency estimates, in
addition to substantially minimizing the longitudinal privacy loss.

We also show why LDP is generally impossible to achieve when data is
longitudinal, which motivates a definition of privacy that better suits the
longitudinal scenario. This is in opposition with the common and
mathematically equivalent path in the literature of claiming a protocol to be
LDP but assuming that the evolving data is uncorrelated or constant in time,
which we believe not be realistic in real-life deployments.

In summary, the main contributions of this paper are three-fold:

  * •

We propose the LOLOHA protocol for longitudinal frequency monitoring under LDP
guarantees.

  * •

We prove the longitudinal privacy and accuracy guarantees of LOLOHA through
theoretical analysis and compare it to existing protocols.

  * •

We show the performance of LOLOHA numerically and experimentally, using both
real-world and synthetic datasets.

Outline. The remainder of this paper is organized as follows. First, in
Section 2, we provide the problem definition and review LDP and existing
longitudinal LDP protocols. Next, we present and analyze our LOLOHA protocols
in Section 3. In Section 4, we give a theoretical comparison of LOLOHA and
state-of-the-art LDP protocols before presenting and interpreting the
experimental results in Section 5. Finally, in Section 6, we review related
work before concluding with future perspectives in Section 7.

##  2\. Preliminaries

In this section, we present the problem considered and we review the LDP
privacy model and relevant protocols.

Notation. For denoting sets, we will use italic uppercase letters $V$, $U$,
etc, and we write ${[1..n]}=\\{1,\ldots,n\\}$. For a vector x (bold lowercase
letters), ${\mathbf{x}}_{i}$ represents the value of its $i$-th coordinate.
Finally, we denote randomized protocols as ${\mathcal{M}}$.

###  2.1. Problem Statement

We consider the situation in which a server collects data from a distributed
group of users while requiring the protection of privacy for each user,
through LDP. The server collects sanitized data over time from each member of
the group with respect to a fixed discrete random variable (_e.g._ , daily
usage of a mobile application). Its objective is to estimate the true
frequencies, or histograms, of the random variable as well as its evolution
over time. We aim to provide the server with an optimized combination of two
algorithms: one for the users, who must sanitize locally their data before
sending it, and another for the server, which wants to aggregate data and
perform the estimation accurately.

Formally, there are $n$ users $U=\\{u_{1},\ldots,u_{n}\\}$ and a random
variable taking values in a set $V$ of size $k$ with true frequencies
$\\{f(v)\\}_{v\in V}$, which may vary over time. Each user $u\in U$, holds a
private sequence of values
$\textbf{v}^{(u)}=\left[v^{(u)}_{1},v^{(u)}_{2},\ldots,v^{(u)}_{\tau}\right]$,
in which $v_{t}^{(u)}$ represents the discrete value $v\in V$ of user $u$ at
time step $t\in{[1..\tau]}$. At each time step $t$, upon collecting the
sanitized values of all $n$ users, the server will estimate a $k$-bins
histogram $\\{\hat{f}(v)\\}_{v\in V}$ in a way that minimizes the Mean Squared
Error (MSE) with respect to $\\{f(v)\\}_{v\in V}$. For all the algorithms
presented hereafter, the estimation $\hat{f}(v)$ is unbiased (_i.e._ ,
$\mathbb{E}(\hat{f}(v))=f(v)$). As a consequence, the MSE is equivalent to the
variance as:

$\mathrm{MSE}=\frac{1}{|V|}\sum_{v\in
V}\mathbb{E}\left[\left(\hat{f}(v)-f(v)\right)^{2}\right]=\frac{1}{|V|}\sum_{v\in
V}\mathbb{V}[\hat{f}(v)]\textrm{.}$

###  2.2. Local Differential Privacy

Privacy model. In this paper, we use LDP (Local Differential Privacy)
(Kasiviswanathan et al., 2008; Duchi et al., 2013a, b) as the privacy model
considered, which is formally defined as follows.

###### Definition 2.1 ($\epsilon$-Local Differential Privacy).

A randomized algorithm ${{\mathcal{M}}}$ satisfies $\epsilon$-local-
differential-privacy ($\epsilon$-LDP), where $\epsilon>0$, if for any pair of
input values $v_{1},v_{2}\in Domain({\mathcal{M}})$ and any possible output
$x^{\prime}$ of ${{\mathcal{M}}}$:

$\Pr[{{\mathcal{M}}}(v_{1})=x^{\prime}]\leq
e^{\epsilon}\cdot\Pr[{{\mathcal{M}}}(v_{2})=x^{\prime}]\textrm{.}$

In essence, LDP guarantees that it is unlikely for the data aggregator to
reconstruct the input data. The privacy loss $\epsilon$ controls the privacy-
utility trade-off for which lower values of $\epsilon$ result in tighter
privacy protection. Similar to central DP, LDP also has several fundamental
properties, such as robustness to post-processing and composition (Dwork et
al., 2014).

###### Proposition 2.2 (Post-Processing (Dwork et al., 2014)).

If ${\mathcal{M}}$ is $\epsilon$-LDP, then $f({\mathcal{M}})$ is also
$\epsilon$-LDP for any function $f$.

###### Proposition 2.3 (Sequential Composition (Dwork et al., 2014)).

Let ${\mathcal{M}}_{t}$ be $\epsilon_{t}$-LDP mechanism, for $t\in[\tau]$.
Then, the sequence of outputs
$[{\mathcal{M}}_{1}(v),\ldots,{\mathcal{M}}_{\tau}(v)]$ is
$\sum_{t=1}^{\tau}\epsilon_{t}$-LDP. Moreover, if ${\mathcal{M}}$ is an
$\epsilon$-LDP mechanism and ${\mathbf{v}}$ is a finite sequence of $k$
values, then the sequence of outputs
$[{\mathcal{M}}(v_{1}),\ldots,{\mathcal{M}}(v_{k})]$ is $k\epsilon$-LDP.

###  2.3. LDP Frequency Estimation Protocols

In this section, we review five state-of-the-art LDP frequency estimation
protocols, which are often used as building blocks for more complex tasks
(_e.g._ , heavy hitter estimation (Bassily and Smith, 2015; Bassily et al.,
2017), machine learning (Mahawaga Arachchige et al., 2020), and private
frequency monitoring (Ding et al., 2017; Erlingsson et al., 2014; Arcolezi et
al., 2022a)).

####  2.3.1. Generalized Randomized Response (GRR)

The GRR (Kairouz et al., 2016a, b) protocol generalizes the Randomized
Response (RR) technique proposed by Warner (Warner, 1965) for $k\geq 2$ while
satisfying LDP.

Fix a parameter $\epsilon>0$ and let
$p\coloneqq\frac{e^{\epsilon}}{e^{\epsilon}+k-1}\in(0,1)$ in which $k=|V|$.
For each $v\in V$, let $\eta_{\neq v}\in V$ be a uniform (_i.e._ , exogenous
noise) random variable over $V\setminus\\{v\\}$. We let
${\mathcal{M}_{\text{GRR}}}:V\to V$ be the random variable given by:

${\mathcal{M}_{\text{GRR}}(v;\epsilon)}\coloneqq\begin{cases}v,&\textrm{w.p.
}p\\\ \eta_{\neq v},&\textrm{w.p. }1-p\textrm{.}\end{cases}$

This protocol satisfies $\epsilon$-LDP, because $\frac{p}{q}=e^{\epsilon}$
(Kairouz et al., 2016a), in which $q\coloneqq\nicefrac{{(1-p)}}{{(k-1)}}$
determines the probability of the response being any fixed noise value
different of $v$. To estimate the normalized frequency of $v\in V$, one counts
how many times $v$ is reported, expressed as $C(v)$, and then computes:

(1) $\hat{f}(v)=\frac{C(v)-nq}{n(p-q)}\textrm{,}$

in which $n$ is the total number of users. In (Wang et al., 2017), it was
proven that Eq. (1) is an unbiased estimator (_i.e._ ,
$\mathbb{E}(\hat{f}(v))=f(v)$).

####  2.3.2. Local Hashing (LH)

LH protocols (Wang et al., 2017) can handle a large domain size $k$ by first
using hash functions to map an input value to a smaller domain of size $g\geq
2$ (typically $g\ll k)$, and then applying GRR to the hashed value.

Fix $\epsilon>0$ and let ${\mathcal{M}_{\text{GRR}}}:{[1..g]}\to{[1..g]}$ be
the GRR mechanism with parameter $\epsilon$ and assuming the input-output
domain to be ${[1..g]}$ instead of $V$, so that the size is $g$ instead of
$k$. In local hashing, each user selects at random a hashing function
$\mathrm{H}$ from a family of universal hash functions, and reports the pair
$\langle\mathrm{H},{\mathcal{M}_{\text{GRR}}(x;\epsilon)}\rangle$, in which
$x=\mathrm{H}(v)$.

The hash values will remain unchanged with probability
$p=\frac{e^{\epsilon}}{e^{\epsilon}+g-1}$ and switch to any different fixed
value in ${[1..g]}$ with probability $q=\frac{1}{e^{\epsilon}+g-1}$. This
means that for each hash value $x\in{[1..g]}$, it holds that:

$\Pr[{\mathcal{M}_{\text{GRR}}(\mathrm{H}(v);\epsilon)}=x]=\begin{cases}p,&\textrm{if
}x=\mathrm{H}(v)\\\ q,&\textrm{otherwise.}\end{cases}$

Let $\langle\mathrm{H}^{u},x^{u}\rangle$ be the report from user $u\in U$. The
server can obtain the unbiased estimation of $v\in V$, with Eq. (1) by setting
$q=\frac{1}{g}$ and $C(v)=|\\{u\in U\mid\mathrm{H}^{u}(v)=x^{u}\\}|$ (Wang et
al., 2017).

The authors in (Wang et al., 2017) describe two LH protocols that differ on
how $g$ is selected: (1) Binary LH (BLH) that selects $g=2$ and (2) Optimal LH
(OLH) that selects $g=\lfloor e^{\epsilon}+1\rceil$ (rounded to closest
integer).

####  2.3.3. Unary Encoding (UE)

UE protocols interpret the user’s input $v\in V$, as a one-hot $k$-dimensional
vector. More precisely, $\textbf{x}=\texttt{UE}(v)$ is a binary vector with
only the bit at the position corresponding to $v$ set to 1 and the other bits
set to 0. The perturbation function of UE protocols randomizes the bits from x
independently with probabilities:

(2)
$\forall{i\in[k]}:\quad\Pr[\textbf{x}_{i}^{\prime}=1]=\begin{cases}p,\textrm{
if }\textbf{x}_{i}=1\textrm{,}\\\ q,\textrm{ if
}\textbf{x}_{i}=0\textrm{.}\end{cases}$

Afterwards, the client sends $\textbf{x}^{\prime}$ to the server. The authors
in (Wang et al., 2017) describe two UE protocols that depend on the parameters
$p$ and $q$ in Eq. (2): (1) Symmetric UE (SUE) (Erlingsson et al., 2014),
which selects $p=\frac{e^{\epsilon/2}}{e^{\epsilon/2}+1}$ and
$q=\frac{1}{e^{\epsilon/2}+1}$ such that $p+q=1$, and (2) Optimal UE (OUE),
which selects $p=\frac{1}{2}$ and $q=\frac{1}{e^{\epsilon}+1}$.

The estimation method used in Eq. (1) applies equally to both UE protocols, in
which $C(v)$ represents the number of times the bit corresponding to $v$ has
been reported. Last, both SUE and OUE protocols satisfy $\epsilon$-LDP for
$\epsilon=ln\left(\frac{p(1-q)}{(1-p)q}\right)$ (Wang et al., 2017).

###  2.4. Existing Longitudinal LDP Frequency Estimation Protocols

For privately monitoring the frequency of values of a population, the simplest
way is that each user adds independent fresh noise to $v$ in each data
collection $t\in{[1..\tau]}$ following one of the LDP protocols described in
the previous section. However, this solution is vulnerable to “averaging
attacks” in which an adversary can estimate the true value from observing
multiple randomized versions of it. To avoid this averaging attack, the
memoization approach (Erlingsson et al., 2014) was designed to enable
longitudinal collections through memorizing a randomized version of the true
value $v$ and consistently reusing it (Ding et al., 2017; Arcolezi et al.,
2021b) or reusing it as the input to a second round of sanitization (_i.e._ ,
chaining two LDP protocols) (Erlingsson et al., 2014; Arcolezi et al., 2022a;
Erlingsson et al., 2020). The next four subsections describe state-of-the-art
memoization-based protocols.

####  2.4.1. RAPPOR Protocol

The utility-oriented version of RAPPOR (Erlingsson et al., 2014) is based on
the SUE protocol, which encodes the user’s input $v\in V$ as a $k$-dimensional
bit-vector and randomizes each bit independently. More specifically, for each
value $v\in V$, the user encodes $\textbf{x}=\texttt{UE}(v)$ and randomizes x
as follows:

Step 1. Permanent RR (PRR): Memoize $\textbf{x}^{\prime}$ such that:

$\forall{i\in[k]}:\quad\Pr[\textbf{x}_{i}^{\prime}=1]=\begin{cases}p_{1}=\frac{e^{{\epsilon_{\infty}}/2}}{e^{{\epsilon_{\infty}}/2}+1},\textrm{
if }\textbf{x}_{i}=1\textrm{,}\\\
q_{1}=\frac{1}{e^{{\epsilon_{\infty}}/2}+1},\textrm{ if
}\textbf{x}_{i}=0\textrm{,}\end{cases}$

in which $p_{1}$ and $q_{1}$ control the level of longitudinal
${\epsilon_{\infty}}$-LDP for
${\epsilon_{\infty}}=ln\left(\frac{p_{1}(1-q_{1})}{(1-p_{1})q_{1}}\right)$
(Erlingsson et al., 2014). This step is carried out only once for each value
$v\in V$ that the user has. Thus, the value $\textbf{x}^{\prime}$ shall be
reused as the basis for all future reports of $v$.

Step 2. Instantaneous RR (IRR): Generate $\textbf{x}^{\prime\prime}$ such
that:

$\forall{i\in[k]}:\quad\Pr[\textbf{x}_{i}^{\prime\prime}=1]=\begin{cases}p_{2},\textrm{
if }\textbf{x}_{i}^{\prime}=1\textrm{,}\\\ q_{2},\textrm{ if
}\textbf{x}_{i}^{\prime}=0\textrm{.}\end{cases}$

This second step is carried out each time $t\in{[1..\tau]}$ a user report the
value $v$. RAPPOR’s deployment selected $p_{2}=0.75$ and $q_{2}=0.25$
(Erlingsson et al., 2014; Wang et al., 2017) (_i.e._ , also symmetric). The
RAPPOR protocol that chains two SUE protocols is referred to as L-SUE in
(Arcolezi et al., 2022a; Arcolezi et al., 2022b). We provide the calculation
of parameters $p_{2}$ and $q_{2}$ in the repository (art, [n.d.]). Note that
${\epsilon_{\infty}}$ corresponds to an upper bound for each value $v$ as
$t\rightarrow\infty$. The privacy guarantees of the IRR step degrade according
to the number of reports $t\in{[1..\tau]}$ (Erlingsson et al., 2014;
Erlingsson et al., 2020).

With two rounds of sanitization, each consisting of an LDP protocol
parametrized with $p,q$, the unbiased estimator in Eq. (1) is now extended to
(Arcolezi et al., 2022a; Erlingsson et al., 2014):

(3)
$\hat{f}_{L}(v)=\frac{\frac{C(v)-nq_{2}}{(p_{2}-q_{2})}-nq_{1}}{n(p_{1}-q_{1})}=\frac{C(v)-nq_{1}(p_{2}-q_{2})-nq_{2}}{n(p_{1}-q_{1})(p_{2}-q_{2})}\textrm{,}$

in which $p_{1}$ and $q_{1}$ are the parameters of the LDP protocol used in
the first step while $p_{2}$ and $q_{2}$ are the parameters of the LDP
protocol used in the second step.

In (Arcolezi et al., 2022a), it was proven that Eq. (3) is an unbiased
estimator (_i.e._ , $\mathbb{E}(\hat{f}_{L}(v))=f(v)$) and that for any value
$v\in V$, the variance $\mathbb{V}$ of the estimator $\hat{f}_{L}(v)$ in Eq.
(3) is:

(4)
$\begin{gathered}\mathbb{V}[\hat{f}_{L}(v)]=\frac{\gamma(1-\gamma)}{n(p_{1}-q_{1})^{2}(p_{2}-q_{2})^{2}}\textrm{,
where}\\\
\gamma=f(v)\left(2p_{1}p_{2}-2p_{1}q_{2}+2q_{2}-1\right)+p_{2}q_{1}+q_{2}(1-q_{1})\textrm{.}\end{gathered}$

In this paper, we will use the approximate variance $\mathbb{V}^{*}$, in which
$f(v)=0$ in Eq. (4), which gives:

(5)
$\mathbb{V}^{*}\left[\hat{f}_{L}(v)\right]=\frac{\left(p_{2}q_{1}-q_{2}\left(q_{1}-1\right)\right)\left(-p_{2}q_{1}+q_{2}\left(q_{1}-1\right)+1\right)}{n(p_{1}-q_{1})^{2}(p_{2}-q_{2})^{2}}\textrm{.}$

Therefore, one can obtain the RAPPOR approximate variance
$\mathbb{V}^{*}[\hat{f}_{\textrm{RAPPOR}}(v)]$ by replacing the resulting
$p_{1},q_{1},p_{2},q_{2}$ parameters into Eq. (5).

####  2.4.2. Optimized Longitudinal UE Protocol

The authors in (Arcolezi et al., 2022a) analyzed all four combinations between
OUE and SUE in both PRR and IRR steps. The optimized protocol named L-OSUE
chains the OUE protocol (PRR step) and the SUE protocol (IRR step). Thus, for
each value $v\in V$, the user encodes $\textbf{x}=\texttt{UE}(v)$ and
randomizes x as follows:

Step 1. PRR: Memoize $\textbf{x}^{\prime}$ such that:

$\forall{i\in[k]}:\quad\Pr[\textbf{x}_{i}^{\prime}=1]=\begin{cases}p_{1}=\frac{1}{2},\quad\quad\textrm{
if }\textbf{x}_{i}=1\textrm{,}\\\
q_{1}=\frac{1}{e^{{\epsilon_{\infty}}}+1},\textrm{ if
}\textbf{x}_{i}=0\textrm{,}\end{cases}$

in which $p_{1}$ and $q_{1}$ control the level of longitudinal
${\epsilon_{\infty}}$-LDP as
$e^{{\epsilon_{\infty}}}=\frac{p_{1}(1-q_{1})}{q_{1}(q-p_{1})}$ (Erlingsson et
al., 2014; Arcolezi et al., 2022a). The value $\textbf{x}^{\prime}$ shall be
reused as the basis for all future reports when the real value is $v$.

Step 2. IRR: Generate $\textbf{x}^{\prime\prime}$ such that:

$\forall{i\in[k]}:\quad\Pr[\textbf{x}_{i}^{\prime\prime}=1]=\begin{cases}p_{2},\quad\quad\quad\quad\textrm{
if }\textbf{x}_{i}^{\prime}=1\textrm{,}\\\ q_{2}=1-p_{2},\textrm{ if
}\textbf{x}_{i}^{\prime}=0\textrm{.}\end{cases}$

in which
$p_{2}=\frac{e^{\epsilon_{\infty}}e^{\epsilon_{1}}-1}{e^{\epsilon_{\infty}}-e^{\epsilon_{1}}+e^{{\epsilon_{\infty}}+{\epsilon_{1}}}-1}$
and $\textbf{x}^{\prime\prime}$ is the report to be sent to the server. Let
$p_{s}=\Pr[\textbf{x}_{i}^{\prime\prime}=1|\textbf{x}_{i}=1]=p_{1}p_{2}+(1-p_{1})q_{2}$
and
$q_{s}=\Pr[\textbf{x}_{i}^{\prime\prime}=1|\textbf{x}_{i}=0]=q_{1}p_{2}+(1-q_{1})q_{2}$.
For the first report, the L-OSUE protocol satisfies ${\epsilon_{1}}$-LDP as
$e^{{\epsilon_{1}}}=\frac{p_{s}(1-q_{s})}{(1-p_{s})q_{s}}$ (Arcolezi et al.,
2022a; Erlingsson et al., 2014).

Similar to RAPPOR, the estimated frequency $\hat{f}_{\textrm{L-OSUE}}(v)$ that
a value $v\in V$ occurs, can be computed using Eq. (3). One can also obtain
the L-OSUE approximate variance $\mathbb{V}^{*}[\hat{f}_{\textrm{L-OSUE}}(v)]$
by replacing the resulting $p_{1},q_{1},p_{2},q_{2}$ parameters into Eq. (5).

####  2.4.3. Longitudinal GRR (L-GRR)

The L-GRR (Arcolezi et al., 2022a) protocol chains GRR in both PRR and IRR
steps. Therefore, for each value $v\in V$, the user randomizes $v$ as follows:

Step 1. PRR: Memoize $x^{\prime}$ such that:

$x^{\prime}=\begin{cases}v,&\textrm{w.p.}\
p_{1}=\frac{e^{{\epsilon_{\infty}}}}{e^{{\epsilon_{\infty}}}+k-1}\textrm{,}\\\
\tilde{v}\in V\setminus\\{v\\},&\textrm{w.p.}\
q_{1}=\frac{1-p_{1}}{k-1}\textrm{,}\\\ \end{cases}$

in which $p_{1}$ and $q_{1}$ control the level of longitudinal
${\epsilon_{\infty}}$-LDP as $e^{{\epsilon_{\infty}}}=\frac{p_{1}}{q_{1}}$
(Kairouz et al., 2016a; Arcolezi et al., 2022a). The value $x^{\prime}$ shall
be reused as the basis for all future reports on the real value $v$.

Step 2. IRR: Generate a report $x^{\prime\prime}$ such that:

$x^{\prime\prime}=\begin{cases}x^{\prime},&\textrm{w.p.}\ p_{2}\textrm{,}\\\
\tilde{x}\in V\setminus\\{x^{\prime}\\},&\textrm{w.p.}\
q_{2}=\frac{1-p_{2}}{k-1}\textrm{,}\\\ \end{cases}$

in which
$p_{2}=\frac{e^{{\epsilon_{\infty}}+{\epsilon_{1}}}-1}{-ke^{\epsilon_{1}}+\left(k-1\right)e^{{\epsilon_{\infty}}}+e^{\epsilon_{1}}+e^{{\epsilon_{1}}+{\epsilon_{\infty}}}-1}$
and $x^{\prime\prime}$ is the report to be sent to the server. Let
$p_{s}=\Pr\left[x^{\prime\prime}=v|v\right]=p_{1}p_{2}+q_{1}q_{2}$ and
$q_{s}=\Pr[x^{\prime\prime}=v|\tilde{v}\in
V\setminus\\{v\\}]=p_{1}q_{2}+q_{1}p_{2}$. For the first report, the L-GRR
protocol satisfies ${\epsilon_{1}}$-LDP since
$e^{\epsilon_{1}}=\frac{p_{s}}{q_{s}}$ (Arcolezi et al., 2022a).

The estimated frequency $\hat{f}_{\textrm{L-GRR}}(v)$ that a value $v$ occurs
can also be obtained using Eq. (3). Besides, one can compute the L-GRR
approximate variance $\mathbb{V}^{*}[\hat{f}_{\textrm{L-GRR}}(v)]$ by
replacing the resulting $p_{1},q_{1},p_{2},q_{2}$ parameters into Eq. (5).

####  2.4.4. dBitFlipPM Protocol

The $d$BitFlipPM (Ding et al., 2017) protocol was proposed to improve the
memoization solution of RAPPOR (Erlingsson et al., 2014) by mapping several
true values to the same noisy response at the cost of losing information due
to generalization. This is done by first partitioning the original domain $V$
into $b$ buckets (_i.e._ , new domain size $2\leq b\leq k$) using a function
$\mathtt{bucket}:V\to{[1..b]}$, such that close values will fall into the same
bucket. Next, each user randomly draws $d$ bucket numbers without replacement
from ${[1..b]}$, denoted by $j_{1},j_{2},\ldots,j_{d}$, and fixes them for all
future data collections. Then, for each $v\in V$, the user sends a sanitized
vector
$\textbf{x}^{\prime}=\left[(j_{1},x_{j_{1}}),\ldots,(j_{d},x_{j_{d}})\right]$
parameterized with the privacy guarantee ${\epsilon_{\infty}}$ as follows:

$\forall{l\in{[1..d]}}:\Pr[x_{j_{l}}=1]=\begin{cases}p=\frac{e^{{\epsilon_{\infty}}/2}}{e^{{\epsilon_{\infty}}/2}+1},\textrm{
if }\mathtt{bucket}(v)=j_{l}\\\
q=\frac{1}{e^{{\epsilon_{\infty}}/2}+1},\textrm{ if }\mathtt{bucket}(v)\neq
j_{l}\end{cases}\textrm{.}$

In other words, users inform the server which bits are sampled as well as
their perturbed values, but the server does not receive any information about
the remaining $b-d$ bits. The server can estimate the number of times each
bucket in ${[1..b]}$ has been reported with Eq. (1) by replacing $n$ with
$\frac{nd}{b}$ as each user only sampled $d$ bits among $b$ buckets.

In contrast to RAPPOR, there is no second round of sanitization, which means
the user runs $d$BitFlipPM with ${\epsilon_{\infty}}$-LDP for all $b$ buckets,
with randomization applied to the $d$ fixed bits $j_{1},j_{2},\ldots,j_{d}$
and memoizes the response. This approach adds uncertainty to the real value
because multiple (close) values will be mapped to the same bucket. The highest
protection is given when $d=1$ (Ding et al., 2017), which will minimize the
chances (to some extent) of detecting high data changes.

##  3\. LOLOHA

In this section, we introduce our LOLOHA (Longitudinal Local Hashing) protocol
for frequency monitoring throughout time under LDP constraints, and we analyze
its utility and privacy.

The privacy analysis of longitudinal protocols requires special treatment
because, since they are stateful, they cannot be modeled as mechanisms mapping
values into values, but rather sequences into sequences. This makes the LDP
constraint too strong in the long term as shown in the following theorem.

###### Theorem 3.1.

(LDP cannot be satisfied when $\tau\to\infty$) Consider a randomized
longitudinal mechanism $\vec{\mathcal{M}}:{[1..n]}^{\tau}\to{[1..m]}^{\tau}$
mapping an input sequence $X_{1},\ldots,X_{\tau}$ to an output sequence
$Y_{1},\ldots,Y_{\tau}$, for some positive integer $\tau$. For the sake of
utility of each reported value $Y_{t}$ ($0$-LDP means total detriment of
utility), assume some negligible but positive fixed $\alpha>0$ such that the
mechanism for generating $Y_{t}$ from $X_{t}$ and the history
$X_{1},Y_{1},\ldots,X_{t-1},Y_{t-1}$ is not $\alpha$-LDP. If
$\tau\geq\epsilon/\alpha$ then $\vec{\mathcal{M}}$ is not $\epsilon$-LDP.

###### Proof.

Let
$y_{1}=\arg\max_{y}\frac{\max_{x}P(X_{1}=x|Y_{1}=y)}{\min_{x}P(X_{1}=x|Y_{1}=y)}$,
and call $x_{1}^{+}$ and $x_{1}^{-}$ to the values that respectively maximize
and minimize $P(X_{1}=x|Y_{1}=y_{1})$. By the minimal utility assumption,
$\frac{p(x_{1}^{+}|y_{1})}{p(x_{1}^{-}|y_{1})}>e^{\alpha}$.

Let
$y_{2}=\arg\max_{y}\frac{\max_{x}P(X_{2}=x|Y_{2}=y,Y_{1}=y_{1},X_{1}=x_{1})}{\min_{x}P(X_{2}=x|Y_{2}=y,Y_{1}=y_{1},X_{1}=x_{1})}$,
and call $x_{2}^{+}$ and $x_{2}^{-}$ to the values that respectively maximize
and minimize $P(X_{2}=x|Y_{2}=y,Y_{1}=y_{1},X_{1}=x_{1})$. Since the output
values of the mechanism are reported one by one in temporal order, we have
$p(x_{1},x_{2}|y_{1},y_{2})=p(x_{1}|y_{1})p(x_{2}|y_{2},y_{1},x_{1})$, hence
by the minimal utility assumption and the first step,
$\frac{p(x_{1}^{+},x_{2}^{+}|y_{1},y_{2})}{p(x_{1}^{-},x_{2}^{-}|y_{1},y_{2})}=\frac{p(x_{1}^{+}|y_{1})p(x_{2}^{+}|y_{2},y_{1},x_{1}^{+})}{p(x_{1}^{-}|y_{1})p(x_{2}^{-}|y_{2},y_{1},x_{1}^{-})}>e^{2\alpha}$.

Repeating this process inductively yields three sequences $y_{i}$, $x_{i}^{+}$
and $x_{i}^{-}$ of length $\tau$ such that
$\frac{p(x_{1}^{+},\ldots,x_{\tau}^{+}|y_{1},\ldots,y_{\tau})}{p(x_{1}^{-},\ldots,x_{\tau}^{-}|y_{1},\ldots,y_{\tau})}>e^{\tau\alpha}$.

This makes it impossible for the mechanism to be $\epsilon$-LDP for any
$\tau\geq\epsilon/\alpha$. ∎

For instance, assume that a user has a secret sequence
${\mathbf{v}}=[1,1,1,3,1,2,1,1,3]$ ($\tau=9$ time steps), and reports
$\vec{\mathcal{M}}({\mathbf{v}})\coloneqq[{\mathcal{M}}(v_{1}),\ldots,{\mathcal{M}}(v_{9})]$,
in which ${\mathcal{M}}$ is the memoization mechanism $(1\mapsto 2;2\mapsto
2;3\mapsto 3)$ that reuses the sanitized report. The server receives
$[2,2,2,3,2,2,2,2,3]$, hence some time-related patterns in the sequence are
exposed, but the memoization protects the uncertainty about the user actual
values. As the sequence size grows, the vectorized memoization mechanism
$\vec{\mathcal{M}}$ that processes temporal data continues to protect the
values indefinitely, but fails to satisfy LDP. For this reason, we introduce
the following relaxed definition of privacy for longitudinal mechanisms.

###### Definition 3.2 (Longitudinal LDP).

For a longitudinal memoizing mechanism ${\mathcal{M}}:A^{\tau}\to B^{\tau}$,
in which $A={[1..k]}$, let ${\mathcal{M}}^{\star}$ denote a mechanism that
takes as input a permutation $x$ of $A$ and outputs
${\mathcal{M}}^{\star}(x):=x^{\prime\prime}$ by shuffling the $k$ entries of
$x$, yielding $x^{\prime}$, and letting
$x^{\prime\prime}_{i}:={\mathcal{M}}(x^{\prime}_{i})$ for each $i=1..k$,
sequentially. ${\mathcal{M}}$ is said to be $\epsilon$-LDP on the users’
values iff ${\mathcal{M}}^{\star}$ is $\epsilon$-LDP.

Definition 3.2 discards all information contained in time correlation by
shuffling the input and aggregates the total privacy loss after all input
values have been memoized. Moreover, Definition 3.2 corresponds to the total
privacy budget that will be consumed for sanitizing all the values of the
user.

Previous influential works, such as RAPPOR (Erlingsson et al., 2014) and
$d$BitFlipPM (Ding et al., 2017), handle the negative consequences of Theorem
3.1 implicitly by assuming that the data values (or buckets) never change or
change in an uncorrelated manner. We consider the former to be unrealistic and
the latter is insufficient to guarantee LDP, though it makes users
indistinguishable. In this paper, we privileged Definition 3.2 over extreme
assumptions on the data to be able to explain at least what is actually being
protected by the mechanism when the assumptions do not hold. Hence, we present
long term guarantees in terms of LDP on the users’ values, but also, single-
report LDP guarantees, as done in the literature, which are equivalent to LDP
assuming constant values.

###  3.1. Overview of LOLOHA

LOLOHA is inspired by the strengths of RAPPOR (Erlingsson et al., 2014)
(double sanitization to minimize data change detection) and $d$BitFlipPM (Ding
et al., 2017) (several values are mapped to the same randomized value)
protocols. More precisely, LOLOHA is based on LH for the PRR step to satisfy
${\epsilon_{\infty}}$-LDP (upper bound), which significantly reduces the
domain size. Thus, the user will uniformly choose at random a universal hash
function $\mathrm{H}$ that maps the original domain $V\rightarrow{[1..g]}$,
with $g\geq 2$ typically much smaller than $k=|V|$. Indeed, given a general
(universal) family of hash functions $\mathscr{H}$, each input value $v\in V$
is hashed into a value in ${[1..g]}$ by hash function
$\mathrm{H}\in\mathscr{H}$, and the universal property requires:

$\forall{v_{1},v_{2}}\in V,v_{1}\neq
v_{2}:\quad\underset{\mathrm{H}\in\mathscr{H}}{\Pr}\left[\mathrm{H}(v_{1})=\mathrm{H}(v_{2})\right]\leq\frac{1}{g}\textrm{.}$

In other words, approximately $k/g$ values $v\in V$ can be mapped to the same
hashed value $\mathrm{H}(v)$ in ${[1..g]}$ due to collision. After the hashing
step, to satisfy ${\epsilon_{\infty}}$-LDP, the user invokes the GRR protocol
to the hashed value $x=\mathrm{H}(v)$ and memoizes the response
$x^{\prime}={\mathcal{M}_{\text{GRR}}(x;{\epsilon_{\infty}})}$. Then, the
value $x^{\prime}$ will be reused as the basis for all future reports on the
hashed value $x$, which supports all values in set $X_{H}=\\{v\in
V\mid\mathrm{H}(v)=x\\}$. The intuition is that the user only leaks
${\epsilon_{\infty}}$ for each hashed value $x\in{[1..g]}$ as they support all
values $v\in V$ that collide to $x=\mathrm{H}(v)$. Notice that instead of
memoization, users could also pre-compute the mapping for each input value.
These two methods would be equivalent in terms of the functionality provided.

Moreover, in contrast with the $d$BitFlipPM protocol in which only close
values are mapped to the same bucket, any two values in $V$ can collide with
probability at most $1/g$. Therefore, even if the user’s value changes
periodically, correlated or in a abrupt manner, there will still be
uncertainty on the actual value $v$. However, with only this PRR step, it
would be possible to detect some of the data changes due to the randomization
of a different hash value. Therefore, LOLOHA also requires the user to apply a
second round of sanitization (_i.e._ , IRR step) to the memoized values
$x^{\prime}$ with the GRR protocol such that the first report satisfies
${\epsilon_{1}}$-LDP, for some chosen positive
${\epsilon_{1}}<{\epsilon_{\infty}}$.

###  3.2. Client-Side of LOLOHA

Algorithm 1 displays the pseudocode of LOLOHA on the client-side, which
receives as input: the true sequence of values
$\textbf{v}=\left[v_{1},v_{2},\ldots,v_{\tau}\right]$ of the user that is
running the code, a universal family $\mathscr{H}$ of hash functions
$\mathrm{H}:V\to{[1..g]}$, and the constants
${\epsilon_{1}},{\epsilon_{\infty}}$, with
$0<{\epsilon_{1}}<{\epsilon_{\infty}}$, that represent respectively the
leakage of the first report and the maximal longitudinal leakage.

Algorithm 1 Client-Side of LOLOHA.

1:Input: User longitudinal values $\left[v_{1},v_{2},\ldots,v_{\tau}\right]$,
family $\mathscr{H}$ of hash functions and constants
$0<{\epsilon_{1}}<{\epsilon_{\infty}}$.

2:Output: None. Sends data to server during execution.

3:$\mathrm{H}\leftarrow_{R}\mathscr{H}$$\triangleright$ Hash function chosen
at random

4:Send $H$.

5:${\epsilon_{\text{IRR}}}\leftarrow\ln\left(\frac{e^{{\epsilon_{\infty}}+{\epsilon_{1}}}-1}{e^{\epsilon_{\infty}}-e^{\epsilon_{1}}}\right)$

6:for each time $t\in{[1..\tau]}$ do:

7: $x\leftarrow\mathrm{H}(v_{t})$. $\triangleright$ Hash step

8: if $x$ is not memoized then:

9: $x^{\prime}\leftarrow{\mathcal{M}_{\text{GRR}}(x;{\epsilon_{\infty}})}$
over ${[1..g]}$. $\triangleright$ PRR step

10: Memoize output $x^{\prime}$ for $x$.

11: else:

12: Get memoized output $x^{\prime}$ for $x$.

13: end if

14:
$x^{\prime\prime}_{t}\leftarrow{\mathcal{M}_{\text{GRR}}(x^{\prime};\,{\epsilon_{\text{IRR}}})}$
over ${[1..g]}$. $\triangleright$ IRR step

15: Send $x^{\prime\prime}_{t}$. $\triangleright$ Sanitized data

16:end for

Privacy analysis. The privacy guarantees of Algorithm 1 are detailed in
Theorems 3.3, 3.4 and especially 3.5.

###### Theorem 3.3.

(Single report LDP of memoization)
Let ${\mathcal{M}}:V\to\mathscr{H}\times{[1..g]}$ denote the process of
applying the hash and PRR steps of LOLOHA to a single element $v\in V$,
producing ${\mathcal{M}}(v)=(\mathrm{H},x^{\prime})$. Then ${\mathcal{M}}$ is
${\epsilon_{\infty}}$-LDP.

###### Proof.

The parameters for the PRR step are
$p=\frac{e^{\epsilon_{\infty}}}{e^{\epsilon_{\infty}}+g-1}$ and
$q=\frac{1}{e^{\epsilon_{\infty}}+g-1}$. For any two possible input values
$v_{1},v_{2}\in V$ and any reported output $(\mathrm{H},x^{\prime})$, we have

$\frac{\Pr\left[(\mathrm{H},x^{\prime})|v_{1}\right]}{\Pr\left[(\mathrm{H},x^{\prime})|v_{2}\right]}\leq\frac{p}{q}=\frac{\frac{e^{{\epsilon_{\infty}}}}{e^{{\epsilon_{\infty}}}+g-1}}{\frac{1}{e^{{\epsilon_{\infty}}}+g-1}}=e^{{\epsilon_{\infty}}}\textrm{.}$

∎

###### Theorem 3.4.

(Single report LDP of LOLOHA)
Let ${\mathcal{M}}:V\to\mathscr{H}\times{[1..g]}$ denote the process of
applying the hash, PRR, and IRR steps of LOLOHA to a single element $v\in V$,
producing ${\mathcal{M}}(v)=(\mathrm{H},x^{\prime\prime})$. Then
${\mathcal{M}}$ is ${\epsilon_{1}}$-LDP.

###### Proof.

Let $(p_{1},q_{1})$ denote the parameters for the PRR step and
$(p_{2},q_{2})$, the parameters for the IRR step. That is,
$p_{1}=\frac{e^{{\epsilon_{\infty}}}}{e^{{\epsilon_{\infty}}}+g-1}$,
$q_{1}=\frac{1}{e^{{\epsilon_{\infty}}}+g-1}$,
$p_{2}=\frac{e^{{\epsilon_{\text{IRR}}}}}{e^{{\epsilon_{\text{IRR}}}}+g-1}$,
and $q_{2}=\frac{1}{e^{{\epsilon_{\text{IRR}}}}+g-1}$. If
$x^{\prime\prime}\neq\mathrm{H}(v)$, it must have changed during either the
PRR or the IRR step, and if $x^{\prime\prime}=\mathrm{H}(v)$, either it was
not changed during either step or it was changed during both. From this
analysis, it can be concluded that for each $y\in{[1..g]}$, we have

$\Pr[x^{\prime\prime}=y]=\begin{cases}p_{1}p_{2}+q_{1}q_{2},\text{ if
}y=\mathrm{H}(v)\textrm{,}\\\ p_{1}q_{2}+q_{1}p_{2},\text{ if
}y\neq\mathrm{H}(v)\textrm{.}\end{cases}$

Therefore, for any two possible input values $v_{1},v_{2}\in V$ and any output
$(\mathrm{H},x^{\prime\prime})$, we have,

$\frac{\Pr\left[(\mathrm{H},x^{\prime\prime})|v_{1}\right]}{\Pr\left[(\mathrm{H},x^{\prime\prime})|v_{2}\right]}\leq\frac{p_{1}p_{2}+q_{1}q_{2}}{p_{1}q_{2}+q_{1}p_{2}}=\frac{e^{\epsilon_{\infty}}\cdot
e^{\epsilon_{\text{IRR}}}+1\cdot 1}{e^{\epsilon_{\infty}}\cdot 1+1\cdot
e^{\epsilon_{\text{IRR}}}}.$

Moreover, since
$e^{\epsilon_{\text{IRR}}}=\frac{e^{{\epsilon_{\infty}}+{\epsilon_{1}}}-1}{e^{\epsilon_{\infty}}-e^{\epsilon_{1}}}$,
then
$e^{\epsilon_{\text{IRR}}}e^{\epsilon_{\infty}}+1=e^{\epsilon_{1}}(e^{\epsilon_{\text{IRR}}}+e^{\epsilon_{\infty}})$.
Hence,

$\frac{\Pr\left[(\mathrm{H},x^{\prime\prime})|v_{1}\right]}{\Pr\left[(\mathrm{H},x^{\prime\prime})|v_{2}\right]}\leq
e^{\epsilon_{1}}.$

∎

###### Theorem 3.5.

(Privacy protection as $\tau\to\infty$)
The client-side of LOLOHA is $g{\epsilon_{\infty}}$-LDP on the users’ values.

###### Proof.

The non-vectorized memoization mechanism (hash and PRR steps) of LOLOHA is a
function ${\mathcal{M}}:V\to{[1..g]}$ that can memorize at most $g$ reports.
For each separate individual report, we known that ${\mathcal{M}}$ satisfies
${\epsilon_{\infty}}$-LDP (Theorem 3.3). Therefore, by sequential composition
of at most $g$ results (Proposition 2.3), ${\mathcal{M}}$ satisfies
$g{\epsilon_{\infty}}$-LDP, and LOLOHA satisfies $g{\epsilon_{\infty}}$-LDP on
the users’ values. ∎

The privacy guarantees of the IRR step (Theorem 3.4) degrade according to the
number of reports $t\in{[1..\tau]}$ (Erlingsson et al., 2014; Erlingsson et
al., 2020). If we let $\epsilon_{t}$ be the privacy guarantee on the users’
values of Algorithm 1 for a fixed user using the data in times ${[1..t]}$, so
that $t=1$ matches exactly ${\epsilon_{1}}$ (Theorem 3.4), then we have
${\epsilon_{1}}\leq\epsilon_{2}\leq\cdots\leq\epsilon_{\tau}\leq
g{\epsilon_{\infty}}.$

Besides, from Algorithm 1, one can remark that instead of leaking a new
${\epsilon_{\infty}}$ for each $v\in V$, LOLOHA will only leak
${\epsilon_{\infty}}$ for each hashed value $x\in{[1..g]}$. Therefore, unlike
RAPPOR that has a worst-case guarantee of $k{\epsilon_{\infty}}$-LDP on the
users’ values, the overall privacy guarantee of our LOLOHA solution will grow
proportionally to the new domain size $2\leq g\ll k$, with worst-case
longitudinal privacy of $g{\epsilon_{\infty}}$-LDP on the users’ values.

###  3.3. Server-Side of LOLOHA

The server-side algorithm of LOLOHA is described in Algorithm 2, which takes
the reported values by $n$ users and aggregates them to estimate the
frequencies of each $v\in V$ at each point in time.

Algorithm 2 Server-Side of LOLOHA.

1:Input: Constants $0<{\epsilon_{1}}<{\epsilon_{\infty}}$, and for each user
$u\in U$, a hash function $H_{u}:V\to{[1..g]}$ and a sequence of hash values
$[x^{\prime\prime(u)}_{1},\ldots,x^{\prime\prime(u)}_{\tau}]$.

2:Output: Matrix with estimations $\hat{f}_{\text{LOLOHA}}(v)_{t}$ for each
$v\in V$ at each $t\in{[1..\tau]}$.

3:Compute parameters:

4:
${\epsilon_{\text{IRR}}}\leftarrow\ln\left(\frac{e^{{\epsilon_{\infty}}+{\epsilon_{1}}}-1}{e^{\epsilon_{\infty}}-e^{\epsilon_{1}}}\right)\quad;\quad
n\leftarrow|U|$

5:
$p_{1}\leftarrow\frac{e^{{\epsilon_{\infty}}}}{e^{{\epsilon_{\infty}}}+g-1}\quad;\quad
q_{1}^{\prime}\leftarrow\frac{1}{g}$

6:
$p_{2}\leftarrow\frac{e^{{\epsilon_{\text{IRR}}}}}{e^{{\epsilon_{\text{IRR}}}}+g-1}\quad;\quad
q_{2}\leftarrow\frac{1}{e^{{\epsilon_{\text{IRR}}}}+g-1}$

7:for each time $t\in{[1..\tau]}$ do:

8: for each $v\in V$ do:

9: $C(v)\leftarrow|\\{u\in U\mid\mathrm{H}_{u}(v)=x^{\prime\prime(u)}_{t}\\}|$

10:
$\hat{f}_{L}(v)_{t}\leftarrow\frac{C(v)-nq_{1}^{\prime}(p_{2}-q_{2})-nq_{2}}{n(p_{1}-q_{1}^{\prime})(p_{2}-q_{2})}$
$\triangleright$ Eq. (3) with $q_{1}^{\prime}$.

11: end for

12:end for

13:return matrix $[\hat{f}_{L}(v)_{t}]_{t,v}$

For large $n$, the estimations of Algorithm 2 are guaranteed to be close to
the true population parameters with high probability as explained in
Proposition 3.6. Moreover, one can also compute the LOLOHA approximate
variance $\mathbb{V}^{*}[\hat{f}_{\textrm{LOLOHA}}(v)]$ by replacing the
server parameters in Algorithm 2 into Eq. (5).

###### Proposition 3.6.

(Asymptotic utility guarantee of LOLOHA)
Fix any arbitrary $t\in{[1..\tau]}$. For each ${v\in V}$, let ${f({v})}$ be
the true population probability of producing the value $v$ at time $t$, and
let ${\hat{f}({v})}\in[0,1]$ be the estimation produced by Algorithm 2 for
time $t$. For any $\beta\in(0,1)$, it holds with probability at least
$1-\beta$ that:

$\max_{{v\in
V}}{|{\hat{f}({v})}-{f({v})}|}<\sqrt{\frac{k}{4n\beta(p_{1}-q_{1}^{\prime})(p_{2}-q_{2})}}\textrm{.}$

###### Proof.

Fix ${v\in V}$, and let $\Delta$ be the random variable given by
$\Delta:={\hat{f}({v})}-{f({v})}\in[-1,1]$ be a random variable. Since
${\hat{f}({v})}$ is unbiased, we have $\mathbb{E}[\Delta]=0$ and
$\mathbb{V}[\Delta]=\mathbb{V}[{\hat{f}({v})}]$. We remark that for any
$\delta,\beta\in(0,1)$, among all random variables $\Delta^{\prime}$ defined
in $[-1,1]$ such that $\mathbb{E}[\Delta^{\prime}]$ and
$\Pr[|\Delta^{\prime}|\geq\delta]=\beta$, the one with minimal variance is the
random variable $\Delta^{*}$ that concentrates a mass of $1-\beta$ at
$\Delta^{\prime}=0$ and two masses of $\beta/2$ at $-\delta$ and $\delta$.
This random variable has variance $\mathbb{V}[\Delta^{*}]=\beta\delta^{2}$.
Hence, for arbitrary $\delta\in(0,1)$ and letting in particular
$\beta:=\Pr[{|{\hat{f}({v})}-{f({v})}|}\geq\delta]$, we conclude that
$\mathbb{V}[{\hat{f}({v})}]=\mathbb{V}[{|{\hat{f}({v})}-{f({v})}|}]\geq\mathbb{V}[\Delta^{*}]=\Pr[{|{\hat{f}({v})}-{f({v})}|}\geq\delta]\cdot\delta^{2}$.
In other words,

$\Pr[{|{\hat{f}({v})}-{f({v})}|}\geq\delta]\leq\mathbb{V}[{\hat{f}({v})}]/\delta^{2}.$

Now, considering all ${v\in V}$ simultaneously, we obtain $\Pr[\max_{{v\in
V}}{|{\hat{f}({v})}-{f({v})}|}\geq\delta]\leq\sum_{v\in
V}\Pr[{|{\hat{f}({v})}-{f({v})}|}\geq\delta]=(\nicefrac{{1}}{{\delta^{2}}})\sum_{v\in
V}\mathbb{V}[{\hat{f}({v})}]$. By rewriting this equation in terms of
confidence, we conclude that with probability at least $1-\beta$,

$\max_{{v\in V}}{|{\hat{f}({v})}-{f({v})}|}<\sqrt{\nicefrac{{\sum_{v\in
V}\mathbb{V}[{\hat{f}({v})}]}}{{\beta}}}.$

Lastly, from Eq. (4) it can be concluded that
$\mathbb{V}[{\hat{f}({v})}]\leq\nicefrac{{1}}{{4n(p_{1}-q_{1}^{\prime})(p_{2}-q_{2})}}$
because the product $\gamma(1-\gamma)$ is maximal at $\gamma=1/2$. As a
consequence, $\max_{{v\in
V}}{|{\hat{f}({v})}-{f({v})}|}<\sqrt{\nicefrac{{k}}{{4n\beta(p_{1}-q_{1}^{\prime})(p_{2}-q_{2})}}}.$
∎

###  3.4. Selecting and Optimizing Parameter $g$

Binary LOLOHA (BiLOLOHA). Following Theorem 3.5, the strongest longitudinal
privacy protection of LOLOHA is when $g=2$.

Optimal LOLOHA (OLOLOHA). To maximize the utility of LOLOHA, we find the
optimal $g$ value by taking the partial derivative of
$\mathbb{V}^{*}[\hat{f}_{\textrm{LOLOHA}}(v)]$ with respect to $g$. Let
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$, for $\alpha\in(0,1)$. This partial
derivative is a function in terms of ${\epsilon_{\infty}}$ and $\alpha$, or
alternatively, in terms of $a=e^{\epsilon_{\infty}}$ and
$b=e^{\alpha\epsilon_{\infty}}$, and it is minimized when $g$ equals (_cf._
development in repository (art, [n.d.])):

(6)
$g=1{+}{\max}\left(1,\left\lfloor\frac{1{-}a^{2}{+}\sqrt{a^{4}{-}14a^{2}{+}12ab(1{-}ab){+}12a^{3}b{+}1}}{6(a{-}b)}\right\rceil\right)\textrm{,}$

in which $\lfloor.\rceil$ means rounding to the closest integer. Fig. 1
illustrates the optimal $g$ selection with Eq. (6) by varying the longitudinal
privacy guarantee ${\epsilon_{\infty}}=[0.5,1,\ldots,4.5,5]$ and
$\alpha\in\\{0.1,0.2,\ldots,0.6\\}$. From Fig. 1, one can remark that in high
privacy regimes (_i.e._ , low $\epsilon$ values), the optimal $g$ is binary
(_i.e._ , our BiLOLOHA protocol with $g=2$). As ${\epsilon_{\infty}}$ or/and
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ get(s) higher (low privacy
regimes), the optimal $g$ is non-binary, which can maximize utility with a
cost in the overall longitudinal privacy $g{\epsilon_{\infty}}$-LDP on the
users’ values, for $g>2$.

Figure 1. Optimal $g$ selection for our OLOLOHA protocol by varying the
longitudinal ${\epsilon_{\infty}}$ and first report
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ privacy guarantees, for
$\alpha\in\\{0.1,0.2,\ldots,0.6\\}$.

##  4\. Theoretical Comparison

In this section, we compare LOLOHA with the state-of-the-art protocols
described in the previous Section 2.4 from a theoretical point of view. Table
1 shows a summary of the main characteristics of these protocols, excluding
utility.

For the theoretical utility, numerical analysis is preferred over an
analytical one because the formulas of variance and approximate variance are
excessively complex. For L-OSUE and $d$BitFlipPM, the approximate variances
are
$\frac{4e^{\epsilon_{1}}}{n\left(e^{2\epsilon_{1}}-2e^{\epsilon_{1}}+1\right)}{}$
and $\frac{b}{2dn\sinh{\left(\frac{\epsilon_{\infty}}{2}\right)}}{}$
respectively, but for the other protocols, the formulas are provided only in
the repository (art, [n.d.]) since they are excessively verbose for this
document.

In order to evaluate numerically the approximate variance $\mathbb{V}^{*}$ of
LOLOHA in comparison with state-of-the-art ones (Erlingsson et al., 2014;
Arcolezi et al., 2022a), for each protocol, we set the longitudinal privacy
guarantee ${\epsilon_{\infty}}$ (upper bound) and the first report privacy
guarantee ${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ (lower bound), for
$\alpha\in(0,1)$. This allows to obtain parameters $p_{1},q_{1},p_{2},q_{2}$
for each protocol, which are then used to compute their approximate variance
with Eq. (5).

Fig. 2 illustrates the numerical values of the approximate variance for our
LOLOHA protocols, RAPPOR (Erlingsson et al., 2014), and L-OSUE (Arcolezi et
al., 2022a) with $n=10000$, ${\epsilon_{\infty}}=[0.5,1,\ldots,4.5,5]$, and
$\alpha\in\\{0.1,0.2,\ldots,0.6\\}$. From Fig. 2, one can remark that all
protocols have similar variance values when $\alpha\leq 0.3$ with only a small
difference when ${\epsilon_{\infty}}$ is high. However, in low privacy
regimes, _i.e._ , when ${\epsilon_{\infty}}$ and $\alpha$ are high, BiLOLOHA
is the least performing protocol in terms of utility, accompanied by RAPPOR.
Indeed, our OLOLOHA protocol has a very similar utility as the optimized
L-OSUE (Arcolezi et al., 2022a) protocol, which indicates a clear connection
also found between their one-round versions (Wang et al., 2017), _i.e._ , OLH
and OUE.

Figure 2. Numerical values of the approximate variance $\mathbb{V}^{*}[\hat{f}_{L}(v)]$ in Eq. (5) of our LOLOHA protocols, RAPPOR (Erlingsson et al., 2014), and L-OSUE (Arcolezi et al., 2022a) varying the longitudinal ${\epsilon_{\infty}}$ and first report ${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ privacy guarantees, for $\alpha\in\\{0.1,0.2,\ldots,0.6\\}$. Protocol | Comm. | Server | Privacy loss
---|---|---|---
| bits per user | run-time | budget
| per time step | complexity | consumption
LOLOHA | $\lceil\log_{2}g\rceil$ | $n\,k$ | $g\,{\epsilon_{\infty}}$
L-GRR (Arcolezi et al., 2022a) | $\lceil\log_{2}k\rceil$ | $n$ | $k\,{\epsilon_{\infty}}$
RAPPOR (Erlingsson et al., 2014) | $k$ | $n\,k$ | $k\,{\epsilon_{\infty}}$
L-OSUE (Arcolezi et al., 2022a) | $k$ | $n\,k$ | $k\,{\epsilon_{\infty}}$
$d$BitFlipPM (Ding et al., 2017) | $d$ | $n\,b$ | $\min(d+1,b)\,{\epsilon_{\infty}}$
Table 1. Theoretical comparison of the protocols.

Though not included in our analysis, the L-GRR protocol from (Arcolezi et al.,
2022a) has shown to be very sensitive to $k$ (a parameter on which its
variance depends on), leading to extremely high values that would obfuscate
the curves of the other protocols in Fig. 2. However, L-GRR is ideal when $k$
is small, which is the case for instance for binary attributes. Besides, we
also did not numerically compare our protocols with $d$BitFlipPM as it only
has a single round of sanitization. A proper comparison with $d$BitFlipPM
would be only considering the PRR step of our LOLOHA protocols. Therefore, by
comparing the approximate variances of double randomization protocols, we can
conclude that our LOLOHA protocols preserve as much utility as state-of-the-
art protocols (Erlingsson et al., 2014; Arcolezi et al., 2022a).

Moreover, from Table 1, LOLOHA has less communication cost than L-UE and
similar server time computation, which is advantageous for large-scale system
deployment to monitor frequency longitudinally. In addition, one clear
limitation of RAPPOR, L-OSUE, and L-GRR is that they do not support even small
data changes of the user’s actual data (Ding et al., 2017), which requires to
invoke the whole algorithm again on the new value. Therefore, following
Definition 3.2 and Proposition 2.3, the overall privacy guarantee of RAPPOR,
L-OSUE, and L-GRR, for all user’s true value $v\in V$ (assuming the user’s
value will change periodically) will grow proportionally to the number of data
changes, with worst-case longitudinal privacy of $k{\epsilon_{\infty}}$-LDP on
the users’ values.

On the other hand, with $d$BitFlipPM, the overall privacy guarantee of
$d$BitFlipPM for all user’s true value $v\in V$ (assuming the user’s value
will change periodically) will grow proportionally to the number of bits $d$
or the number of bucket changes, with worst-case longitudinal privacy of
$\min(d+1,b){\epsilon_{\infty}}$-LDP on the users’ values (_cf._ Definition
3.2 and Proposition 2.3). However, there is a loss of information due to both
the generalization of the original domain size $k$ to $b$ buckets and due to
sampling only $d$ bits. Besides, the $d$BitFlipPM protocol is vulnerable to
detecting high data changes (_i.e._ , change of real bucket) as there is no
second round of sanitization (_i.e._ , IRR step) (Xue et al., 2022). This data
change detection problem is (to some extent) minimized when $d$ is small.

##  5\. Experimental Evaluation

In this section, we present the setup of our experiments and the experimental
results of our LOLOHA protocols in comparison with the state-of-the-art.

###  5.1. Setup of Experiments

The main goal of our experiments is to study the effectiveness of our proposed
LOLOHA protocols on longitudinal frequency estimates through multiple $\tau>1$
data collections. In particular, we aim to show that our LOLOHA protocols (i)
maintain competitive utility to state-of-the-art memoization-based LDP
protocols (Erlingsson et al., 2014; Ding et al., 2017; Arcolezi et al., 2022a)
while (ii) minimize longitudinal privacy loss. With these objectives in mind,
we run experiments using both synthetic and real-world datasets.

Environment. All algorithms are implemented in Python 3 with Numpy and Numba
libraries. The codes we develop for all experiments are available in the
repository (art, [n.d.]). Since LDP algorithms are randomized, we report
average results over 20 runs.

Datasets. We use the following real and synthetic datasets.

  * •

Syn. To simulate the deployment of (Ding et al., 2017) to collect data every 6
hours, we generate a synthetic dataset with $k=360$ (_i.e._., the number of
minutes in 6 hours), $n=10000$ users, and $\tau=120$ data collections (_i.e._
, 4x over 30 days). For each user, the value at the first timestamp follows a
Uniform distribution. For each subsequent time, a change can occur with
probability $p_{ch}=0.25$, with value following a Uniform distribution too.

  * •

Adult. This is a classical dataset from the UCI machine learning repository
(Dua and Graff, 2017) with $n=45222$ samples after cleaning. We only selected
the “hours-per-week" attribute with $k=96$. To simulate multiple data
collections, we randomly permuted the data $\tau=260$ times (_i.e._ , 52 weeks
over 5-years). Note that the real frequency remains the same but each user has
a random private sequence.

  * •

DB_MT. This dataset is produced by the folktables Python package (Ding et al.,
2021) that provides access to datasets derived from the US Census. We selected
the survey year 2018 and the “Montana” state, which results in $n=10336$
samples. To simulate $\tau=80$ counter data collections, we selected all
person record-replicate weights attributes111https://www.census.gov/programs-
surveys/acs/microdata/documentation.html., _i.e._ , PWGTP1, …, PWGTP80. The
total number of unique values among all columns is $k=1412$.

  * •

DB_DE. Similar to DB_MT, we selected the “Delaware” state, which results in
$n=9123$, $\tau=80$, and $k=1234$.

Methods evaluated. We consider for evaluation the following longitudinal LDP
protocols:

  * •

RAPPOR. The utility-oriented protocol from (Erlingsson et al., 2014) based on
SUE (_cf._ Section 2.4.1).

  * •

L-OSUE. The optimized L-UE protocol from (Arcolezi et al., 2022a) (_cf._
Section 2.4.2).

  * •

L-GRR. The optimized longitudinal protocol from (Arcolezi et al., 2022a) when
$k$ is small (_cf._ Section 2.4.3).

  * •

$d$BitFlipPM. The one-round randomization mechanism from (Ding et al., 2017)
with $d\in\\{1,b\\}$, referred respectively as $1$BitFlipPM and $b$BitFlipPM,
in which the former $1$BitFlipPM is tuned for privacy and the latter
$b$BitFlipPM for utility (_cf._ Section 2.4.4)

  * •

LOLOHA. Our protocols following Algorithm 1, which are BiLOLOHA with $g=2$
adjusted for privacy and OLOLOHA with $g$ following Eq. (6) tuned for utility.

Privacy metrics. We vary the longitudinal privacy parameter in the range
${\epsilon_{\infty}}=[0.5,1,\ldots,4.5,5]$ and
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$, for $\alpha\in\\{0.4,0.5,0.6\\}$,
to compare our experimental results with numerical ones from Section 4 (with
higher visibility).

Performance metrics. To evaluate our results, we use the MSE averaged by the
number of data collection $\tau$, denoted by $MSE_{avg}$. Thus, for each time
$t\in{[1..\tau]}$, we compute for each value $v\in V$ the estimated frequency
$\hat{f}_{L}(v)_{t}$ and the real one $f(v)_{t}$ and calculate their
differences before averaging by $\tau$. More formally,

(7) $MSE_{avg}=\frac{1}{\tau}\sum_{t\in{[1..\tau]}}\frac{1}{|V|}\sum_{v\in
V}\left(f(v)_{t}-\hat{f}_{L}(v)_{t}\right)^{2}\textrm{.}$

We also assess the averaged longitudinal privacy loss for all users, denoted
by $\check{\epsilon}_{avg}$. More precisely, after the end of all data
collections $\tau$, we compute for each user $u\in U$ their overall
longitudinal privacy loss $\check{\epsilon}_{\infty}^{(u)}$ and average by
$n$. For example, RAPPOR (and L-GRR and L-OSUE) leaks a new
${\epsilon_{\infty}}$ in each data change with $\check{\epsilon}_{\infty}\leq
k{\epsilon_{\infty}}$, while LOLOHA protocols leak a new ${\epsilon_{\infty}}$
in each hash value change with $\check{\epsilon}_{\infty}\leq
g{\epsilon_{\infty}}$. More formally,

(8) $\check{\epsilon}_{avg}=\frac{1}{n}\sum_{u\in
U}\check{\epsilon}_{\infty}^{(u)}\textrm{.}$

Finally, for the $d$BitFlipPM protocol, we also evaluate the percentage of
users in which an attacker can identify all (bucket) data change points
(_i.e._ , worst-case analysis) due to different PRR reports throughout the
$\tau$ data collections.

###  5.2. Results

First, we compare the utility performance of our LOLOHA protocols with all
four state-of-the-art memoization-based protocols for frequency monitoring
under LDP guarantees, namely, RAPPOR (Erlingsson et al., 2014), L-OSUE
(Arcolezi et al., 2022a), L-GRR (Arcolezi et al., 2022a), and $d$BitFlipPM
(Ding et al., 2017), for $d\in\\{1,b\\}$. Fig. 3 illustrates the $MSE_{avg}$
metric in Eq. (7) for all methods and all Syn, Adult, DB_MT, and DB_DE
datasets, by varying the longitudinal ${\epsilon_{\infty}}$ and first report
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ privacy guarantees, for
$\alpha\in\\{0.4,0.5,0.6\\}$. On the one hand, since $k\leq 360$ for Syn and
Adult datasets, when implementing $d$BitFlipPM, we select $b=k$ to estimate
the same $k$-bins histogram as all other methods in Figs. 3(a) and 3(b). On
the other hand, we select $b=\lfloor k/4\rfloor$ bins for both DB_MT
($k=1412$) and DB_DE ($k=1234$) datasets, but we did not include the error
metric of $d$BitFlipPM in Figs. 3(c) and 3(d) as the error is five orders of
magnitude higher due to histograms of different sizes ($b<k$).

Fig. 3 shows that the experimental results with all datasets match the
numerical results of variance values from Fig. 2 for our LOLOHA protocols,
RAPPOR, and L-OSUE. More specifically, our OLOLOHA protocol has similar
utility to the optimized L-OSUE protocol, a relationship also find between
their one-round versions OLH and OUE in (Wang et al., 2017). In high privacy
regimes, all four protocols, _i.e._ , RAPPOR, L-OSUE, BiLOLOHA, and OLOLOHA
have very similar utility. In low privacy regimes, L-OSUE and OLOLOHA
outperforms both RAPPOR and BiLOLOHA. The least performing longitudinal LDP
protocols are L-GRR and $1$BitFlipPM, the former due to high domain sizes $k$,
as shown in (Arcolezi et al., 2022a), and the latter due to sampling only a
single $d=1$ bit out of $b$ ones. The $b$BitFlipPM protocol outperforms all
experimented longitudinal LDP protocols due to having only a single round of
sanitization (_i.e._ , the PRR step) and by reporting all $d=b$ bits, which is
consistent with (Ding et al., 2017) (the larger $d$ the greater the utility).

However, increasing the number of bits $d$ the users must report negatively
impacts privacy, as each new input value has a high probability of generating
a new output value, which will be detected by the server. For instance, for
both $d$BitFlipPM protocols, for $d\in\\{1,b\\}$, Table 2 exhibits the
percentage of users in which all bucket changes were detected by the server
due to different PRR responses throughout $\tau$ data collections, for all
Syn, Adult, DB_MT, and DB_DE datasets. Remark that when $d=1$, the protocol is
adjusted for privacy, thus being less vulnerable with respect to privacy with
only a small percentage ($<1\%$) of users that the server always detected a
different randomized output due to different input values. Besides, one can
note that the percentage of attacked users decreases as ${\epsilon_{\infty}}$
gets higher when $d=1$. The intuition is that the probability of randomizing
the single bit will be smaller with high ${\epsilon_{\infty}}$, thus
generating the same report many times. On the other hand, the $b$BitFlipPM
protocol is tuned for utility, which increased the probability of always
generating a new randomized output due to new input values and, thus leading
to 100% of detection for all four datasets. Though we only perform both
extreme cases (lower $d=1$ and upper $d=b$ bounds), one can picture the
privacy-utility trade-off of $d$BitFlipPM for other $d$ values in between our
results of Fig. 3 and Table 2.

Table 2. Percentage of users in which the server detected all data change points for $d$BitFlipPM, for $d\in\\{1,b\\}$, and all Syn, Adult, DB_MT, and DB_DE datasets. ${\epsilon_{\infty}}$ | $d=1$ | $d=b$
---|---|---
Syn | Adult | DB_MT | DB_DE | Syn | Adult | DB_MT | DB_DE
0.5 | 0% | 0% | 0.0048% | 0% | 100% | 100% | 100% | 100%
1.0 | 0% | 0% | 0.0044% | 0% | 100% | 100% | 100% | 100%
1.5 | 0% | 0% | 0.0048% | 0% | 100% | 100% | 100% | 100%
2.0 | 0% | 0% | 0.0039% | 0% | 100% | 100% | 100% | 100%
2.5 | 0% | 0% | 0.0024% | 0% | 100% | 100% | 100% | 100%
3.0 | 0% | 0% | 0.0024% | 0% | 100% | 100% | 100% | 100%
3.5 | 0% | 0% | 0.0024% | 0% | 100% | 100% | 100% | 100%
4.0 | 0% | 0% | 0.0019% | 0% | 100% | 100% | 100% | 100%
4.5 | 0% | 0% | 0.0010% | 0% | 100% | 100% | 100% | 100%
5.0 | 0% | 0% | 0.0010% | 0% | 100% | 99.99% | 100% | 100%

((a)) Syn dataset: $k=360$, $n=10000$, and $\tau=120$.

((b)) Adult dataset: $k=96$, $n=45222$, and $\tau=260$.

((c)) DB_MT dataset: $k=1412$, $n=10336$, and $\tau=80$.

((d)) DB_DE dataset: $k=1234$, $n=9123$, and $\tau=80$.

Figure 3. Averaged MSE for $\tau$ data collections in Eq. (7) by varying the
longitudinal ${\epsilon_{\infty}}$ and first report
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ privacy guarantees, for
$\alpha\in\\{0.4,0.5,0.6\\}$, on (a) Syn, (b) Adult, (c) DB_MT, and (d) DB_DE
datasets. The evaluated methods are: $d$BitFlipPM (Ding et al., 2017), L-OSUE
(Arcolezi et al., 2022a), RAPPOR (Erlingsson et al., 2014), L-GRR (Arcolezi et
al., 2022a), and our LOLOHA protocols.

We now analyze the longitudinal privacy guarantees of our LOLOHA protocols in
comparison with the state-of-the-art memoization-based LDP protocols. Fig. 4
illustrates the $\check{\epsilon}_{avg}$ metric in Eq. (8) for all methods and
all Syn, Adult, DB_MT, and DB_DE datasets, by varying the longitudinal
${\epsilon_{\infty}}$ and first report
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ privacy guarantees, for
$\alpha\in\\{0.4,0.5,0.6\\}$. Notice that the results of $d$BitFlipPM
protocols in Figs. 4(a) and 4(b) are with $b=k$ buckets and in Figs. 4(c) and
4(d) are with $b=\lfloor k/4\rfloor$ buckets.

((a)) Syn dataset: $k=360$, $n=10000$, and $\tau=120$.

((b)) Adult dataset: $k=96$, $n=45222$, and $\tau=260$.

((c)) DB_MT dataset: $k=1412$, $n=10336$, and $\tau=80$.

((d)) DB_DE dataset: $k=1234$, $n=9123$, and $\tau=80$.

Figure 4. Averaged longitudinal privacy loss for $\tau$ data collections in
Eq. (8) by varying the longitudinal ${\epsilon_{\infty}}$ and first report
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$ privacy guarantees, for
$\alpha\in\\{0.4,0.5,0.6\\}$, on (a) Syn, (b) Adult, (c) DB_MT, and (d) DB_DE
datasets. The evaluated methods are: $d$BitFlipPM (Ding et al., 2017), L-OSUE
(Arcolezi et al., 2022a), RAPPOR (Erlingsson et al., 2014), L-GRR (Arcolezi et
al., 2022a), and our LOLOHA protocols.

From Fig. 4, one can remark that all four LDP protocols, RAPPOR, L-OSUE,
L-GRR, and $b$BitFlipPM (when $b=k$ in Figs. 4(a) and 4(b)), have an averaged
longitudinal privacy loss linear to the number of data changes the users
performed throughout the $\tau$ data collections. Fig. 4(a) presents the
smallest $\check{\epsilon}_{avg}$ as both $k=360$ and the change rate
$p_{ch}=0.25$ are small. However, in a worst-case scenario in which the users
change their values significantly or $\tau\rightarrow\infty$, the overall
privacy loss of RAPPOR, L-OSUE, L-GRR, and $b$BitFlipPM can grow to values as
large as $k{\epsilon_{\infty}}$ for all datasets. Note that in Figs. 4(a) and
4(b), naturally, setting $b=k$ does not benefit from the $d$BitFlipPM
advantage for enhancing longitudinal privacy protection by mapping several
close values to the same bin, which leads to higher $\check{\epsilon}_{avg}$.
In contrast, in Figs. 4(c) and 4(d), the longitudinal privacy loss of
$b$BitFlipPM protocols is lower than RAPPOR, L-OSUE, and L-GRR because
$b=\lfloor k/4\rfloor$ buckets, but still significantly higher than our LOLOHA
protocols.

Indeed, the privacy loss of our LOLOHA protocols depends only on the new
domain size $g\geq 2$, which is agnostic to $k$. For this reason, our BiLOLOHA
protocol with $g=2$ leaked about 15 to 25 orders of magnitude less than the
state-of-the-art LDP protocols considering the experimented $\tau$ values.
These are similar results achieved by the $1$BitFlipPM protocol, which agrees
with the theoretical analysis in Table 1, although BiLOLOHA consistently and
considerably outperforms $1$BitFlipPM in terms of utility loss (see Fig. 3).
Besides, since our OLOLOHA protocol has privacy loss depending on the optimal
$g$ value in Eq. (6), which can be $g>2$ in low privacy regimes, it only
resulted in about 2 to 5 order of magnitude less privacy loss than the state-
of-the-art LDP protocols, for the experimented $\tau$ value. More
specifically, when ${\epsilon_{\infty}}$ is high and $\alpha=0.6$ (see Fig.
4(d)), OLOLOHA leaked about 2 orders of magnitude less privacy loss than the
$b$BitFlipPM protocol. However, as the number of data collections
$\tau\rightarrow\infty$, $b$BitFlipPM privacy loss will go to
$b{\epsilon_{\infty}}$, which is $b/g$ times higher than the one from OLOLOHA
with $g{\epsilon_{\infty}}$. Besides, in practice, lower values of
${\epsilon_{\infty}}$ and $\alpha\ll 1$ should be used to ensure strong
longitudinal privacy guarantees since the first
${\epsilon_{1}}=\alpha{\epsilon_{\infty}}$-LDP report. As shown in Fig. 1,
this will mean lower values of $g$, which will substantially decrease the
longitudinal privacy loss of OLOLOHA.

###  5.3. Discussion

In brief, we have evaluated in our experiments the performance of our LOLOHA
protocols in comparison with four state-of-the-art memoization-based LDP
protocols (Erlingsson et al., 2014; Ding et al., 2017; Arcolezi et al., 2022a)
for frequency monitoring on different datasets and varying different
parameters. We now summarize the main findings that help justify the many
claims of our paper.

More precisely, the conclusions we stated in Section 4 are based on the
analytical variances of the LDP protocols. To corroborate these conclusions,
our empirical experiments in Section 5.2, which measured the MSE metric, do
indeed correspond to the numerical results of the variances.

Furthermore, the main disadvantage of RAPPOR (Erlingsson et al., 2014) and the
two others optimized protocols from (Arcolezi et al., 2022a), (_i.e._ , L-GRR
and L-OSUE), is the linear relation on $k$ for the overall longitudinal
privacy loss, _i.e._ , $k{\epsilon_{\infty}}$, as each data change needs to be
memoized. Thus, for the monitoring of large-scale systems (_e.g._ ,
application usage, calories ingestion, preferred webpage, etc), the overall
privacy loss of such protocols will be tremendous, being unrealistic for
private frequency monitoring.

Even though the $d$BitFlipPM (Ding et al., 2017) generalizes the original
domain size $k$ to $b$ buckets, there is still a linear relation on the new
domain size $b\leq k$ for the overall longitudinal privacy loss, _i.e._ ,
$b{\epsilon_{\infty}}$, as each bucket change needs to be memoized when the
mechanism is tuned for utility. What is more, this generalization naturally
leads to loss of information and one has to carefully choose the bucket
numbers/width for the best privacy-utility trade-off. Besides, the privacy-
utility trade-off of $d$BitFlipPM also depends on the number of bits $d\leq b$
each user samples. However, even when $d=1$, which offers the strongest
protection (Ding et al., 2017), in our experiments, the server was still able
to detect all bucket change of a small portion of users (see Table 2). Hence,
as one adjusts $d$ for utility, _i.e._ , $1<d\leq b$, the higher the
attacker’s success rate to detect all user’s data changes will be.

The best choice for adequately balancing privacy and utility for frequency
monitoring is with our LOLOHA protocols, as the privacy loss is only linear to
the new (reduced) domain size $2\leq g\ll k$. Though we only experiment with
$80\leq\tau\leq 260$ data collections in Section 5.2, in the worst case, this
represents a significant $k/g$ decrease factor of privacy loss by our LOLOHA
protocols. Intuitively, LOLOHA can be tuned to satisfy the strongest
longitudinal privacy protection by selecting $g=2$ (_i.e._ , our BiLOLOHA
protocol). In this setting, there is loss of utility in the encoding step
through local hashing since the output is just one bit. For instance, even if
this bit is transmitted correctly after the two rounds of sanitization, the
server can only obtain one bit of information about the input (_i.e._ , to
which half of the input domain the value belongs to (Wang et al., 2017)).
Nevertheless, from the analytic variance analysis in Fig. 2 and empirical
experiments in Fig. 3, LOLOHA is optimal with $g=2$ in high privacy regimes,
_i.e._ , low ${\epsilon_{\infty}}$ values, which is desirable for practical
deployments.

As a limitation, users fix their randomly selected hash function
$\mathrm{H}\in\mathscr{H}$ with our LOLOHA protocols (_cf._ Algorithm 1),
which can be regarded as a unique identifier in longitudinal data collection.
However, this is a common assumption of the LDP model, which assumes the
server already knows the users’ identifiers (Bittau et al., 2017; Wang et al.,
2019; Erlingsson et al., 2019, 2020), but not their private data. One way to
counter this link between the user’s randomized report and their identifier is
to assume a trusted intermediate, such as a shuffler, that does not collude
with the server, _e.g._ , the Shuffle DP model (Bittau et al., 2017;
Erlingsson et al., 2019, 2020), which we let the investigation for future
work.

##  6\. Related Work

Differential privacy (Dwork et al., 2006; Dwork, 2006; Dwork et al., 2014) has
been increasingly accepted as the current standard for data privacy. The
central DP model assumes a trusted curator, which collects the clients’ raw
data and releases sanitized aggregated data. The LDP model (Kasiviswanathan et
al., 2008; Duchi et al., 2013a, b) does not rely on collecting raw data
anymore, which has a clear connection with the concept of randomized response
(Warner, 1965). In recent years, there have been several studies on the local
DP setting, _e.g._ , for frequency estimation of a single (Wang et al., 2017;
Acharya et al., 2019; Feldman et al., 2022; Kairouz et al., 2016a, b; Naor and
Vexler, 2020; Cormode et al., 2021) and multiple (Arcolezi et al., 2021a;
Varma et al., 2022; Liu et al., 2023) attributes; mean estimation (Nguyên et
al., 2016; Wang et al., 2019), heavy hitter estimation (Bassily and Smith,
2015; Bassily et al., 2017), and machine learning (Mahawaga Arachchige et al.,
2020; Zhou and Tan, 2021).

As for locally differentially private monitoring, Erlingsson, Pihur, and
Korolova (Erlingsson et al., 2014) proposed the RAPPOR algorithm for frequency
monitoring that is based on the memoization solution described in Section 2.4.
The recent study of Arcolezi et al. (Arcolezi et al., 2022a) generalizes this
framework for optimally chaining two LDP protocols, proposing the L-GRR
protocol that is optimized for small domain size $k$ and the L-OSUE protocol
for higher $k$ (see Figs. 2 and 3). Moreover, Erlingsson et al. (Erlingsson et
al., 2020) formalize the privacy guarantees of using two rounds of
sanitization under both local and shuffle DP guarantees. Naor and Vexler (Naor
and Vexler, 2020) also formalized the privacy guarantees of chaining two LDP
protocol as well as introduced a new Everlasting privacy definition.

An alternative approach for memoization named $d$BitFlipPM has been proposed
by Ding, Kulkarni, and Yekhanin (Ding et al., 2017), discussed in Section
2.4.4. The $d$BitFlipPM protocol allows frequent but only small changes in the
original data since a high change (_i.e._ , a different bucket) can be
detected by an attacker (_cf._ Table 2). Although an attacker that is able to
identify a data change can still not infer the user’s actual data (controlled
by ${\epsilon_{\infty}}$), the overall LDP guarantees can be highly reduced if
these changes are correlated (Erlingsson et al., 2014; Ding et al., 2017;
Erlingsson et al., 2019). For instance, the authors in (Tang et al., 2017)
performed a detailed analysis of Apple’s LDP implementation and examined its
longitudinal privacy implications. Naor and Vexler (Naor and Vexler, 2020)
also investigated the trackability of RAPPOR following their new Everlasting
privacy definition.

LOLOHA leverages the best of RAPPOR and $d$BitFlipPM, which can inherently
minimize these inference attacks. More precisely, on the one hand, LOLOHA uses
LH (Wang et al., 2017) for domain reduction, which allows many values to
collide (universal hashing property) and thus creates uncertainty about the
user’s actual value. Indeed, LH protocols are the least attackable LDP
protocols in the recent studies of Arcolezi et al. (Arcolezi et al., 2022c)
and Emre Gursoy et al. (Gursoy et al., 2022) considering a Bayesian adversary.
Besides that, LOLOHA also has two rounds of sanitization following RAPPOR’s
framework, which can improve privacy to minimize data change detection.
Finally, another line of work for frequency monitoring under LDP is data
change-based (Joseph et al., 2018; Erlingsson et al., 2019; Xue et al., 2022;
Ohrimenko et al., 2022), motivated by the fact that, generally, users’ data
changes infrequently. A similar idea was proposed much earlier in the work of
Chatzikokolakis, Palamidessi, and Stronati (Chatzikokolakis et al., 2014),
which proposed a predictive mechanism for location-based systems to utilize
privacy budget only for new “hard” location points (_i.e._ , with bad
predictions). However, these approaches normally impose restrictions on the
number of data collections $\tau$ and on the number of data changes as their
accuracy degrades linearly or sub-linearly with the number of changes in the
underlying data distributions, which can limit their applicability and
scalability to real-world systems.

##  7\. Conclusion and Perspectives

In this paper, we study the fundamental problem of monitoring the frequency of
evolving data throughout time under LDP guarantees. We proposed a new locally
differentially private protocol named LOLOHA, which is built on top of domain
reduction to minimize longitudinal privacy loss up to a $k/g$ factor and
double randomization to enhance privacy. Through theoretical analysis, we have
proven the longitudinal privacy (Theorems 3.3, 3.4, and 3.5) and accuracy
guarantees (Proposition 3.6) of our LOLOHA protocols. In addition, through
extensive experiments with synthetic and real-world datasets, we have shown
that our proposed LOLOHA protocols preserve competitive utility as state-of-
the-art LDP protocols (Erlingsson et al., 2014; Ding et al., 2017; Arcolezi et
al., 2022a) by considerably minimizing longitudinal privacy loss (from 2 to 25
orders of magnitude with the experimented $\tau$ values). As future work, we
intend to identify reasonable conditions of the input data (not constant as in
(Erlingsson et al., 2014; Arcolezi et al., 2022a)) in which one can satisfy
the standard $\epsilon$-LDP definition. Besides, we intend to identify attack-
based approaches to longitudinal LDP frequency estimation protocols (_e.g._ ,
data change detection or correlated data) and to extend the analysis of our
LOLOHA protocols to the shuffle DP model. Last, we also aim to integrate
LOLOHA to the multi-freq-ldpy package (Arcolezi et al., 2022b).

###### Acknowledgements.

The authors deeply thank the anonymous meta-reviewer and reviewers for their
insightful suggestions. The work of Héber H. Arcolezi, Carlos Pinzón, and
Catuscia Palamidessi was supported by the European Research Council (ERC)
project HYPATIA under the European Union’s Horizon 2020 research and
innovation programme. Grant agreement n. 835294. Sébastien Gambs is supported
by the Canada Research Chair program as well as a Discovery Grant from NSERC.

## References

  * (1)
  * art ([n.d.]) [n.d.].  LOLOHA repository.  https://github.com/hharcolezi/LOLOHA.
  * Acharya et al. (2019) Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019.  Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. In _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research)_ , Kamalika Chaudhuri and Masashi Sugiyama (Eds.), Vol. 89. PMLR, 1120–1129.
  * Arcolezi et al. (2021a) Héber H. Arcolezi, Jean-François Couchot, Bechara Al Bouna, and Xiaokui Xiao. 2021a.  Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_ _(CIKM ’21)_. Association for Computing Machinery, New York, NY, USA, 47–57.  https://doi.org/10.1145/3459637.3482467
  * Arcolezi et al. (2021b) Héber H. Arcolezi, Jean-François Couchot, Bechara Al Bouna, and Xiaokui Xiao. 2021b.  Longitudinal Collection and Analysis of Mobile Phone Data with Local Differential Privacy. In _Privacy and Identity Management_ , Michael Friedewald, Stefan Schiffner, and Stephan Krenn (Eds.). Springer International Publishing, Cham, 40–57.  https://doi.org/10.1007/978-3-030-72465-8_3
  * Arcolezi et al. (2022a) Héber H. Arcolezi, Jean-François Couchot, Bechara Al Bouna, and Xiaokui Xiao. 2022a.  Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates.  _Digital Communications and Networks_ (2022).  https://doi.org/10.1016/j.dcan.2022.07.003
  * Arcolezi et al. (2022b) Héber H. Arcolezi, Jean-François Couchot, Sébastien Gambs, Catuscia Palamidessi, and Majid Zolfaghari. 2022b.  Multi-Freq-LDPy: Multiple Frequency Estimation Under Local Differential Privacy in Python. In _Computer Security – ESORICS 2022_ , Vijayalakshmi Atluri, Roberto Di Pietro, Christian D. Jensen, and Weizhi Meng (Eds.). Springer Nature Switzerland, Cham, 770–775.  https://doi.org/10.1007/978-3-031-17143-7_40
  * Arcolezi et al. (2022c) Héber H. Arcolezi, Sébastien Gambs, Jean-François Couchot, and Catuscia Palamidessi. 2022c.  On the Risks of Collecting Multidimensional Data Under Local Differential Privacy.  _arXiv preprint arXiv:2209.01684_ (2022).
  * Bassily et al. (2017) Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2017.  Practical Locally Private Heavy Hitters. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ _(NIPS’17)_. Curran Associates Inc., Red Hook, NY, USA, 2285–2293.
  * Bassily and Smith (2015) Raef Bassily and Adam Smith. 2015.  Local, Private, Efficient Protocols for Succinct Histograms. In _Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing_ _(STOC ’15)_. Association for Computing Machinery, New York, NY, USA, 127–135.  https://doi.org/10.1145/2746539.2746632
  * Bittau et al. (2017) Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. 2017\.  Prochlo: Strong Privacy for Analytics in the Crowd. In _Proceedings of the 26th Symposium on Operating Systems Principles_ _(SOSP ’17)_. Association for Computing Machinery, New York, NY, USA, 441–459.  https://doi.org/10.1145/3132747.3132769
  * Chatzikokolakis et al. (2014) Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Marco Stronati. 2014.  A Predictive Differentially-Private Mechanism for Mobility Traces. In _Privacy Enhancing Technologies_ , Emiliano De Cristofaro and Steven J. Murdoch (Eds.). Springer International Publishing, Cham, 21–41.  https://doi.org/10.1007/978-3-319-08506-7_2
  * Cormode et al. (2021) Graham Cormode, Samuel Maddock, and Carsten Maple. 2021\.  Frequency estimation under local differential privacy.  _Proceedings of the VLDB Endowment_ 14, 11 (July 2021), 2046–2058.  https://doi.org/10.14778/3476249.3476261
  * Ding et al. (2017) Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017\.  Collecting Telemetry Data Privately.  In _Advances in Neural Information Processing Systems 30_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 3571–3580.
  * Ding et al. (2021) Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. 2021.  Retiring Adult: New Datasets for Fair Machine Learning. In _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 6478–6490.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml, (accessed January 2023).
  * Duchi et al. (2013b) John Duchi, Martin J Wainwright, and Michael I Jordan. 2013b.  Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation. In _Advances in Neural Information Processing Systems_ , C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (Eds.), Vol. 26. Curran Associates, Inc.
  * Duchi et al. (2013a) John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013a.  Local Privacy and Statistical Minimax Rates. In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_. IEEE, 429–438.  https://doi.org/10.1109/focs.2013.53
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential Privacy. In _Automata, Languages and Programming_ , Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–12.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006.  Calibrating Noise to Sensitivity in Private Data Analysis.  In _Theory of Cryptography_. Springer Berlin Heidelberg, 265–284.  https://doi.org/10.1007/11681878_14
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al. 2014\.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ 9, 3–4 (2014), 211–407.
  * Erlingsson et al. (2020) Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. 2020\.  Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.  _arXiv preprint arXiv:2001.03618_ (2020).
  * Erlingsson et al. (2019) Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019.  Amplification by shuffling: From local to central differential privacy via anonymity. In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 2468–2479.
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014\.  RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In _Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security_. ACM, New York, NY, USA, 1054–1067.  https://doi.org/10.1145/2660267.2660348
  * Feldman et al. (2022) Vitaly Feldman, Jelani Nelson, Huy Nguyen, and Kunal Talwar. 2022\.  Private frequency estimation via projective geometry. In _Proceedings of the 39th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research)_ , Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (Eds.), Vol. 162. PMLR, 6418–6433.
  * Glerum et al. (2009) Kirk Glerum, Kinshuman Kinshumann, Steve Greenberg, Gabriel Aul, Vince Orgovan, Greg Nichols, David Grant, Gretchen Loihle, and Galen Hunt. 2009.  Debugging in the (Very) Large: Ten Years of Implementation and Experience. In _Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles_ _(SOSP ’09)_. Association for Computing Machinery, New York, NY, USA, 103–116.  https://doi.org/10.1145/1629575.1629586
  * Gursoy et al. (2022) M. Emre Gursoy, Ling Liu, Ka-Ho Chow, Stacey Truex, and Wenqi Wei. 2022.  An Adversarial Approach to Protocol Analysis and Selection in Local Differential Privacy.  _IEEE Transactions on Information Forensics and Security_ 17 (2022), 1785–1799.  https://doi.org/10.1109/TIFS.2022.3170242
  * Joseph et al. (2018) Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner. 2018.  Local Differential Privacy for Evolving Data. In _Advances in Neural Information Processing Systems_ , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc.
  * Kairouz et al. (2016a) Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016a.  Discrete distribution estimation under local privacy. In _Int. Conf. on Machine Learning_. PMLR, 2436–2444.
  * Kairouz et al. (2016b) Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2016b.  Extremal mechanisms for local differential privacy.  _The Journal of Machine Learning Research_ 17, 1 (2016), 492–542.
  * Kasiviswanathan et al. (2008) Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2008\.  What Can We Learn Privately?. In _2008 49th Annual IEEE Symposium on Foundations of Computer Science_. IEEE, 531–540.  https://doi.org/10.1109/FOCS.2008.27
  * Liu et al. (2023) Gaoyuan Liu, Peng Tang, Chengyu Hu, Chongshi Jin, and Shanqing Guo. 2023.  Multi-Dimensional Data Publishing with Local Differential Privacy. In _Proceedings of the 26th International Conference on Extending Database Technology, EDBT 2023, Ioannina, Greece, March 28 - March 31, 2023_. OpenProceedings.org, 183–194.  https://doi.org/10.48786/edbt.2023.15
  * Mahawaga Arachchige et al. (2020) Pathum Chamikara Mahawaga Arachchige, Peter Bertok, Ibrahim Khalil, Dongxi Liu, Seyit Camtepe, and Mohammed Atiquzzaman. 2020.  Local Differential Privacy for Deep Learning.  _IEEE Internet of Things Journal_ 7, 7 (2020), 5827–5842.  https://doi.org/10.1109/JIOT.2019.2952146
  * Naor and Vexler (2020) Moni Naor and Neil Vexler. 2020.  Can Two Walk Together: Privacy Enhancing Methods and Preventing Tracking of Users. In _1st Symposium on Foundations of Responsible Computing (FORC 2020)_ _(Leibniz International Proceedings in Informatics (LIPIcs))_ , Aaron Roth (Ed.), Vol. 156. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 4:1–4:20.  https://doi.org/10.4230/LIPIcs.FORC.2020.4
  * Nguyên et al. (2016) Thông T. Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, and Junbum Shin. 2016\.  Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy.  _ArXiv_ abs/1606.05053 (2016).
  * Ohrimenko et al. (2022) Olga Ohrimenko, Anthony Wirth, and Hao Wu. 2022.  Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data. In _Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ _(PODS ’22)_. Association for Computing Machinery, New York, NY, USA, 237–249.  https://doi.org/10.1145/3517804.3526226
  * Tang et al. (2017) Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. 2017.  Privacy loss in apple’s implementation of differential privacy on macos 10.12.  _arXiv preprint arXiv:1709.02753_ (2017).
  * Apple Differential Privacy Team (2017) Apple Differential Privacy Team. 2017\.  Learning with privacy at scale.  https://docs-assets.developer.apple.com/ml-research/papers/learning-with-privacy-at-scale.pdf, (accessed January 2023).
  * Varma et al. (2022) Gatha Varma, Ritu Chauhan, and Dhananjay Singh. 2022\.  Sarve: synthetic data and local differential privacy for private frequency estimation.  _Cybersecurity_ 5, 26 (2022).  https://doi.org/10.1186/s42400-022-00129-6
  * Wang et al. (2019) Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. 2019\.  Collecting and Analyzing Multidimensional Data with Local Differential Privacy. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. IEEE, 638–649.  https://doi.org/10.1109/ICDE.2019.00063
  * Wang et al. (2017) Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017\.  Locally Differentially Private Protocols for Frequency Estimation. In _26th USENIX Security Symposium (USENIX Security 17)_. USENIX Association, Vancouver, BC, 729–745.
  * Warner (1965) Stanley L. Warner. 1965\.  Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias.  _J. Amer. Statist. Assoc._ 60, 309 (March 1965), 63–69.  https://doi.org/10.1080/01621459.1965.10480775
  * Xue et al. (2022) Qiao Xue, Qingqing Ye, Haibo Hu, Youwen Zhu, and Jian Wang. 2022.  DDRM: A Continual Frequency Estimation Mechanism with Local Differential Privacy.  _IEEE Transactions on Knowledge and Data Engineering_ (2022), 1–1.  https://doi.org/10.1109/TKDE.2022.3177721
  * Zhou and Tan (2021) Xingyu Zhou and Jian Tan. 2021.  Local Differential Privacy for Bayesian Optimization. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 11152–11159.