\section{Risk Analysis}

In this section, we will address how the system proposed in this paper mitigates some of the key risks that might arise when implementing a system that allows analysts to ask queries from the server. In this work, we have assumed an implementation of the aggregation protocol that guarantees that the adversary can only get access to aggregates of at least B users, where the batch size B is routed through, and logged on, the device. One can imagine multiple ways to implement such a functionality, and different implementations would entail their own risk analyses.  In this section, we discuss risks and mitigations for the whole system assuming the aggregation protocol with this functionality is implemented securely. Below is a list of potential risks, and how the system mitigates against them.

\begin{itemize}
\item \textbf{Flexible queries could allow analysts to target small populations.} This risk is mitigated by the fact that differential privacy protects users against individual privacy loss \cite{DR14}, and protects against information being leaked about small populations. The main protection is from the aggregate differential privacy guarantee, with the local differential privacy guarantee as an additional guarantee. Further, an aggregation protocol with the additional functionality that it can enforce a lower bound on the cohort size can ensure that only aggregate information is released.

We note that this protection depends on the cohort containing a sufficiently large number of \emph{honest} users. Thus, the aggregation protocol must mitigate the risk of sybil attacks. Additionally, observe that the targeting criteria (the features of users that a query attempts to learn) being public allows for auditability, which further mitigates the targeting risk.

\item \textbf{Broad query classes could allow for accidental approval of sensitive queries.} This risk is mitigated by allowing the restrictiveness (or broadness) of the query class to be tuned to suit the setting. The query class
can be vetted for concerns other than individual privacy.
\item \textbf{Flexible queries from server may allow an analyst to set their own privacy budget.}
This risk is mitigated by strict privacy budgeting on-device that ensures that privacy loss is carefully controlled. Local privacy budgets are stored and enforced on-device.
	Cohort Aggregate privacy budgets are routed through the device and enforced by the aggregation protocol. The device only needs to trust the aggregation protocol to enforce the minimum cohort size.
\item \textbf{Flexible queries may allow an analyst to ask questions that are not part of the approved query class.}	This risk is mitigated by query verification on-device that ensures only queries in the approved query class are answered by the device. Query logs on-device can also provide further transparency about the queries being asked and answered by the device.
\end{itemize}

\section{Conclusion and Open Problems}

In this work, we proposed a system for enabling interactive federated statistics with strong privacy guarantees. The privacy guarantees are supported by an aggregation protocol that ensures that only aggregate statistics, with cohort aggregate privacy guarantees can be seen by any analyst. This aggregate privacy guarantee is reinforced by local privacy guarantees that are enforced on-device. This architecture allows the user device to maintain control over the privacy assurance and ensures that inadvertent error by an analyst leads to utility loss, \emph{not} privacy loss.

It has been shown in a number of prior works~\cite{Abadi:2016, McMahanRT018, Bagdasaryan:2022} that in the federated setting, private interactive algorithms (enabled by allowing analysts to ask adaptive queries from the server) can greatly improve the accuracy of the private statistics learned. Further research is needed to expand the class of statistics that we can learn in this framework. In practical deployments, user's can have multiple data points.
This additional data can be utilized by adaptive algorithms, for example, the algorithm described in the introduction for learning new phrases can potentially gain from carefully selecting the next data point that the user communicates.
Additionally, there can be heterogeneity in both the quantity and distribution of user data. Heterogeneity poses additional challenges for analysts both in terms of algorithm design and interpretation of results. How to best utilize user data in the multiple-data-points-per-user setting is still an active, and important, area of research.

\section*{Acknowledgements}
We thank Úlfar Erlingsson, Julien Freudiger for their guidance during the early stages of this project; Rohith Prakash, Noah Jacobs, Andrew Cherkashyn, Mona Chitnis, Roman Holenstein, Gaurav Chandalia, Chiraag Sumanth, Mayank Yadav, Abhishek Bhowmick, JP Lacerda, Yuan Li, Zhong Wang, Michael Scaria, Kristine Guo, Oliver Chick, Hwasung Lee, Yi Sheng Chan for their help with this effort.

\bibliographystyle{abbrv}

\section{Deletion Differential Privacy}\label{sec:deletionDP}

In this section, we will outline how one could use deletion model of local differential privacy as the main local differential privacy, rather than the replacement model outlined in Defintions~\ref{LDP} and~\ref{localDP}. First, let us formally define the deletion model.

\begin{defn}[Local Randomizer \cite{DR14,Kasiviswanathan:2008,Erlingsson2020}]
Let $\mathcal{A}: \mathcal{D} \to \mathcal{Y}$ be a randomized algorithm mapping a data entry in $\mathcal{D}$ to $\mathcal{Y}$.  The algorithm $\mathcal{A}$ is an $\epsilon$-DP local randomizer in the \emph{deletion} model if there exists a reference distribution $\mathcal{R}$ such that for all data entries $d \in \mathcal{D}$ and all events $E\subset \mathcal{Y}$, we have
\[
- \epsilon \leq \ln\left(\frac{\Pr[\mathcal{A}(d) \in E ]}{\Pr[\mathcal{R} \in E ]}  \right)\leq \epsilon
\]
\end{defn}

The deletion model of differential privacy is closely related to the replacement model introduced in Definition~\ref{LDP}; if $\mathcal{A}$ is $\epsilon$-DP in the deletion model then $\mathcal{A}$ is $\epsilon'$-DP in the replacement model where $\epsilon'$ can take any value in $[\epsilon, 2\epsilon]$. Exactly where the replacement privacy guarantees lies in $[\epsilon, 2\epsilon]$ is algorithm dependent. Conversely, if $\mathcal{A}$ is $\epsilon$-DP in the replacement model then it is $\epsilon$-DP in the deletion model.

Differential privacy in the deletion model ensures that it is impossible to confidently determine whether an individual contributed data or simply reported a sample from the reference distribution (i.e. did not contribute data). This is slightly weaker than replacement DP, which guarantees that from the output of $\mathcal{A}$, it is impossible to confidently guess whether the user’s data point was $d$ or $d'$, for any pair $d$ and $d'$. If we think of the reference distribution as the "average" user behavior then, intuitively, deletion DP means it hard to distinguish the behavior of an outlier from the average behavior. Replacement DP provides the slightly stronger guarantee that it is hard to distinguish between any two outliers, even if the outliers are ``opposites".
One can define the deletion model for local differential privacy in exactly the same manner as Definition~\ref{localDP} where the local randomizers must be $\epsilon$-DP in the deletion model.

\subsection{Symmetric Private One-Hot Encoding}\label{sec:symOHE}

In section, we will outline a locally differentially private randomizer that is appropriate for use when implementing the system we have outlined with deletion local differential privacy. \emph{Symmetric private one-hot encoding} is a slight variant on asymmetric private one-hot encoding, which was outlined in Section~\ref{sec:OHE}.

\subsubsection{Client-Side Algorithm}

The client encodes their bit as a vector of length $|\mathcal{D}|$, which is 1 in the position of the client's data, and 0 elsewhere. They then independently send the value of each coordinate using a standard differentially private algorithm called randomized response.
Algorithm~\ref{algclient:OHE} gives details of the client-side algorithm.

\begin{algorithm}[htb]
	\caption{Client-Side $\A_{\sf client-symOHE}$} \label{algclient:OHE}
	\begin{algorithmic}[1]
		\REQUIRE Data element $d \in \mathcal{D}$; $\epsilon$.
		\STATE Initialise $v, \tilde{v} \in \{0\}^{\mathcal{D}}$
		\STATE $v_d = 1$
		\FOR{$d'\in\mathcal{D}$}
			\STATE $\tilde{v_{d'}} = \begin{cases} v_{d'} & \text{with probability } \frac{e^{\epsilon}}{1+e^{\epsilon}}\\ 1-v_{d'} & \text{otherwise} \end{cases}$
		\ENDFOR
		\RETURN $\tilde{v}$
	\end{algorithmic}
\end{algorithm}

\begin{thm}[Privacy guarantee] \label{privacysymOHE}
For any $\epsilon>0$, $\A_{\sf client-symOHE}$ is $\epsilon$-locally differentially private in the deletion model.
\end{thm}

\begin{proof}
The reference distribution $\mathcal{R}$ is obtained by independently for each coordinate outputting 0 with probability $\frac{e^{\epsilon}}{1+e^{\epsilon}}$ and 1 otherwise. Note that given datapoint $d\in\mathcal{D}$, the reference distribution matches the distribution $\A_{\sf client-symOHE}(d; \epsilon)$ on every coordinate except $d$. Therefore, given $\pmb{v}\in\{0,1\}^{\mathcal{D}}$,
\begin{align*}
\frac{\Pr(\mathcal{R}=\pmb{v})}{\Pr(\A_{\sf client-symOHE}(d)=\pmb{v})} &= \frac{\prod_{d'\in\mathcal{D}}\Pr((\mathcal{R})_{d'}=\pmb{v}_{d'})}{\prod_{d'\in\mathcal{D}} \Pr((\A_{\sf client-symOHE}(d))_{d'}=\pmb{v}_{d'})}\\
&=\frac{\Pr((\mathcal{R})_{d}=\pmb{v}_{d})}{\Pr((\A_{\sf client-OHE}(d))_{d}=\pmb{v}_{d})}\\
&=\begin{cases}
\frac{e^{\epsilon}}{1} & \text{if } \pmb{v}_d=0\\
\frac{1}{e^{\epsilon}} & \text{if } \pmb{v}_d=1
\end{cases}.
\end{align*}
\end{proof}

\noindent Note that $\A_{\sf client-symOHE}$ is $2\epsilon$-locally differentially private in the replacement model.

\subsubsection{Server-Side Algorithm}

The server-side algorithm $\A_{\sf server-symOHE}$ simply aggregates the local reports, and de-bias the resulting noisy histogram.

\begin{algorithm}[htb]
	\caption{Server-Side $\A_{\sf server-symOHE}$} \label{algserver:OHE}
	\begin{algorithmic}[1]
		\REQUIRE $\{\tilde{v}^{(1)}, \cdots, \tilde{v}^{(n)}\}$; $\epsilon$.
		\STATE Construct $\tilde{f}:\mathcal{D}\to\mathbb{R}$ where for all $d\in\mathcal{D}$
		\[\tilde{f}(d) = \frac{1+e^{\epsilon}}{e^{\epsilon}-1}\sum_{i=1}^n \tilde{v}^{(i)}_d-\frac{n}{e^{\epsilon}-1}\]
		\RETURN $\tilde{f}$
	\end{algorithmic}
\end{algorithm}

\begin{thm}[Utility guarantee]\label{OHEutilityguarantee}
Let $\epsilon>0$, $d\in\mathcal{D}$, and $\tilde{f}(d)$ be the $d$-th coordinate of the output of $\A_{\sf server-symOHE}(\tilde{v}^{(1)}, \cdots, \tilde{v}^{(n)}; \epsilon)$ where each $\tilde{v}^{(1)}$ is reported using $\A_{\sf client-symOHE}$. If $f(d)$ is the true frequency of $d$ then,
\[\mathbb{E}[\tilde{f}(d)]=f(d)\]
\[\var{\tilde{f}(d)} = n\cdot \frac{e^{\epsilon}}{(e^{\epsilon}-1)^2}.\]
\end{thm}

\begin{proof}
For each $i\in[n]$,
\[\mathbb{E}[\tilde{v}^{(i)}_d]=\frac{e^{\epsilon}-1}{1+e^{\epsilon}}v^{(i)}_d+\frac{1}{1+e^{\epsilon}} \;\;\;\text{and}\;\;\; \var{\tilde{v}^{(i)}_d)}= \frac{e^{\epsilon}}{(e^{\epsilon}+1)^2}.\] Therefore,
\begin{align*}
\mathbb{E}[\tilde{f}(d)] &= \frac{1+e^{\epsilon}}{e^{\epsilon}-1}\sum_{i=1}^n \mathbb{E}[\tilde{v}^{(i)}_d]-\frac{n}{e^{\epsilon}-1}\\
&= \frac{1+e^{\epsilon}}{e^{\epsilon}-1}\sum_{i=1}^n \left(\frac{e^{\epsilon}-1}{1+e^{\epsilon}}v^{(i)}_d+\frac{1}{1+e^{\epsilon}}\right)-\frac{n}{e^{\epsilon}-1}\\
&= \sum_{i=1}^n v^{(i)}_d
\end{align*}
and
\begin{align*}
\var{\tilde{f}(d)} &= \var{\frac{1+e^{\epsilon}}{e^{\epsilon}-1}\sum_{i=1}^n \tilde{v}^{(i)}_d}\\
&= \sum_{i=1}^n \left(\frac{1+e^{\epsilon}}{e^{\epsilon}-1}\right)^2 \var{ \tilde{v}^{(i)}_d}\\
&= \sum_{i=1}^n \left(\frac{1+e^{\epsilon}}{e^{\epsilon}-1}\right)^2 \frac{e^{\epsilon}}{(e^{\epsilon}+1)^2}\\
&=n\cdot \frac{e^{\epsilon}}{(e^{\epsilon}-1)^2}
\end{align*}
\end{proof}

\subsubsection{Privacy Amplification by Aggregation Bounds for Private One-Hot Encoding}

Theorem~\ref{amplificationbyaggregation} gave an upper bound on the privacy parameters for aggregating $n$ local reports, each sent using a replacement local DP randomizer. We also discussed that an upper bound could be computed numerically based on algorithms presented in~\cite{Feldman:2022}. When using local DP randomizers that are $\epsilon_0$-DP in the deletion model, one can use Theorem~\ref{amplificationbyaggregation} after using the conversion from deletion DP privacy parameters to replacement DP privacy parameters. However, this approach is suboptimal for many local randomizers, including symmetric private OHE. In this section, we will outline a numerical method for computing an upper bound on the cohort aggregate privacy guarantee when aggregating $n$ copies of symmetric private OHE. We'll be using the privacy amplification in terms of an alternate version of differential called R\'enyi differential privacy.

\begin{defn}[R\'enyi divergence]
For two random variables $P$ and $Q$, the R\'enyi divergence of $P$ and $Q$ of order $\alpha>1$ is \[D^{\alpha}(P\|Q) = \frac{1}{\alpha-1}\ln \mathbb{E}_{x\sim Q}\left[\left(\frac{P(x)}{Q(x)}\right)^{\alpha} \right] .\]
For $\alpha =1$, $D^{1}(P\|Q) = \mbox{KL}(P\|Q) = \mathbb{E}_{x\sim P}\left[\ln\left(\frac{P(x)}{Q(x)}\right)\right]$.
\end{defn}

Firstly, we'll need a method for computing the general amplification by aggregation bounds for binary randomized response. Binary randomized response is defined by \[\texttt{2RR}(d; \epsilon_0) = \begin{cases} d & \text{with probability} \frac{e^{\epsilon_0}}{e^{\epsilon_0}+1} \\ 1-d & \text{otherwise.} \end{cases}\] The algorithm $\A_{\sf client-symOHE}$ simply performs binary randomized response individually on each coordinate. Define $\rho_{\texttt{2RR}}(n, \alpha, \epsilon_0)$ to be a function such that for any two databases $D, D'\in\{0,1\}^n$ that differ on the data of a single individual, \[D^{\alpha}\left(\sum_{i=1}^n \texttt{2RR}(d^{(i)}; \epsilon_0), \sum_{i=1}^n \texttt{2RR}(d^{'(i)}; \epsilon_0)\right)\le \rho_{\texttt{2RR}}(n,\alpha,\epsilon_0)\]
For any given $n, \alpha$ and $\epsilon_0$, the function $\rho_{\texttt{2RR}}(n, \alpha, \epsilon_0$ can be computed numerically. One can also use general upper bounds on the privacy amplification by aggregation in terms of R\'enyi differential privacy, presented in \cite{Feldman:2022}.

\begin{thm}\label{RAPPORrenyi}
Let $\epsilon_0>0, \epsilon>0$, $\delta\in[0,1]$, $n\in\mathbb{N}$, $\alpha>1$ and $\mathcal{D}$ be a finite data universe. Then, for all pairs of datasets $D, D'\in\mathcal{D}^n$ that differ on the data of a single individual, \[D^{\alpha}\left(\sum_{i=1}^n \A_{\sf client-symOHE}(d^{(i)}; \epsilon_0), \sum_{i=1}^n \A_{\sf client-symOHE}(d^{'(i)}; \epsilon_0)\right)\le 2\rho_{\texttt{2RR}}(n, \alpha, \epsilon_0).\]
\end{thm}

\begin{proof}
Assume without loss of generality that $D$ and $D'$ differ on the data of the first individual. We can view each coordinate as an independent differentially private local randomizer, and the output of $\A_{\sf client-symOHE}$ as the composition of these local randomizers.
Notice that the distributions of $\sum_{i=1}^n \A_{\sf client-symOHE}(d^{(i)}; \epsilon_0)$ and $\sum_{i=1}^n \A_{\sf client-symOHE}(d^{'(i)}; \epsilon_0)$ only differ in the $d^{(1)}$th and $d^{'(1)}$th coordinate. Therefore, we can use the composition theorem of R\'enyi differential privacy \cite{Mironov2017RnyiDP}.
\begin{align*}
D^{\alpha}&\left(\sum_{i=1}^n \A_{\sf client-symOHE}(d^{(i)}; \epsilon_0), \sum_{i=1}^n \A_{\sf client-symOHE}(d^{'(i)}; \epsilon_0)\right)\\
&\le D^{\alpha}\left(\left[\sum_{i=1}^n \A_{\sf client-symOHE}(d^{(i)}; \epsilon_0)\right]_{d^{(1)}}, \left[\sum_{i=1}^n \A_{\sf client-symOHE}(d^{'(i)}; \epsilon_0)\right]_{d^{(1)}}\right)\\
&\hspace{0.5in} +D^{\alpha}\left(\left[\sum_{i=1}^n \A_{\sf client-symOHE}(d^{(i)}; \epsilon_0)\right]_{d^{'(1)}}, \left[\sum_{i=1}^n \A_{\sf client-symOHE}(d^{'(i)}; \epsilon_0)\right]_{d^{'(1)}}\right)\\
&\le 2\epsilon_{\texttt{2RR}}(n, \alpha, \epsilon_0),
\end{align*}
where the final bound holds since restricted to each coordinate, $\A_{\sf client-symOHE}(d^{'(i)}; \epsilon_0)$ is simply binary randomized response.
\end{proof}

There are standard formulas for converting bounds on the R\'enyi divergence to privacy guarantees in terms of $(\epsilon, \delta)$-DP~\cite{Mironov2017RnyiDP, Kamath:2020}.
Thus, we can obtain an upper bound on the privacy amplification by aggregation when each user uses $\A_{\sf client-symOHE}$ to communicate their data, by converting Theorem~\ref{RAPPORrenyi} into a bound on the privacy loss in terms of $(\epsilon, \delta)$-DP.

\section{Introduction}

Gaining insight into trends in the user population is an important aspect of improving the user experience. For example,
learning popular words that users type, helps improve keyboard language models. The data needed to derive these insights can be personal and sensitive, and must be kept private. We study the problem of learning aggregate information about data that lives on device, while providing strong privacy protection to individuals. Often these data are multi-dimensional, and one wants to learn, for example, correlations between various attributes. Traditional approaches to this problem such as RAPPOR~\cite{erlingsson2014rappor} and others (e.g. ~\cite{applelearningatscale}) convert the high-dimensional data to categorical data (e.g. by bucketing), and use algorithms such as binary randomized response  \cite{W65} (2RR) on a one-hot encoding of the data, or refinements of it to build a noisy histogram. These systems are often static; they are designed to, statically, send snapshots of the data at a pre-specified cadence.

In this work, we propose an iterative approach to such problems, that aligns better with how data analysts typically interact with data. Such an interactive approach can also allow for more accurate answers to queries of interest. We describe how such an approach can be implemented and consider the privacy risks against different kinds of attackers.
An aggregation protocol ensures that the server only sees the \emph{aggregate} of the reports sent by users. We use a locally differentially privacy (DP) algorithm to add noise to the reports, so that the privacy of the final aggregate can be analyzed using recent upper bounds for privacy amplification by shuffling \cite{CheuSUZZ19, ErlingssonFMRTT19}.

One of the main challenges with implementing a federated statistics platform that allows for interaction is ensuring that the device can enforce any privacy constraints; both individual privacy constraints and ensuring that the user's data is only used for appropriate queries. To address individual privacy constraints, we propose an on-device differential privacy budget accountant that allows the device to limit the total individual privacy risk of privatized data leaving the device. We also propose an on-device query verification framework that validates that the user's data is only used in queries that are part of an approved query class. More details on both of these key features are given in Section~\ref{systemsoverview}. We will also discuss additional concerns that may arise when implementing such a system, including secure data storage and auditability.

At a high level, interactive algorithms for histogram estimation build on top of a private histogram algorithm such as RAPPOR~\cite{erlingsson2014rappor} or PI- RAPPOR ~\cite{pmlr-v139-feldman21a}. However, instead of a fixed histogram of the data, the algorithm can iteratively specify how the data should be bucketed to define the histogram cells. For example we may first build a coarse grained histogram of the data. Based on the measurements thus made, the algorithm can refine the bucketing and build a new histogram.
Each such query gets answered by devices using a local DP algorithm, coupled with an aggregation framework such as PRIO~\cite{Prio}. Privacy amplification by shuffling bounds allow us to control the privacy loss of one such query.
Results bounding the privacy loss of composing multiple differentially private algorithms can allow us to ensure that the total privacy cost, of the sequence of adaptive queries, against the server can be controlled.
We propose a system design that makes it possible for the user’s device to verify various parameters of the queries and ensure a pre-specified privacy budget. Our system starts with a specification of the set of allowed queries and privacy budgets for a particular analysis. Our design ensures that the device can enforce these constraints. Indeed one of our design goals is that an inadvertent error by the analyst translates to loss of utility for the analyst, and cannot lead to additional privacy loss.

This interactive approach offers more accurate answers than a more traditional static approach in many settings. The benefit of interactive queries in such contexts is well-studied; indeed in the central model of differential privacy, there is a long line of work on adaptive approaches to building histograms~(e.g. \cite{Cormode2012DifferentiallyPS, Qardaji:2012, Song:2013, Bagdasaryan:2022}). As a simple example, suppose that we wish to learn new n-grams of words that are typed on devices. In a traditional static system, we would first decide on the length n of the n-grams we want to learn in advance, say n = 4. Each device would pick a random 4-gram that they typed, and send a local DP report based on it. We would thus build a noisy histogram of the frequency counts of the 4-grams chosen by the devices. In an interactive approach, we would first construct a histogram of 1-grams, i.e. of the popular words. We then use the knowledge of the frequent 1-grams to restrict our search for 2-grams; we only attempt to learn 2-grams that start with a frequent 1-gram. The frequent 2-grams are then extended to 3-grams and so on. An obvious advantage of this approach, and one exploited in previous work in the central model, is that we learn a hierarchical representation of the data and e.g. get the frequent 3-grams which may not be prefixes of any
frequent 4-gram. Note that estimating the frequency of a 3-gram by adding up frequencies of all 4-grams that start with it is not a feasible option in the DP setting as each of these frequencies has some noise added, leading to a much larger standard deviation for the noise for the sum than is required. The limit on the number of frequent 3-grams also limits the number of possible 4-grams we potentially report on. Thus the “dictionary’‘ over which we run a histogram query is smaller, allowing for higher accuracy and efficiency. In addition, in the event that user’s have multiple 4-grams on their device, this approach makes it feasible to select which 4-gram to report on, based on the learnt information. More generally, the device may report on a subset of 4-grams~\cite{Kim:2021, pmlr-v119-gopi20a} and restricting oneself to 4-grams whose prefix 3-grams are frequent in the dataset can lead to more accurate answers.
Such an approach works broadly for any hierarchically structured data universe, of which n-grams over words is but one example. Geographical data falls most naturally in this class and has been used for visualizations in several works, see, for example~\cite{Erlingsson2020}. Understanding the distribution of a single real-valued feature also falls in this category: we would like to bucket the data into intervals that are as fine as can be supported by noisy histogram measurements. When the distribution is unknown, we can learn the right bucketing by following such an adaptive algorithm, repeatedly refining buckets with large counts.
We will consider learning new $n$-grams (sequences of $n$ words) typed by users using the keyboard as a running example throughout this paper.

In addition to greater algorithmic flexibility, an interactive approach is more compatible with how a data analyst would typically study a dataset. They may start with looking at the one-dimensional marginals of the data at some granularity, and then want to look at 2-way marginals, or for a bucketization of the data that depends on the distribution.

\section{Asymmetric Private One-Hot Encoding}\label{sec:OHE}

\emph{Asymmetric private one-hot encoding} outputs a histogram of counts over a domain $\mathcal{D}$, for a dataset consisting of $n$ individuals. This algorithm is simple and has high accuracy, but has high communication complexity when the data domain is large. At a high level, one hot encoding is composed of a client-side algorithm and a server-side algorithm.  The client-side algorithm is an $\epsilon$-DP local randomizer and ensures that the data that leaves the user's device is $\epsilon$-locally differentially private. The server side algorithm simply aggregates the local responses, and de-bias the result. This algorithm was proposed and used in RAPPOR \cite{erlingsson2014rappor}.  Let $f:\mathcal{D} \rightarrow \mathbb{R}$ be an oracle that gives the frequency of an element in $\mathcal{D}$ from a given dataset $\{d^{(1)},\cdots, d^{(n)}\}$. We design a differentially private algorithm $\mathcal{A}$ that outputs an oracle $\tilde f: \mathcal{D}\rightarrow \mathbb{R}$ which is an unbiased estimate of $f(d)$, that is $\forall d\in\mathcal{D}, \mathbb{E} \left[ \tilde f(d) \right] = f(d)$, and has small variance.

\subsection{Client-Side Algorithm}

The client encodes their bit as a vector of length $|\mathcal{D}|$, which is 1 in the position of the client's data, and 0 elsewhere. They then independently send the value of each coordinate using a standard differentially private algorithm that is an asymmetric version of randomized response. Let $\texttt{Bernoulli}(p)$ be a Bernoulli random variable which is $1$ with probability $p$ and $0$ with probability $1-p$.
Algorithm~\ref{algclient:OHE} gives details of the client-side algorithm.

\begin{algorithm}[htb]
	\caption{Client-Side $\A_{\sf client-OHE}$} \label{algclient:OHE}
	\begin{algorithmic}[1]
		\REQUIRE Data element $d \in \mathcal{D}$; $\epsilon$.
		\STATE Initialise $v, \tilde{v} \in \{0\}^{\mathcal{D}}$
		\STATE $v_d = 1$ \label{datadependence}
		\FOR{$d'\in\mathcal{D}$}
			\STATE $\tilde{v_{d'}} \sim \begin{cases} \texttt{Bernoulli}(1/2) & \text{if } v_{d'}=1 \\ \texttt{Bernoulli}(1/(e^{\epsilon}+1)) & \text{if } v_{d'}=0 \end{cases}$
		\ENDFOR
		\RETURN $\tilde{v}$
	\end{algorithmic}
\end{algorithm}

\begin{thm}[Privacy guarantee] \label{privacyOHE}
For any $\epsilon>0$, $\A_{\sf client-OHE}$ is $\epsilon$-locally differentially private in the replacement model.
\end{thm}

\begin{proof}[Proof of Theorem~\ref{privacyOHE}]
Let $d, d'\in\mathcal{D}$ be two data points and $\epsilon>0$. Therefore, for any $(v_{d''})_{d''\in\mathcal{D}}\in\{0,1\}^{\mathcal{D}}$,
\begin{align*}
\frac{\Pr(\A_{\sf client-OHE}(d)=(v_{d''})_{d''\in\mathcal{D}})}{\Pr(\A_{\sf client-OHE}(d)=(v_{d''})_{d''\in\mathcal{D}})} &= \frac{\Pr({\rm Bernoulli}\left(1/2\right)=v_d)\prod_{d''\in\mathcal{D}, d''\neq d}\Pr({\rm Bernoulli}\left(\frac{1}{e^{\epsilon}+1}\right)=v_{d''})}{Pr({\rm Bernoulli}\left(1/2\right)=v_{d'})\prod_{d''\in\mathcal{D}, d''\neq d'}\Pr({\rm Bernoulli}\left(\frac{1}{e^{\epsilon}+1}\right)=v_{d''})}\\
&= \frac{\Pr({\rm Bernoulli}\left(1/2\right)=v_d)\Pr({\rm Bernoulli}\left(\frac{1}{e^{\epsilon}+1}\right)=v_{d'})}{\Pr({\rm Bernoulli}\left(\frac{1}{e^{\epsilon}+1}\right)=v_{d})\Pr({\rm Bernoulli}\left(1/2\right)=v_{d'})}\\
&= \frac{\Pr({\rm Bernoulli}\left(\frac{1}{e^{\epsilon}+1}\right)=v_{d'})}{\Pr({\rm Bernoulli}\left(\frac{1}{e^{\epsilon}+1}\right)=v_{d})}\\
&\in [e^{-\epsilon}, e^{\epsilon}]
\end{align*}
\end{proof}

\subsection{Server-Side Algorithm}

The server-side algorithm $\A_{\sf server-OHE}$ simply aggregates the local reports, and de-bias the resulting noisy histogram.

\begin{algorithm}[htb]
	\caption{Server-Side $\A_{\sf server-OHE}$} \label{algserver:OHE}
	\begin{algorithmic}[1]
		\REQUIRE $\{\tilde{v}^{(1)}, \cdots, \tilde{v}^{(n)}\}$; $\epsilon$.
		\STATE Construct $\tilde{f}:\mathcal{D}\to\mathbb{R}$ where for all $d\in\mathcal{D}$
		\[\tilde{f}(d) = \frac{2(1+e^{\epsilon})}{e^{\epsilon}-1}\sum_{i=1}^n \tilde{v}^{(i)}_d-\frac{n}{e^{\epsilon}-1}\]
		\RETURN $\tilde{f}$
	\end{algorithmic}
\end{algorithm}

\begin{thm}[Utility guarantee]\label{OHEutilityguarantee}
Let $\epsilon>0$, $d\in\mathcal{D}$, and $\tilde{f}(d)$ be the $d$-th coordinate of the output of $\A_{\sf server-OHE}(\tilde{v}^{(1)}, \cdots, \tilde{v}^{(n)}; \epsilon)$ where each $\tilde{v}^{(1)}$ is reported using $\A_{\sf client-OHE}$. If $f(d)$ is the true frequency of $d$ then,
\[\mathbb{E}[\tilde{f}(d)]=f(d)\]
\[\var{\tilde{f}(d)} = n\cdot \frac{4e^{\epsilon}}{(e^{\epsilon}-1)^2}+f(d).\]
\end{thm}

\section{Device Enrollment - Detailed Example}\label{appendix:deviceenrollment}

As an example, suppose the analysts' goal is to learn the popular $n$-grams joined with user age.
An example of a recipe used for learning a histogram of popular 3-grams, joined with age of the device owner is presented in Figure \ref{fig:recipe}. The fields in this recipe are as follows:

\begin{itemize}
\item recipe identifier: a unique identifier for this recipe.
\item version: recipe version for compatibility.
\item analysis identifier: provides the unique identifier which is used as the prefix for collection ids so that the server can identify payloads corresponding to this histogram query. This prefix can be part of a list hardcoded as part of the device OS as well, for further verification. Furthermore, data deemed as \emph{non-sensitive}, as well as experiment ids, could be appended to this string before submission to server.
\item query: this query is first verified and if it is an allowed query, it will be executed on the on-device data. If the query is not allowed, the system exits and no privatized record is shared with the secure aggregation protocol.
\item cohorts: if any data, relevant to the query, is determined to be non-sensitive, then it is specified here. This data could be appended to the collection id prefix provided in client identifier. For example, when learning n-grams of known words, the locale (device language like $``en\_US"$) may be deemed \emph{non-sensitive}. The device should keep a list of approved non-sensitive data fields for each analysis hardcoded as part of the device OS.

\item data content type: a scheme to encode the query output to a one hot vector. In this field, we determine the tuple of features we intend to learn, and a rule for bucketing each element of this tuple. In the example presented in Figure  \ref{fig:recipe}, we choose to build a histogram of  ({\bf age, ngrams}).
\begin{itemize}
\item Age is bucketed based on the bucket boundaries provided in the recipe. In the example recipe in Figure \ref{fig:recipe}, the buckets for age are $\{\emph{OOV}, \emph{[20, 30)}, \emph{[30, 40]}, \cdots, \emph{[70, 80)}] $, where \emph{OOV} is added on the device for the elements which are not covered in the bucketing rule. The total number of age buckets is $(1 + 7)$.
\item  n-grams are bucketed based on the prefix tree, and the set of known words provided on the recipe. Every combination of prefix tree leaf and a known word listed in recipe is considered to be a bucket. In addition to OOV token, the device adds an \emph{end-token} to determine if a leaf in the given prefix tree is a leaf as well. For the recipe in Figure \ref{fig:recipe}, the buckets for 3-grams are $\{$\emph{OOV}, \emph{hello world end-token},\emph{hello world OOV}, \emph{hello world a}, $\cdots,$ \emph{i got world}$\}$. The total number of buckets are
$(1 + 3 \times (1 + 1 + 9))$
\item eventually, every combination of  buckets above builds a one hot vector for ({\bf age, ngrams}). The total number of bins will be $(1 + 7) \times (1 + 3 \times (1 + 1 + 9))$
\end{itemize}

\end{itemize}

\begin{figure}[H]
	\begin{center}
			\includegraphics[scale=0.4]{recipe.png}
	\caption{Sample recipe for learning join distribution of 3-grams and device owner age.}
		\label{fig:recipe}
	\end{center}
\end{figure}

\section{Mathematical Preliminaries}
Consider a data universe $\mathcal{D}$ which has $p$ elements, typically written as $[p] = \{ 1, \cdots, p\}$. Let $n$ be the total number of records, and for record $i \in [n]$, denote its data entry as $d^{(i)} \in \mathcal{D}$.

\subsection{Differential Privacy}

In this work, we describe a system with two levels of privacy protection; differential privacy in the aggregate model and differential privacy in the local model. The system is designed to provide the first level of privacy through the use of an aggregation protocol. An aggregation protocol ensures that the server only has access to the sum of the individual reports sent from each device. The aggregate differential privacy guarantees are achieved after the data leaves the aggregation protocol. As a secondary layer of privacy protection, local differential privacy guarantees are enforced on device: any sensitive data leaving a user's device will be protected by local differential privacy. We will introduce these two types of privacy guarantees in this section.

\subsubsection{Local Differential Privacy}

Let us first introduce local differential privacy. This privacy guarantee is enforced on-device via the use of local randomizers.

\begin{defn}[Local Randomizer \cite{DR14,Kasiviswanathan:2008,Erlingsson2020}]\label{LDP}
Let $\mathcal{A}: \mathcal{D} \to \mathcal{Y}$ be a randomized algorithm mapping a data entry in $\mathcal{D}$ to an output space $\mathcal{Y}$.
The algorithm $\mathcal{A}$ is an $\epsilon$-DP local randomizer if for all pairs of data entries $d,d'\in\mathcal{D}$, and all events $E\subset\mathcal{Y}$, we have $$
- \epsilon \leq \ln\left(\frac{\Pr[\mathcal{A}(d) \in E ]}{\Pr[\mathcal{A}(d') \in E ]}  \right)\leq \epsilon.
$$
\end{defn}
\noindent The privacy parameter $\epsilon$ captures the \emph{privacy loss} consumed by the output of the algorithm. If $\epsilon = 0$ then the output is independent of the input and we are ensuring perfect privacy, while $\epsilon = \infty$ enforces no constraints on $\mathcal{A}$ and hence provides no privacy guarantee. Differential privacy for an appropriate $\epsilon$ ensures that it is impossible to confidently determine what the individual contribution was, given the output of the mechanism. In turn, this implies a strong Bayesian interpretation: the posterior given the output of the mechanism is point-wise multiplicatively close to the prior one may have about an individual's data.

In general, differential privacy is defined for algorithms with input databases with more than one record. In the local model of differential privacy, algorithms may only access the data through a local randomizer so that no raw data leaves the device. For a single round protocol, local differential privacy is defined as follows:
\begin{defn}[Local Differential Privacy \cite{Kasiviswanathan:2008}]\label{localDP}
Let $\mathcal{A}: \mathcal{D}^n \to \mathcal{Z}$ be a randomized algorithm mapping a dataset with $n$ records to some arbitrary range $\mathcal{Z}$.  The algorithm $\mathcal{A}$ is $\epsilon$-local differentially private if it can be written as $\mathcal{A}(d^{(1)}, \cdots, d^{(n)}) = \phi\left(\mathcal{A}_1(d^{(1)}), \cdots, \mathcal{A}_n(d^{(n)}) \right)$ where the $\mathcal{A}_i: \mathcal{D} \to \mathcal{Y}$ are $\epsilon$-local randomizers for each $i \in [n]$ and $\phi: \mathcal{Y}^n \to \mathcal{Z}$ is some post-processing function of the privatized records $\mathcal{A}_1(d^{(1)}),\cdots, \mathcal{A}_n(d^{(n)})$.  Note that the post-processing function does not have access to the raw data records.
\end{defn}

\noindent Local differential privacy guarantees are enforced on-device.

The definition of a local randomizer given in Definition~\ref{LDP} is sometimes called the \emph{replacement model} of local differential privacy. A slightly weaker notion referred to as the deletion model \cite{Erlingsson2020} can also be used to provide meaningful privacy guarantees with slightly more accurate results when local differential privacy is the primary privacy guarantee. Since we are concerned with aggregate differential privacy in this paper, we will focus on the replacement model, which is more appropriate for combining with aggregate differential privacy.

\subsubsection{Aggregate Differential Privacy}

The aggregate model of differential privacy is a distributed model of computation in which, as in the local model, clients hold their own data and a server communicates with the clients in a federated manner to perform data analysis. In addition, the model includes a \emph{aggregation protocol} that sums the local reports, with the guarantee that the output of the aggregation protocol does not reveal anything about the local reports except their sum\footnote{The term aggregation protocol is commonly used to refer to protocols that perform other types of aggregation. In this paper, we will only be referring to aggregation protocols that output the sum of the input values}. The aggregation protocol computes the sum of the local reports, and this is released to the server\footnote{The aggregate model of DP is a special case of the more general and common shuffle model of differential privacy introduced in \citep{ErlingssonFMRTT19, CheuSUZZ19} which permutes the local reports, rather than summing. Since the system we propose uses an aggregation protocol, we focus on the aggregate model of DP in this paper. The sum of the local reports reveals strictly less information than a permutation of the local reports, so the aggregate model enjoys stronger privacy guarantees.}

\begin{defn}\label{defnaggregateDP}
A single round algorithm $\mathcal{A}$ is $(\epsilon, \delta)$-DP in the aggregate model if the output of the aggregation protocol on two datasets that differ on the data of a single individual are close. Formally, an algorithm $\mathcal{A}:\mathcal{D}^n\to\mathcal{Z}$ is $(\epsilon, \delta)$-DP in the aggregate model if the following conditions both hold:
\begin{itemize}
\item it can be written as $\mathcal{A}(d^{(1)}, \cdots, d^{(n)})=\phi(\texttt{Aggregator}(f(d^{(1)}), \cdots, f(d^{n)}))$ where $f:\mathcal{D}\to\mathcal{Z}$ is a randomized function that transforms that data, $\texttt{Aggregator}$ is an aggregation protocol, and $\phi:\mathcal{Y}^n\to\mathcal{Z}$ is some post-processing of the aggregated report
\item for any pair of datasets $D$ and $D'$ that differ on the data of a single individual, and any event $E$ in the output space,
\[
\Pr(\mathcal{A}(D)\in E)\le e^{\epsilon} \Pr(\mathcal{A}(D')\in E)+\delta.
\]
\end{itemize}
Note that the post-processing function takes the aggregation as its input and does not have access to the individual reports.
\end{defn}

A multi-round algorithm $\mathcal{A}$ is $(\epsilon,\delta)$-DP in the aggregate model if it is the composition of single round algorithms which are DP in the aggregate model, and the total privacy loss of $\mathcal{A}$ is $(\epsilon,\delta)$-DP.
One can formulate a version of Definition~\ref{defnaggregateDP} for multi-round algorithms, for a more in-depth discussion see \cite{Jain2021ThePO}. In this paper, we will assume that the privacy guarantee of multi-round algorithms is computed using standard theorems that bound the privacy guarantee of the adaptive composition of multiple differentially private single round algorithms~\cite{DMNS06, DRV}. This is the case for most algorithms of interest in this setting.
In the system described in this paper, we will always use functions $f$ that are $\epsilon_0$-DP local randomizers. This ensures that all our algorithms are $\epsilon_0$-differentially private in the local model \emph{and} $(\epsilon,\delta)$-differentially private in the aggregate model. When each user uses a DP local randomizer to communicate their data, the privacy guarantee in the aggregation model, $\epsilon$, can be bounded by a quantity that is a function of both $\epsilon_0$, the privacy guarantee in the local model, and $n$, the number of users that participate in the aggregation protocol. The following result, commonly referred to as \emph{privacy amplification by aggregation}, shows how $\epsilon$ decreases as $n$ increases. This phenomena was originally observed by \citep{ErlingssonFMRTT19} and \citep{CheuSUZZ19}, although the version we state here is due to \cite{Feldman:2022}.

\begin{thm}\label{amplificationbyaggregation}
Suppose $\mathcal{A}:\mathcal{D}^n\to\mathcal{Z}$ is an algorithm that can be written as $\mathcal{A}(d^{(1)}, \cdots, d^{(n)})=\phi(\texttt{Aggregator}(f(d^{(1)}, \cdots, f(d^{n)}))$ where $f:\mathcal{D}\to\mathcal{Z}$ is a randomized function that transforms that data, $\texttt{Aggregator}$ is an aggregation protocol, and $\phi:\mathcal{Y}^n\to\mathcal{Z}$ is some post-processing of the aggregated report. If $f$ is an $\epsilon_0$-DP local randomizer in the replacement model, then for any $\delta\in[0,1]$ such that $\epsilon_0\le\ln(\frac{n}{8\ln(2/\delta)}-1)$, $\mathcal{A}$ is $(\epsilon,\delta)$-DP in the aggregate model where
\begin{equation}\label{shufflebound}
\epsilon \le \log\left(1+(e^{\epsilon_0}-1)\left(\frac{4\sqrt{2\log(4/\delta)}}{\sqrt{(e^{\epsilon_0}+1)n}}+\frac{4}{n}\right)\right).
\end{equation}
\end{thm}

Note that Theorem~\ref{amplificationbyaggregation} immediately implies a corresponding theorem for the case where the functions $f$ are $\epsilon_0$-DP local randomizers in the deletion model by replacing $\epsilon_0$ with $2\epsilon_0$ in eqn~\eqref{shufflebound}.
This upper bound on $\epsilon$ is approximately $O\left(\epsilon_0\frac{\sqrt{\log(1/\delta)}}{\sqrt{n}}\right)$ when $\epsilon<1$ and $O\left(\frac{\sqrt{e^{\epsilon_0}\log(1/\delta)}}{\sqrt{n}}\right)$ when $\epsilon\ge1$, where $\epsilon_0$ is the local privacy parameter in the replacement model. Numerical computations of the privacy amplification can obtain tighter bounds on the privacy of the output of the aggregation protocol. In the system described in this paper, we propose computing the privacy amplification numerically using the technique presented in \cite[Theorem 3.1]{Feldman:2022}. This code is available at \url{https://github.com/apple/ml-shuffling-amplification}. In Figure~\ref{varyingnamplification} we show how the privacy of the output of the aggregation protocol changes as a function of the cohort size for two given local privacy guarantees $\epsilon_0=3$ and $\epsilon_0=6$. For example, we can see that if each user sends their data using a $3$-DP local randomizer, then the privacy of the output of the aggregation protocol is at most $(1,10^{-6})$-DP in the aggregate model once $n>1,000$ and decreases quickly as the cohort size grows.

\begin{figure}
\begin{center}
\includegraphics[scale=0.5]{Privacy_amp.png}
\end{center}
\caption{Cohort aggregate privacy guarantees ($(\epsilon, 10^{-6})$) as a function of cohort size ($n$) for $\epsilon_0=3$ and $\epsilon_0=6$.}
\label{varyingnamplification}
\end{figure}

We remark that one can also measure the privacy amplification in terms of an alternative definition of privacy known as R\'enyi differential privacy~\cite{Mironov2017RnyiDP}. Using R\'enyi differential privacy will typically allow us to get stronger bounds for the privacy guarantee of composing multiple differentially private algorithms. We refer the reader to~\cite{Feldman:2022, Kim:2021} for details, and for simplicity, assume here that we compose $(\epsilon,\delta)$-DP guarantees using the advanced composition theorem~\cite{DRV}.

Since we want the output of the aggregation protocol to achieve the required level of privacy regardless of the cohort size, we suggest using an aggregation protocol that has the additional functionality that given a minimum cohort size $m$, the protocol will only release the aggregate if the actual cohort size is greater than $m$. If too few users participate in answering a query, the aggregation protocol does not output anything.  Given a local privacy parameter $\epsilon_0$, and a desired privacy guarantee on the output of the aggregation protocol $\epsilon$, we can compute the minimum cohort size $m$ for which the privacy guarantee would hold if $m$ users were to participate. The minimum cohort is communicated from the device to the aggregation protocol.
We will refer to the privacy guarantee of the output of the aggregation protocol with this additional functionality as the \emph{cohort-aggregate privacy guarantee}.

Our privacy analysis of the aggregate model via Theorem~\ref{amplificationbyaggregation} implicitly relies on each user gaining privacy from the noise added to the aggregate by all the other users. While we assumed that all clients are honest, this can be easily relaxed to assuming that at least a constant fraction of clients are honest and applying the privacy amplification by aggregation to the subset of honest clients.
An alternative approach to reducing the trust in user's behaving honestly would be to equip the aggregation protocol with the ability to add the noise needed for privacy.
\section{Related Work}

Differential privacy \citep{DMNS06} began in the cryptography and theoretical computer science communities over a decade ago and has become the privacy benchmark across a variety of fields \cite{DR14}.  In this work, we will consider the local model of differential privacy \cite{Kasiviswanathan:2008}, as well as the aggregate model of differential privacy, which is closely related to the recently introduced shuffle model \cite{ErlingssonFMRTT19, CheuSUZZ19}.

There has been considerable work on differential privacy in the local model, first introduced in \cite{Kasiviswanathan:2008}.
This work includes obtaining tight bounds for statistical estimators \citep{duchi2013local}, learning problems \citep{Kasiviswanathan:2008}, and studying frequency estimation \citep{BS15,erlingsson2014rappor,FPE16}. The main frequency estimation algorithm of interest in this paper, private one-hot encoding, was proposed and used in RAPPOR \cite{erlingsson2014rappor}. Several follow-up works have reduced the communication, time and space complexity of private frequency estimation, or the problem of privately identifying heavy hitters, while maintaining accuracy~\cite{BS15, MS06, hsu2012distributed, pmlr-v139-feldman21a}. While we will not discuss these techniques in this paper, they are certainly of interest in a system like the one we describe.

The idea of using an aggregation protocol as a subroutine goes back to the early days of differential privacy~\cite{ODO}. It has been proposed for smart meter data privacy in~\cite{Aces:2011}. As it forms the central primitive in our proposed system, we name this model Aggregate Differential Privacy. A closely related model is the shuffle model, which was first introduced in two concurrent works
\citep{ErlingssonFMRTT19,CheuSUZZ19}. These works demonstrated that shuffling data sent from users using locally differentially private randomisers can provably amplify DP guarantees. Since then a number of works have studied privacy amplification by shuffling and the model augmented with a shuffler more generally (e.g.~\citep{Balle:2019,Ghazi:2019,GhaziPV19,Balle:2020,Balle2020,GMPV20,cheu2020limits,CheuSUZZ19,BalcerCheu,WangXDZHHLJ20,Erlingsson2020,FeldmanMT:2020,girgis2020shuffled}). This amplification by shuffling can also be used to analyze models augmented with an aggregation protocol such as PRIO \citep{Prio}
(since the sum of real values provides even less information than shuffled values). In particular, privacy amplification by shuffling was used in Apple’s and Google’s Exposure Notification Privacy-preserving Analytics~\citep{ENPA:2021}.

The power of interaction in locally differentially private algorithms has been well documented in the literature \cite{Joseph:2019, 10.5555/3454287.3455630, Dagan:2020} by works showing that the ability to adaptively query users results in strictly more accurate algorithms. Recent work has also explored the power of interactivity in the setting of aggregate or shuffle differential privacy. Bagdasaryan et. al \citep{Bagdasaryan:2022} propose using an interactive algorithm similar to the one described in the introduction to learn location heatmaps under aggregate differential privacy. They demonstrate the improvement of this algorithm over standard non-interactive approaches.

There have been a few experimentaly systems and practical deployments of differentially private systems. Unlike our system, most of these employ central differential privacy, including the PSI ($\Psi$) system \cite{Psi}, OpenDP \cite{OpenDP}, Census Bureau system \cite{Census2, census2020}, Airavat \cite{RSKSW}, PINQ \cite{PINQ}, and GUPT \cite{MTSSC12}. In the local setting, RAPPOR deploys differential privacy on the Chrome web browser \cite{erlingsson2014rappor,FPE16}.

\section{System Overview}\label{systemsoverview}

Our proposed architecture consists of device- and server- side infrastructure. We will use the term \emph{query} to refer to a single data collection event on device,
and \emph{analysis} to refer to a collection of queries performed for a given task.
At a high level,
the device stores information about the kind of queries that are allowed in the analysis as well as their privacy budgets. This information is hard-coded as part of the device OS, and encodes the immutable parts of the policy that ships with the OS. The data, as it is generated, get saved in a secure data storage. The server infrastructure allows an analyst to send interactive queries to devices, which are then verified (that they are allowed queries) on device. The response, with noise added, gets sent to an aggregation protocol, which allows the analyst to see the aggregate results of the query. We provide details of various parts of the system in this section.

Our proposed design allows for interactive queries. However, the queries are constrained to belong a certain class of queries and a description of this query class gets stored on device. This description includes the set of attributes that the analysis is allowed to access, as well as the kinds of queries that are permitted. We defer more details about the query class constraints and verification to Section~\ref{queryverification}.

 In addition, the answers to these queries are governed by a set of privacy constraints.
We impose global constraints for the whole analysis as well as per-data field privacy constraints. Section~\ref{sec:privacy-budget} has further details on the privacy constraints.

\begin{figure}
	\begin{center}
			\includegraphics[scale=0.15]{overall-architecture_new}
	\caption{Proposed system architecture. Histogram query results are protected by differential privacy constraints. Reports from multiple devices are aggregated using an aggregation protocol so that the server only sees the aggregate report from a cohort of a pre-specified minimum size.
	}
		\label{fig:system}
	\end{center}
\end{figure}

                \lstset{language={},literate={``}{\textquotedblleft}1, xleftmargin=.3in, numberstyle=\tiny,xrightmargin=-.1in}

Prior to being queried, an on-device framework should be used to provide secure storage for the data. This framework should be optimized for fast sequential access to user data, since this data is generated by user actions we sometimes call these data generation events simply ``events". Each event is donated to an approved data stream with unique identifier, and fixed schema.
For example, when a user types a phrase using their keyboard,  an event would be added to the corresponding ``keyboard" stream.

An access control mechanism can be used to ensure that this data store is readable only by queries which are approved to access this data. Further, a retention policy assures that each event is stored on the device for a limited, approved period of time.
Figure \ref{fig:device-system} contains an example of a potential on-device architecture.

\begin{figure}[H]
	\begin{center}
			\includegraphics[scale=0.15]{on-device-architecture_new}
	\caption{On device architecture example. The query and data are processed in the sandbox environment, then passed to the DP library, which contains algorithms carefully vetted to satisfy differential privacy.}
		\label{fig:device-system}
	\end{center}
\end{figure}

\subsection{Device Enrollment}\label{device_enrollment}
In order to run a query from the server, a \emph{recipe} is deployed to all opted-in devices. A recipe includes a query which is executed on the data stream, and a schema to encode the query output to a one hot vector.
For example, for the algorithm outlined in the introduction, for interactively learning n-grams of known words, one query in this analysis would ask users to send a randomly chosen 3-gram, among those they have typed, that starts with a member of a small list of popular 2-grams.\footnote{If the user does not have any 2-grams that match the requirements, then they should send a random 3-gram as sending nothing can itself be disclosive. Further, it is sufficient to send a hash of the list of popular 2-grams to the devices.}
In order to enable learning popular 3-grams, we send the list of popular 2-grams in a prefix tree data structure, as well as set of known tokens for completing this prefix tree. If a token is not in this list, it will be tokenized to a special token \emph{OOV} which denotes an \emph{Out of Vocabulary} token.

In this example, the recipe sent from the server needs to contain several pieces of information. Firstly, the recipe should contain the query itself, and the requested local and cohort aggregate privacy budgets for this query. In addition, a scheme to encode the query output as a one-hot vector should be included. This ensures the query output is an appropriately formed input for the types of local randomizers that arise in differentially private histogram estimation. This scheme is often defined by the tuple of features we intend to learn, and a bucketing rule for each feature. For an example, see Appendix~\ref{appendix:deviceenrollment}.

If any data fields accessed by the query are determined to be non-sensitive, then these can also be specified in the recipe. For example, when learning n-grams of known words, the locale (device language, eg. american english) may be deemed non-sensitive. The device should keep a list of approved non-sensitive data fields hard-coded as part of the device OS. The recipe may also contain meta information such as a recipe identifier or version number, which can be attached to the privatized query response when being sent to the server.

\subsection{Query Class Verification}\label{queryverification}

As mentioned earlier, the analysis is restricted to only ask queries that lie within the approved query class. In the non-adaptive setting, this query class may be a singleton set (a set that contains only one element), and the architecture mainly serves to co-ordinate from the server when to run the query. More generally, a broader set of queries may be allowed. Any query class should be supported by a query class verifier; a piece of code that runs on device and can verify that the query given in a recipe is a member of the query class.
When the number of allowed queries is small, this can be achieved by simply listing the set of allowable queries.

As an example of a broader query class, suppose that the query class is specified by an allowed set of data fields, and any query that only accesses those data fields is a permitted query. One could verify that a query belonged to this query class by configuring the underlying database management system (DBMS) to restrict access to the allowed list of fields. Upon execution of the query, the DBMS will return an error indicating that the query was denied if a non-allowed field is referenced.

\subsection{Privacy Budget Verification}\label{sec:privacy-budget}
All analyses run on the system we propose satisfy strong differential privacy guarantees.
Each analysis must satisfy a cohort aggregate privacy budget that is shared over all the queries contained in that analysis. Recall that the cohort aggregate privacy budget is the privacy guarantee of the output of an aggregation protocol with the additional functionality that it can enforce a minimum cohort size.  Additionally, each query must satisfy a specified local privacy budget.
Since queries within an allowable query class may access data types with varying sensitivity, we also employ a more fine-grained differential privacy budget for individual queries. Each data field is assigned an allowed local privacy budget, an allowed cohort aggregate privacy budget and an allowed number of types that data type may be accessed per analysis. Any query must satisfy the most stringent privacy conditions of any data field that is accessed by that query.

Table~\ref{ondevicebudgetaccountant} summarizes hypothetical parameter settings for the proposed on-device budget accountant that tracks and limits the differential privacy parameter for each data field, for queries related to the use of the keyboard. In this example, a team interested in improving next word prediction may request access to $n$-grams typed with the keyboard, as well as metrics related to the performance of the currently deployed keyboard model like model perplexity. More sensitive fields like bucketed age may be useful for assessing how performance varies among subpopulations. By using this fine grained privacy budget account, we can ensure that not only is the total differential privacy parameter bounded, but particularly sensitive information is further protected.
When a query is sent to the device, a series of privacy budget checks ensure that the device has enough remaining differential privacy budget to run the query with the desired differential privacy parameters:

\begin{itemize}
\item \textbf{Check 1:}  Check that the analysis has enough differential privacy budget remaining and has not exceeded its allowed number of queries per Table~\ref{usecaseprivacybudgets}. Formally, $\epsilon+\epsilon_{\rm Used}\le \epsilon_{\rm Allowed}$ and  $k_{\rm Used}+1\le k_{\rm Allowed}$.
\item \textbf{Check 2:} Check that data fields used in the query have enough differential privacy budget remaining and have not exceeded their allowed number of queries per Table~\ref{datatypeprivacybudgets}. Formally, for every data field accessed by the query, $\epsilon_0\le \epsilon_{\rm Allowed, Data\; field}^{\rm local}$, $\epsilon+\epsilon_{\rm Used, Data\; field}\le \epsilon_{\rm Allowed, Data\; field}$ and $k_{\rm Used, Data\; field}+1\le k_{\rm Allowed, Data\; field}$. This check requires a complete and accurate list of data fields that are accessed by the query.
\item \textbf{Check 3:} The cohort-aggregate differential privacy guarantee $\epsilon$ will be achieved by the aggregation of at least $m$ $\epsilon_0$-DP local reports.
\end{itemize}

If all checks are passed, the device runs the query. The differential privacy budget accountant is updated to reflect the privacy loss incurred by running the query. Formally, $\epsilon_{\rm Used} \mapsto \epsilon_{\rm Used}+\epsilon$, $k_{\rm Used} \mapsto k_{\rm Used}+1$, and for every data field accessed by the query $\epsilon_{\rm Used, Data\; field} \mapsto \epsilon_{\rm Used, Data\; field}+\epsilon$, $k_{\rm Used, Data\; field} \mapsto k_{\rm Used, Data\; field}+1$. If any of the checks fail, the device does not run the query. While we have described the privacy checks as using the basic composition theorem, these can naturally be adapted to the use of advanced composition theorem, or other privacy accounting methods.

While we do not formally track the local privacy budgets, the limit on the allowed number of reports imposes an upper bound of $\epsilon_{\rm Allowed}^{\rm local} \times k_{\rm Allowed}$ on the local privacy loss for the analysis, and a potentially stronger upper bound of $\epsilon_{\rm Allowed, Data\; field}^{\rm local} \times k_{\rm Allowed, Data\; field}$ on the local privacy loss per data field.

\begin{center}
\begin{table}
\begin{subtable}{1\textwidth}
\begin{tabular}{  | L{3.5cm}| L{3.5cm} | L{3.5cm} | L{3.5cm} | }
  \hline
 \textbf{\small Allowed Cohort Aggregate Privacy Budget $\epsilon_{\rm Allowed, Analysis}$} & \textbf{\small Used Cohort Aggregate Privacy Budget $\epsilon_{\rm Used, Analysis}$} & \textbf{\small Allowed Number of Reports $k_{\rm Allowed, Analysis}$} & \textbf{\small Number of Reports Used $k_{\rm Used, Analysis}$} \\
  \hline\hline
0.5 & 0 & 1 & 0\\
  \hline
\end{tabular}
\caption{Example of Maximum Privacy Budgets per Analysis allocations. Approved analyses must abide by their own approved privacy budgets. These budgets are adjusted to suit the sensitivity of the data used. The number of local reports that an analysis can receive from a given device is also limited.}\label{usecaseprivacybudgets}
\end{subtable}
\begin{subtable}{1\textwidth}
\begin{tabular}{ | L{1.7cm} | L{2.5cm}| L{2.5cm} | L{2.5cm} | L{2.5cm} | L{2.5cm} |}
  \hline
\textbf{\small Data Field} & \textbf{\small Allowed Local Privacy Budget $\epsilon_{\rm Allowed, Data\; field}^{\rm local}$} & \textbf{\small Allowed Cohort Aggregate Privacy Budget $\epsilon_{\rm Allowed, Data\; field}$} & \textbf{\small Used Cohort Aggregate Privacy Budget $\epsilon_{\rm Used, Data\; field}$} & \textbf{\small Allowed Number of Reports $k_{\rm Allowed, Data\; field}$} & \textbf{\small Number of Reports Used $k_{\rm Used, Data\; field}$} \\
  \hline\hline
  $n$-gram & 5 & 1 & 0 & 1 & 0\\
  \hline
  Bucketed age & 2 & 0.3 & 0 & 1 & 0 \\
  \hline
  Model perplexity & 8 & 1 & 0 & 1 & 0\\
  \hline
\end{tabular}
\caption{Example of Maximum Privacy Budgets per Data Field allocations. For each data field we bound the total privacy loss of any query that access that data field. These budgets are adjusted to suit the sensitivity of the data field. }\label{datatypeprivacybudgets}
\end{subtable}

\caption{ Example of a potential on-device differential privacy budget accountant for keyboard analysis.}\label{ondevicebudgetaccountant}
\end{table}
\end{center}

\subsection{Privatization}
Once it has been established that that there is enough privacy budget remaining to run the query, the device uses a local randomizer to respond to the query. We will describe one possible randomizer choice, private one-hot encoding (OHE), in more detail in the appendix. Briefly, private OHE involves each user representing their data as a one-hot encoded binary array, then flipping each coordinate of this array independently with some pre-specified probability. After local privatization, the randomizer output is sent to the aggregation protocol. For instance, if the aggregation is based on PRIO~\cite{Prio}, the privatized record would be secret-shared into shares that would be encrypted using the public keys of non-colluding servers. Finally, the query, privatized record, and any function of the privatized record that leaves the device (e.g. shares of the privatized record) can be logged to the device for auditability.

\subsubsection{Aggregation}
In order to build a system with strong privacy guarantees, the aggregation protocol should guarantee that it does not reveal anything about the local reports except their sum. However, our overall architecture is oblivious to the particular aggregation protocol. One option is to use a multiple server architecture as in PRIO~\cite{Prio}. Such a system with two servers has been used in earlier systems~\cite{ENPA:2021, enpatalk, firefox}. Each device secret shares their local report into two additive shares, which are sent to two non-colluding servers.
Each server aggregates the shares it receives within a time window, and conditioned on the batch size being sufficiently large, publishes its aggregate to a third server. Individual shares are only stored for this time window and are deleted right after the batch aggregation job finishes. The third server aggregates all these results, and returns the result to the analyst. By performing the aggregation in this manner, we ensure that no party has access to any individual local report.


\section{Introduction}\label{Sec:Intro}
The general theory of the van der Waals force was developed by Lifshits in Refs.
\refcite{Lif56,LifPit80} in the framework of  statistical physics. In the case
of
interaction between particle and plate it is commonly referred to as the
Casimir-Polder force.\cite{CasPol48} For small distance the potential of
interaction is proportional to inverse third degree of distance from the plate.
For large distance the retardation of the interaction is taken into account and
the potential falls down as fourth degree of distance. The last achievements in
Casimir effect have been discussed in great depth in books and
reviews.\cite{Mil01}\cdash\cite{KliMohMos09}

The van der Waals force is very important for interaction of graphene
(graphite layers) with
bodies\cite{BogOveHylLunBruJen00}\cdash\cite{BorFiaGitVas09} and
microparticles.\cite{BonLam05}\cdash\cite{ChuFedKliYur10}
An understanding of the mechanisms of molecule-nanostructure interaction is of
importance for the problem of hydrogen storage in carbon
nanostructures.\cite{DilJonBekKiaBetHeb97} The microscopic mechanisms underlying the
absorption phenomenon remain unclear (see, for example
Ref.~\refcite{Nec06}).

In the present paper we use model of the fullerene in terms of the two
dimensional free electron gas\cite{Fet73} which is usually called as
hydrodynamical model.  This model was applied and developed for the molecule
$C_{60}$ in Ref.~\refcite{Bar04}, for flat plasma sheet  in Ref.
\refcite{BorPirNes05} and for spherical plasma surface in Ref.
\refcite{BorKhu08}. In
the framework of this model the conductive surface is considered as infinitely
thin shell with the specific wave number $\Omega = 4\pi n e^2/mc^2$, where $n$
is surface density of electrons and $m$ is the electron mass. Since the surface
is infinitely thin, the information about the properties
of the surface is encoded in the boundary conditions on the conductive surface
which are different for TE and TM modes. It was
shown\cite{BorKhu08} that
the energy of the vacuum electromagnetic fluctuations for surface shaped as
sphere has a maximum for radius of sphere approximately equal to the specific
wavelength of the model $\lambda_\Omega = 2\pi/\Omega$. What this means is the
Casimir force tries to enlarge sphere with radius larger then $\lambda_\Omega$
and it tries to reduce the sphere with radius larger then $\lambda_\Omega$. The
Boyer result\cite{Boy68} is recovered in the limit $\Omega \to \infty$.

At the same time it is well known\cite{GeiNov07} that the energy of electrons
in graphene has linear frequency dependence whereas in framework of the
hydrodynamic model the energy of electrons is quadratic in the frequency. There
is also another point that the electrons in the graphene have zero or very small
effective mass. To describe correctly these unusual properties of electrons in
graphene the Dirac fermion model was suggested in Ref. \refcite{Sem84}. The
electrons in this model are described by $(2+1)D$ Dirac action with
characteristic propagation velocity as Fermi velocity $v_F \approx c/300$ and
very small mass gap $m < 0.1 eV$. This model was applied for calculation of
Casimir interaction energy between graphene plate and perfect conductor
plane\cite{BorFiaGitVas09} and recently
for Casimir-Polder interaction energy between graphene and H, He$^*$ and Na
atoms.\cite{ChuFedKliYur10}

It was shown that the Casimir energy for large distance between graphene plate
and perfect conductor plane\cite{BorFiaGitVas09} is decreasing by one power of
the separation a faster than for ideal conductors, that is as $(ma)^{-4}$. If
the mass of gap is zero at the beginning of calculations, $m=0$, they obtained
standard dependence $a^{-3}$. For the case  of Casimir-Polder interaction
energy between graphene and atoms\cite{ChuFedKliYur10} the hydrodynamic and
the Dirac models give qualitatively different results. For the large separation
the energy decreases with separation as $a^{-4}$ which is a typical behavior of
the atom-plate interaction at relativistic separations, but the coefficients are
different. In the case of H, He$^*$ and Na atoms, the hydrodynamic model gives
$\approx 5$ times larger coefficient than the Dirac model. There is also
interesting observation about mass gap parameter: the energy does not depend on
the parameter for $m < 10^{-3/2} eV$ and therefore the limit $m\to 0$ is
satisfied.

In the present paper the hydrodynamical model of fullerene is adopted -- the
infinitely thin sphere with radius $R$ in vacuum and finite conductivity. To
obtain the van der Waals interaction energy between an atom and this sphere we
use the following approach which is due to Lifshits (see Refs.
\refcite{Lif56,LifPit80,BorGeyKliMos06,BlaKliMos07}). We put the sphere inside
the spherical vacuum cavity with radius $L = R+d$ which is inside the
dielectric media with coefficients $\mu, \varepsilon$. Then we find the
zero-point energy of this system by using the zeta-function regularization
approach, and take the limit of the rared media with $\varepsilon = 1+ 4\pi N
\alpha + O(N^2)$, where $N\to 0 $
is the volume density of the atoms and $\alpha$ is the polarizability of the
unit atom. The interaction energy per unit atom which is situated $d$ from the
sphere is found by simple formula
\begin{equation*}
E_a(s) = -\lim_{N\to 0}\frac{\partial_d E(s)}{4\pi N (R+d)^2},
\end{equation*}
where $E(s)$ is the zeta-regularized energy with regularization parameter $s$.

\section{Matching Conditions For Two Cylinders}\label{Sec:Maxwell}

Let us consider a conductive infinitely thin sphere with radius $R$ in vacuum
spherical cavity with radius $L=R+d$ which is inside the dielectric media with
parameters $\mu, \varepsilon$. We have two concentric spheres and we should
consider the boundary conditions on two spherical boundaries.

Assuming the spherical symmetry, the electromagnetic field is factorized for two
independent polarizations usually called as \textsf{\scriptsize TE}  and \textsf{\scriptsize TM}  modes. The angular
dependence is described by spherical functions $Y_{lm}$ and radial function $f$
subjects for radial equation
\begin{equation}
f'' + \frac 2r f' + \left( \frac{\omega^2}{c^2}\varepsilon \mu  -
\frac{l(l+1)}{r^2}\right)f = 0.
\end{equation}
The two independent solutions of this equation are the spherical Bessel
functions $j_l(z) = \sqrt{\pi/2z} J_{l+1/2}(z), \ y_l(z) = \sqrt{\pi/2z}
Y_{l+1/2}(z)$, where $z = r \omega \sqrt{\varepsilon\mu}/c$.

At the boundary, $L=R+d$, the matching conditions read
\begin{subequations}\label{matching_cond}
\begin{eqnarray}
 \mathbf{n} \cdot [\mathbf{B}_2 - \mathbf{B}_1]_L &=& 0, \ \mathbf{n} \cdot
[\mathbf{D}_2 - \mathbf{D}_1]_L =0,\allowdisplaybreaks \\
 \mathbf{n} \times [\mathbf{H}_2 - \mathbf{H}_1]_L &=& 0, \ \mathbf{n} \times
[\mathbf{E}_2 - \mathbf{E}_1]_L =0,
\end{eqnarray}
\end{subequations}
where $\mathbf{n} = \mathbf{r}/r$ is an unit normal to the sphere. We have to
take into account also that $k=\omega /c$ inside the sphere $r=L$ and $k= \omega
\sqrt{\mu\varepsilon}/c$ outside the sphere. The square brackets above denote
the coincidence limit on the boundary $r=L$.

The electromagnetic fields given infinitely thin conductive surface $\Sigma$
in vacuum was considered by Fetter.\cite{Fet73} The applications of
this model for vacuum fluctuations of field see in Refs.
\refcite{Bar04}--\refcite{BorKhu08}. The  boundary conditions on the
sphere with $r=R$ read
\begin{subequations} \label{cond2}
\begin{eqnarray}
\mathbf{n}\cdot [\mathbf{H}_{2} - \mathbf{H}_{1}]_R &=& 0,\ \mathbf{n}\cdot
[\mathbf{E}_{2} - \mathbf{E}_{1}]_R = \frac{\Omega }{k^2} \nabla_{|\!|} \cdot
\mathbf{E}_{|\!|}, \\
\mathbf{n} \times [\mathbf{H}_2 - \mathbf{H}_1]_R &=& -\frac{i\Omega }{k }
\mathbf{n} \times \mathbf{E}_{|\!|},\ \mathbf{n} \times [\mathbf{E}_2 -
\mathbf{E}_1]_R = 0,
\end{eqnarray}
\end{subequations}
where $k=\omega /c$ and $\Omega = 4\pi n e^2/mc^2$ is a specific wave number on
the sphere. Because of the fact that the sphere is infinitely thin we may
consider the Maxwell equations in vacuum with zero right hand side
and all information about sphere will be encoded in boundary conditions
(\ref{cond2}). An interesting treatment of this boundary condition is in Ref.
\refcite{Vas09}.

\section{The Solution of the Matching Conditions}\label{Sec:Matching}

Let us represent the radial function in the following way
\begin{equation}
f = \left\{
 \begin{array}{lll} f_{in}&=a_{in} j_l(kr),& r<R \\
               f_{out}&=a_{out} j_l(kr) + b_{out} y_{l}(kr),&R<r<L \\
               f_{\varepsilon}&=a_{\varepsilon} h^{(1)}_l(kr),&r>L
 \end{array}\right.
\end{equation}
where $j_l,y_l$ and $h_l^{(1)}$ are the spherical Bessel functions and $k=\omega
/c$ inside the sphere, $r < L$ and $k= \omega \sqrt{\mu\varepsilon}/c$ outside
the sphere for $r > L$.

In this case the matching conditions (\ref{matching_cond}) and (\ref{cond2}) in
manifest form read
\begin{eqnarray}
 [rf_{out} - rf_{in}]_{R} &=&0,\nonumber\allowdisplaybreaks \\{}
[(rf_{out})'_r -  (rf_{in})'_r - \Omega (rf_{in})]_R &=&0,\nonumber\allowdisplaybreaks \\{}
[rf_{out} - rf_{\varepsilon}]_{L} &=&0,\allowdisplaybreaks \\{}
[(rf_{out})'_r -  \frac{1}{\mu}(rf_{\varepsilon})'_r]_L &=&0, \nonumber
\end{eqnarray}
for \textsf{\scriptsize TE}  mode, and
\begin{eqnarray}
 [(rf_{out})'_r - (rf_{in})'_r]_{R} &=&0,\nonumber\allowdisplaybreaks \\{}
[(rf_{out}) -  (rf_{in}) + \frac{\Omega}{k^2} (rf_{in})'_r]_R
&=&0,\nonumber\allowdisplaybreaks \\{}
[rf_{out} -  \frac{1}{\mu}rf_{\varepsilon}]_L&=&0,\allowdisplaybreaks \\{}
[(rf_{out})'_r -  \frac{1}{\mu\varepsilon}(rf_{\varepsilon})'_r]_L
&=&0,\nonumber
\end{eqnarray}
for \textsf{\scriptsize TM}  mode. The solutions of these equations exist if and only if the
following equations are satisfied ($\mu=1$)
\begin{subequations}
\begin{eqnarray}
 \Sigma_{\textsf{\scriptsize TE} } &=& H'(z_\varepsilon) \Psi_{\textsf{\scriptsize TE} } -
\frac{1}{\sqrt{\varepsilon}} H(z_\varepsilon) \Psi'_{\textsf{\scriptsize TE} }=0 ,\allowdisplaybreaks \\
 \Sigma_{\textsf{\scriptsize TM} } &=& z^2\left\{ H(z_\varepsilon) \Psi'_{TM} -
\frac{1}{\sqrt{\varepsilon}} H'(z_\varepsilon) \Psi_{\textsf{\scriptsize TM} }\right\}=0 ,
\end{eqnarray}
\end{subequations}
where $z_\varepsilon = z \sqrt{\mu\varepsilon}$, $z = kL = \omega L/c$; the
prime is derivative with respect the argument, and
\begin{subequations}
\begin{eqnarray}
 \Psi_{\textsf{\scriptsize TE} }(z) &=& J(z) + \frac{\Omega}{k} J(x) [J(x) Y(z) - J(z) Y(x)],\allowdisplaybreaks \\
 \Psi_{\textsf{\scriptsize TM} }(z) &=& J(z) + \frac{\Omega}{k} J'(x) [J'(x) Y(z) - J(z) Y'(x)].
\end{eqnarray}
\end{subequations}
Here $J(x) = xj_l(x),\ Y(x) = xy_l(x),\ H(x) = xh^{(1)}_l(x)$ are the
Riccati-Bessel functions, and $x=kR$. For $\varepsilon =1$, the result obtained
in the Ref. \refcite{BorKhu08} is
recovered
\begin{subequations}
\begin{eqnarray}
 \Sigma_{\textsf{\scriptsize TE} } &=& i\left\{1 - \frac{\Omega}{ik} J(x)H(x)
\right\}=if_{\textsf{\scriptsize TE} }(k),\allowdisplaybreaks \\
 \Sigma_{\textsf{\scriptsize TM} } &=& -iz^2 \left\{1 - \frac{\Omega}{ik} J'(x)H'(x) \right\} = -
iz^2f_{\textsf{\scriptsize TM} }(k),
\end{eqnarray}
\end{subequations}
for real value of $k$.

On the imaginary axis $k\to i k$ we obtain
\begin{subequations} \label{sigmas}
\begin{eqnarray}
 \Sigma_{\textsf{\scriptsize TE} } &=& \frac{1}{\sqrt{\varepsilon}} e_l(z_\varepsilon)
\Phi'_{\textsf{\scriptsize TE} } - e'_l(z_\varepsilon) \Phi_{\textsf{\scriptsize TE} }  ,\allowdisplaybreaks \\
 \Sigma_{\textsf{\scriptsize TM} } &=& z^2\left\{e_l(z_\varepsilon) \Phi'_{\textsf{\scriptsize TM} } -
\frac{1}{\sqrt{\varepsilon}} e_l'(z_\varepsilon) \Phi_{\textsf{\scriptsize TM} }\right\},\allowdisplaybreaks \\
 \Phi_{\textsf{\scriptsize TE} } &=& s_l(z) + \frac{Q}{x} s_l(x) [s_l(z) e_l(x) - s_l(x)
e_l(z)],\allowdisplaybreaks \\
 \Phi_{\textsf{\scriptsize TM} } &=& s_l(z) - \frac{Q}{x} s'_l(x) [s_l(z) e'_l(x) - s'_l(x) e_l(z)],
\end{eqnarray}
\end{subequations}
where $Q=\Omega R$, $z = kL,\ z_\varepsilon = z \sqrt{\varepsilon},\ x = kR$,
$\varepsilon = \varepsilon (i\omega)$ and
\begin{equation}
 s_l(x) = \sqrt{\frac{\pi x}{2}} I_{l+1/2}(x), \ e_l(x) = \sqrt{\frac{2 x}{\pi}}
K_{l+1/2}(x)
\end{equation}
are the Riccatti-Bessel spherical functions of the second kind. For $\varepsilon
= 1$ we obtain
\begin{equation}
 \Sigma_{\textsf{\scriptsize TE} } = f_{\textsf{\scriptsize TE} }(ik), \ \Sigma_{\textsf{\scriptsize TM} } = z^2f_{\textsf{\scriptsize TM} }(ik)
\end{equation}
in accordance with Ref. \refcite{BorKhu08}.

\section{The Energy}\label{Sec:Energy}
Within the limits of approach,\cite{BorEliKirLes97} the
expressions for \textsf{\scriptsize TE}  and \textsf{\scriptsize TM}  contributions in regularized  zero-point energy read
($\omega=kc,\nu =  l + 1/2$)
\begin{eqnarray}
E^{\textsf{\scriptsize TE} }(s) &=& -\frac{\hbar c\cos\pi s}{\pi} \mu^{2s}\sum_{l=1}^\infty \nu
\int_0^\infty dk k^{1-2s} \partial_k \ln \Sigma_{\textsf{\scriptsize TE} },\allowdisplaybreaks \\
E^{\textsf{\scriptsize TM} }(s) &=& -\frac{\hbar c\cos\pi s}{\pi} \mu^{2s} \sum_{l=1}^\infty \nu
\int_0^\infty dk k^{1-2s} \partial_k \ln  \Sigma_{\textsf{\scriptsize TM} },
\end{eqnarray}
where the integrand functions are given by Eqs. (\ref{sigmas}).

Let us consider now the rared media with $\varepsilon (i\omega) = 1 + 4\pi N
\alpha (i\omega) + O(N^2)$, where $\alpha$ is polarizability of the atom and the
density of the dielectric matter $N\to 0$. In this case the Casimir energy
$E(s)$ is expressed in terms the energy per unit atom $E_a(s)$ by relation
\begin{equation}
E(s) = N \int_d^\infty E_a(s) 4\pi (R+r)^2 dr + O(N^2).
\end{equation}
From this expression it follows that
\begin{equation}
E_a(s) = -\lim_{N\to 0}\frac{\partial_d E(s)}{4\pi N (R+d)^2}.
\end{equation}
By virtue of the fact that the Casimir energy is zero for an atom in vacuum
($Q = 0$) without boundaries, we define the interaction energy by the following
relation
\begin{equation}
E_{\Omega} = \lim_{s\to 0} \{E_a(s) -  \lim_{\Omega \to 0} E_a(s)\}.
\end{equation}
With this definition we integrate by part over $k$ and arrive with the final
formula ($x=kR,\ z=kL,\ L = R + d$)
\begin{equation}
E_\Omega = -\frac{\hbar c\Omega}{\pi L^2}\! \sum_{l=1}^\infty \nu \!\!\!
\int\limits_0^\infty\!\! dk \alpha (i\omega) \left\{ \frac{s_l^2(x)
e_l^2(z)}{f_{\textsf{\scriptsize TE} }(ik)} + \frac{{s'}_l^2(x) {e'}_l^2(z) + {s'}_l^2(x){e}_l^2(z)
\frac{\nu^2 - \frac{1}{4}}{z^2}}{f_{\textsf{\scriptsize TM} }(ik)} \right\},\label{Fcp}
\end{equation}
where the Jost functions on the imaginary axes read
\begin{eqnarray}
f_{\textsf{\scriptsize TE} }(ik) &=& 1 + \frac{\Omega}{k} s_l(x)e_l(x) ,\\
f_{\textsf{\scriptsize TM} }(ik) &=& 1 - \frac{\Omega}{k} s'_l(x)e'_l(x).
\end{eqnarray}

To perform computations one needs an expression for the atomic dynamic
polarizabilities of hydrogen. It was shown\cite{BlaKliMos05} that
the polarizabilities can be represented with sufficient precision in the
framework of the single-oscillator model
\begin{equation}
 \alpha (i\omega) = \frac{g_a^2}{\omega^2 + \omega^2_a},\label{alpha}
\end{equation}
where $\alpha_a (0) = 4.50\ a.u.$ ($1\ a.u. = 1.482 \cdot 10^{-31} m^3$) and
$\omega_a = 11.65 eV$ for hydrogen atom.

Let us consider different limits.

1) In the limit of perfect conductivity, $\Omega\to\infty$, which we call the
Boyer limit, we obtain
\begin{equation}
E_B = -\frac{\hbar c}{\pi L^2}\!\sum_{l=1}^\infty\! \nu \!\!\int_0^\infty
\!\!\!\!\!\!dk k \alpha (i\omega)
\!\!\left\{ \frac{s_l^2(x) e_l^2(z)}{s_l(x)e_l(x)} - \frac{
{s'}_l^2(x) {e'}_l^2(z) + {s'}_l^2(x)
{e}_l^2(z) \frac{\nu^2 - \frac{1}{4}}{z^2}}{s'_l(x)e'_l(x)}
\right\}.\label{FcpBoyer}
\end{equation}

2) The limit of infinite radius of sphere, $R\to \infty$, with fixed distance,
$d$, between the surface of sphere and an atom requires more machinery. In
this case we change the variable of integration $k\to \nu k$  in Eqs.
(\ref{Fcp}) and (\ref{FcpBoyer}) and use the uniform expansion for Bessel
functions.\cite{AbrSte70} In the limit of $R\to\infty$, the integrands in
above both  expressions have the same form and the main contribution to the
energy comes from the first term of uniform expansion,
 \begin{equation}
E = -\lim_{R\to \infty} \frac{\hbar c g^2}{\pi c^2 (R+d)^2} \sum_{l=1}^\infty
\nu^3 \int_0^\infty \frac{dy y}{y^2 \nu^2 + q^2}\frac{e^{-2\nu [\eta(u) -
\eta(y)]}}{ut(u)},
\end{equation}
where $u = y (1+d/R),\ q_a = k_a R$ , $t(x) =
1/\sqrt{1+x^2}$ and $\eta (x) = \sqrt{1+x^2} + \ln \frac{x}{1+\sqrt{1+x^2}}$.

Next, the sum over $l$ we represent in the following integral
\begin{equation}
\sum_{l=1}^\infty \frac{\nu^3 e^{-2\nu\delta}}{y^2 \nu^2 + q_a^2} = \frac{1}{4
q_a y} \int_{0}^\infty \frac{27 + 17 e^{-2(t+\delta)} + 5
e^{-4(t+\delta)}-e^{-6(t+\delta)}} {e^{3(t+\delta)}(e^{-2(t+\delta)}-1)^4 }
\sin\frac{2q_at}{y} dt.
\end{equation}
Assuming this expression we interchange the limit $R\to \infty$ and integrals
over $y$ and $t$ and obtain
\begin{equation}\label{defS}
E= -\frac{3\hbar c \alpha(0)}{8\pi d^4} S,
\end{equation}
where
\begin{equation}
S = \frac 13 \int_0^\infty dt e^{-t} \left\{ \frac{1+t}{1+\frac{t^2}{4v^2}} +
\frac{t}{(1+\frac{t^2}{4v^2})^2} \right\},
\end{equation}
and $v = dk_a$. Let us consider large distance, $d$, between the plate (sphere
of infinite radius) and an atom, $d k_a \gg 1$. In the limit of $v\to\infty$ we
obtain that $S =1$ and therefore the Casimir-Polder $(\sim d^{-4})$ energy,
\begin{equation}
E= -\frac{3\hbar c \alpha(0)}{8\pi d^4},
\end{equation}
is recovered. For small distances, $dk_a \ll 1$, we change the variable $t\to
\tau = t/2v$ and take the limit of $v \to 0$. In this case we obtain that $S =
\pi v/3$ and the energy has the form $\sim d^{-3}$,
\begin{equation}\label{CasPolSmall}
E= -\frac{\hbar c \alpha(0)k_a}{8 d^3},
\end{equation}
as should be the case. The plot of the $S$ as function of variable $v=dk_a$ is
shown in Fig. \ref{fig:sboyerv}.

\begin{figure}[pb]
\centerline{\includegraphics[scale=0.9]{1}}
\vspace*{8pt}
\caption{\footnotesize The plot of $S$ as the function of the $v=kd_a$. It tends
to unity for large $v$ ($E \sim d^{-4}$) and it is linear over $v$ ($E\sim
d^{-3}$) for small distances between an atom and plate. The relation of the
energy and $S$ is given by Eq. (\ref{defS}).}\label{fig:sboyerv}
\end{figure}

3) Let us analyze the energy for large ($d\gg k_a^{-1}, d\gg R$) and small
($d\ll k_a^{-1}, d\ll R$) distances between the sphere and an atom for finite
$\Omega$ and $R$. In the case of large distance, $d\to \infty$, of an atom from
the shell we use  Eq. (\ref{Fcp}). We change integrand variable $k=y/d$, next
take limit $d\to \infty$, and then we take the integral over $y$. The main
contribution comes from the first term with $l=1$:
\begin{subequations}
\begin{eqnarray}
E_\Omega &\approx&  -\frac{3\hbar c \alpha(0)}{8\pi d^4} S_\Omega,\allowdisplaybreaks  \\
S_\Omega &=& \frac{R^{3}}{d^{3}} \left\{ \frac{7Q}{3(3+Q)} + \frac{46}{3}
F(a)\right\},\allowdisplaybreaks  \label{sdinf} \\
F(a) &=& \frac{8a^{2}}{23} \int_0^\infty \frac{y^{4} + 2 y^{3} + 5 y^{2} + 6 y +
3}{3y^{2} + 2a^{2}}e^{-2y}dy,
\end{eqnarray}
\end{subequations}
where $a^{2} = Q d^{2}/R^{2} = d^{2} \Omega /R$. The first term in above
expression (\ref{sdinf}) comes from {\rm TE}\ mode and second -- from {\rm TM}\
polarization. The function $F$  increases monotonically from zero for small $a$
($d^{2} \ll R/\Omega$) to unity  for large $a$ ($d^{2} \gg R/\Omega$). In the
case of $a \ll 1$ the function $F(a) \approx 2\pi \sqrt{6} a/23$. Therefore, in
the limit of $\Omega \to 0$, the energy $E_\Omega \to 0$ as should be the case.

Assuming a finite conductivity, $\Omega \not = 0$, and  large distance $d \gg
k_a^{-1}, d \gg R, d \gg \sqrt{R/\Omega}$  we obtain that
\begin{equation*}
S_\Omega = \frac{R^3}{d^3} \left\{ \frac{7Q}{3(3+Q)} + \frac{46}3 \right\}
\end{equation*}
and  we arrive with expression
\begin{equation}\label{Egreat}
E_\Omega \approx  -\frac{\hbar c \alpha (0) R^3}{8\pi  (3+Q)d^7} (53 Q + 138).
\end{equation}
Taking into account the Casimir-Polder interaction energy of two atoms with
polarizations $\alpha$ and $\alpha_f$,
\begin{equation}
E = - \frac{23}{4\pi} \frac{\hbar c \alpha(0) \alpha_f(0)}{d^7},
\end{equation}
we observe that the sphere with finite conductivity has static polarizability
\begin{equation}\label{alpha_2}
\alpha_f = \frac{53 Q + 138}{46 Q + 138}R^3.
\end{equation}

For small distances we obtain that
\begin{equation}
E= -\frac{\hbar c \alpha(0)k_a}{8 d^3}
\end{equation}
as should be the case, because close to the sphere we observe flat surface.

\section{Numerical Analysis}\label{Sec:Num}

For simplicity we extract as a factor the Casimir-Polder expression for the
interaction energy of an atom with plate,
\begin{equation}
 E_{\Omega,B} = -\frac{3\hbar c \alpha (0)}{8\pi d^4} {S}_{\Omega},
\end{equation}
and we will numerically calculate the dimensionless quantity ${S}_\Omega$.

Let us consider the interaction energy between hydrogen atom and molecule
$C_{60}$. For this molecule\cite{Bar04} we have: $R = 3.42 \textrm{\AA} = 0.342
nm$, $Q = \Omega R = 4.94 \cdot 10^{-4}$ and $\Omega/k_a = 2.44\cdot 10^{-2}$.
The polarizability of hydrogen atom within the single-oscillator model
reads\cite{RauKleColBru82,BorGeyKliMos06,BlaKliMos07} $\alpha_a (0) = 4.50\ a.u.$
($1\ a.u. = 1.482 \cdot 10^{-31} m^3$) and $\omega_a = 11.65 eV = 17.698 \cdot
10^{15} Hz\ (k_a = 0.059 nm^{-1},\ \lambda_a = 106.4 nm)$ where $\omega/c = k=
2\pi /\lambda$. Therefore, $q_a = k_a R = 0.0202$.

Taking into consideration  all the numerical values of parameters we represent
the energy for this system in the following form
\begin{equation}
 E_{\Omega}(eV) = -\frac{0.0156}{d^4(nm)} S_{\Omega}(q_a,r),
\end{equation}
where the energy is measured in $eV$ and the distance is measured in nanometres.
The numerical simulations for the function $S$ are shown in Fig. \ref{fig:srd}
and the energy $E_\Omega$ in Fig. \ref{fig:srdhyd}.
\begin{figure}[pb]
\centerline{\includegraphics[scale=0.7]{2a}\includegraphics[scale=0.7]{2b}}
\vspace*{8pt}
\caption{\footnotesize The plot of $S$ as the function of the distance $d$
between an atom and the sphere. Thin curve is the energy for the case $R \to
\infty$ (Casimir-Polder energy for plate), middle thickness curve is the case of
the molecule $C_{60}$, and the thick curve is the case of ideal sphere ($\Omega
\to \infty$). In the figure $b$ we compare the energy for the plane with the
energy in the sphere case.}\label{fig:srd}
\end{figure}
The radius of the hydrogen atom is $r_H = 0.053 nm$. For this minimal distance,
$d=r_H$, we have numerically $E = 3.8 eV$. In the case of plate with hydrogen
atom we obtain $6.4 eV$.

\begin{figure}[pb]
\centerline{\includegraphics[scale=0.7]{3a}\includegraphics[scale=0.7]{3b}}
\vspace*{8pt}
\caption{\footnotesize The plot of the energy $E_\Omega$ as the function of the
distance $d$ between the sphere and the hydrogen atom. In the figure $a)$ we
show the energy starting from the distance $d = 0.053 (nm)$ (the radius of the
hydrogen atom). In the  figure $b)$  the energy in large interval is shown.}
\label{fig:srdhyd}
\end{figure}

For large distances we obtain from Eq. (\ref{Egreat})
\begin{equation}\label{Efar}
E_\Omega(eV) \approx -\frac{0.0095}{d^7(nm)}.
\end{equation}
This expression approximates the exact one with error $10\%$ starting with
distance $d=50nm$.

\section{Conclusion} \label{Sec:Conc}

In the foregoing, we have obtained the analytic expression for the
Casimir-Polder (van der Waals) energy for a system which contains an atom or
microparticle and  infinitely thin sphere with finite conductivity which models
a fullerene. We used the zeta-regularization approach and for renormalization we
used a simple physically reasonable condition -- the energy should be zero for
an  atom alone without a sphere. The conductive sphere with radius $R$ is
characterized by the only parameter $\Omega = 4\pi n e^2/mc^2$ with dimension of
wave number, where $n$ is the surface density of electrons. The limit $\Omega
\to \infty$ corresponds to the ideal case considered by Boyer.\cite{Boy68} The
microparticle is characterized by the only parameter, polarizability $\alpha$.

The expression obtained reproduces in the limit $R\to \infty$ the Casimir-Polder
result for an atom and plate (see Eqs. (\ref{defS})-(\ref{CasPolSmall})). For
small distances we have $d^{-3}$ dependence and far from the plate we obtain
$d^{-4}$ due to retardation. For finite radius of the sphere we have different
behavior of the energy. Close to the sphere,  $d\ll 1/k_a$ and $d\ll R$, we have
the same $d^{-3}$ dependence as in the Casimir-Polder case and far from the
sphere we obtained $d^{-7}$ dependence given in Eq. (\ref{Egreat}). This
expression is valid for $d\gg 1/k_a$ and $d\gg R$.

Application to the molecule $C_{60}$ with hydrogen atom is plotted in Fig.
\ref{fig:srdhyd}. For closest distance atom from the fullerene, which is radius
of hydrogen atom $r_H$, the energy is $3.8 eV$ which is two times smaller then
for the case of hydrogen atom with plate. Away from the fullerene (in fact
larger then $50 nm$) the energy falls down as $d^{-7}$ (see Eq. (\ref{Efar}))
which is in three orders of
magnitude faster then for the Casimir-Polder case. This dependence corresponds
to the Casimir-Polder interaction atoms for large distance. Taking into account
this analogy we obtain the polarizability of fullerene ($Q = \Omega R =
4.94\cdot 10^{-4} \ll 1$)
\begin{equation*}
\alpha_f = \frac{53 Q + 138}{46 Q +138} R^3 \approx R^3 = 4\cdot 10^{-29} m^3.
\end{equation*}
This expression is close to that calculated in Ref. \refcite{FowLazZan91} where
the authors obtained $\alpha_p(0) = 7\cdot 10^{-29} m^3$.

\section*{Acknowledgments}
The author would like to thank V. Mostepanenko and G. Klimchitskaya for
stimulation of
these calculations and M. Bordag for discussions. This work was supported by the
Russian Foundation for Basic Research Grant No. 11-02-01162-a.