# local_panprivacy_for_federated_analytics__5b4d44c1.pdf

Local Pan-Privacy for Federated Analytics

Vitaly Feldman * 1 Audra Mc Millan * 1 Guy N. Rothblum * 1 Kunal Talwar * 1

Pan-privacy was proposed by (Dwork et al., 2010) as an approach to designing a private analytics system that retains its privacy properties in the face of intrusions that expose the system s internal state. Motivated by federated telemetry applications, we study local pan-privacy, where privacy should be retained under repeated unannounced intrusions on the local state. We consider the problem of monitoring the count of an event in a federated system, where event occurrences on a local device should be hidden even from an intruder on that device. We show that under reasonable constraints, the goal of providing information-theoretic differential privacy under intrusion is incompatible with collecting telemetry information. We then show that this problem can be solved in a scalable way using standard cryptographic primitives.

1. Introduction

Private federated telemetry systems allow for collection of aggregate statistics from a population, while ensuring a strong privacy guarantee for individuals. For example, private federated learning and statistics have been used to collect webpage and search engine popularities from Chrome browsers (Erlingsson et al., 2014), learn popular emojis (Apple s Differential Privacy Team, 2017), collect Covid epedimiological metrics (Apple and Google, 2021), collect browser performance metrics (Helmer et al., 2018), collect operating system telemetry (Ding et al., 2017), and train keyboard models (Xu et al., 2023; Zhang et al., 2023).

These systems typically rely on the client device storing information about usage on device, and periodically, at appropriate times, taking part in a protocol that computes an aggregate. These protocols use encryption to protect this data from an eavesdropper. In some cases, additional cryptographic protocols are used to protect the individual contri-

*Equal contribution 1Apple, Cupertino, CA, USA. Correspondence to: Kunal Talwar <ktalwar@apple.com>.

Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

butions from the server computing the aggregate (Bonawitz et al., 2017; Corrigan-Gibbs and Boneh, 2017). Finally, the aggregate itself protects individual contributions by noise addition to provide a differential privacy guarantee.

In some applications, one may want to additionally protect against an attacker that has access to the device. For example, a computer in a public library may be accessed by one user, and later by another. In such a case, we would want to ensure that the second user cannot learn about the activity of the first user by inspecting the internal state of the device. In this work, we initiate the study of estimating population statistics while ensuring privacy against an ondevice intruder. We call this model local pan-privacy, as it aims to protect against an intrusion at the local device, much as pan-privacy protects against an intrusion at the server.

We study locally pan-private algorithms for some fundamental statistical tasks in a simple streaming setting. There are n devices in total. For each device, at each time step, an event of interest, such as an application crash while using a feature, may or may not occur. Thus, each device s input is a sequence of T bits. The device can communicate with the server at the end of the T time steps, and we require that the protocol retains its privacy properties in the face of multiple intrusions on device (c.f. Remark 4). The first statistic we study is COUNTNONZERO, which counts the number of devices on which the event occurred in at least one of the T time steps. In the standard local privacy model, this task can be accomplished by each device sending a randomized response of a bit corresponding to whether on not the event occurred at any of the T steps. Such a protocol can also lead to near-optimal central privacy guarantees via shuffling or aggregation (Feldman et al., 2020), when the responses are aggregated by a trusted server, or by a secure aggregation system. In this work, we focus on the setting where we either have a trusted server, or where the secure aggregation system uses a two-server architecture as in PRIO (Corrigan-Gibbs and Boneh, 2017).

We also study two additional statistics of the event count distribution: the mean number of occurrences per device, and a histogram of the number of occurrences, appropriately bucketed. As with the COUNTNONZERO, these tasks also admit simple and commonly-used algorithms in the local privacy model, based on the Laplace mechanism (Dwork

Local Pan-Privacy for Federated Analytics

et al., 2006) and on RAPPOR (Erlingsson et al., 2014) respectively. We remark that these simple tasks underpin a large number of private federated statistics, and can enable a much richer set of data science tasks. For example, Zhu et al. (2020); Chadha et al. (2024) use histograms over small known domains to discover heavy hitters over large domains.

We show that local pan-privacy is severely limited if we insist on providing (information-theoretic) differential privacy in the face of intrusions. Our lower bound shows that for the COUNTNONZERO task, the error of any algorithm must be

T times larger than that needed for local differential privacy alone. This lower bound holds even when the event occurs at most once on each device.

Theorem 1 (Informal version of Theorem 9). Any locally pan-private algorithm (for ε = 1) for COUNTNONZERO on n devices, for large enough T, must incur additive error Ω(

n T), even though a local DP algorithm can estimate COUNTNONZERO with additive error Ω( n).

We then show that under standard cryptographic assumptions, local pan-privacy can be ensured without this overhead. We present algorithms for all of the aforementioned problems, for both the singleand the two-server models, showing that local pan-privacy comes at no additional cost in the privacy-utility trade-off. Our protocols need a publickey encryption scheme, with a few additional properties that are satisfied by commonly-used encryption schemes. We note that public-key encryption is already used to protect the communication from a network intrusion, so local panprivacy does not increase the complexity of the required assumptions. While we can define local pan-privacy broadly as a computational differential privacy guarantee against a local intruder, our protocols actually provide a stronger semantic security guarantee.

Theorem 2 (Informal version of Theorem 10). Suppose that we have a public-key encryption scheme that is rerandomizable. Then there is a streaming algorithm for COUNTNONZERO in the single-server and in the two-server model with the following properties.

The on-device algorithm satisfies computational local pan-privacy; the on-device sequence of states on any pair of input streams are computationally indistinguishable.

The on-device state consists of O(1) ciphertexts, and the device sends one message consisting of O(1) ciphertexts.

In the local and aggregator model of differential privacy, the algorithm achieves privacy-utility trade-offs that are within constant factors of algorithms without the local pan-privacy constraint.

In a rerandomizable encryption scheme, a ciphertext can be rerandomized (using only the public key) to create a new ciphertext encrypting the same plaintext, which is indistinguishable from a fresh encryption of a different plaintext, see Definition 2.8. A similar result to Theorem 2 holds for building approximate histograms, as well as for estimating the mean number of events. The latter requires slightly stronger assumptions on the encryption scheme (namely, the scheme needs to be additively homomorphic).

At a high level, this is achieved by maintaining a state on device that contains information about the stream so far, but in encrypted form. Since the local device does not have the private key, this ensures that the on-device state contains no useful information for an adversary that does not collude with the server. The challenge then is to maintain the state under updates to the stream, and we show that for our tasks of interest, this is feasible. We remark that a publickey fully homomorphic encryption (FHE) scheme can be used to achieve computational local pan-privacy, as any algorithm for the on-device computation can be made locally pan-private by keeping the state encrypted at all times and operating on the encrypted state. However, this is overkill: FHE schemes incur a large space and time overhead, and in this work we strive to rely on more minimal and more efficient cryptographic primitives.

We provide privacy at the level of the whole device, and not just at the event level. Thus a user may use the shared device multiple times during our collection period, and our algorithms will protect all of their interactions. Our model allows for continuous intrusion: the adversary can see the state of the device before and after each update. In our example of a shared device, this means that the attacker can see the memory contents of the device before and after a user is using it (but not while they are using it). Thus from our point of view, the updates to the state are atomic. Finally, we show that the existence of a public-key encryption scheme is necessary for the existence of an accurate locally pan-private algorithm for COUNTNONZERO.

Theorem 3 (Informal version of Theorem 6.1). Suppose that we have a locally pan-private algorithm for COUNTNONZERO that has additive error less than n/4 with high probability. Then we can build a public key encryption scheme.

1.1. Related Work

Pan-privacy (Dwork et al., 2010) was proposed as an approach to designing data analysis algorithms that do not maintain a disclosive internal state. In particular, they maintain privacy even under intrusions. This notion was studied in several subsequent works, e.g. (Mir et al., 2011). The goal of maintaining privacy in the presence of potential intrusions on a user s device is common to several settings.

Local Pan-Privacy for Federated Analytics

Examples include web browsing, where several popular browsers offer a mode where browsing history is not stored on device and chat apps where messages are ephemeral. In many situations, it may be undesirable to keep any information from events in such settings. In others, statistical information about events such as application crashes may be useful to improve the user experience. The notion of history independence (Micciancio, 1997; Naor and Teague, 2001) shares similar goals of ensuring that the memory representation of a data structure does not leak information about the history of interactions with a data structure. Oblivious RAM algorithms (Goldreich and Ostrovsky, 1996) share a similar goal of ensuring that the memory access pattern of an algorithm does not leak information about the inputs it is being run on. Forward Secrecy (G unther, 1990) addresses a similar goal of protecting old communications from future intrusions.

Organization:

We present some preliminaries and definitions in Section 2. Section 3 presents our lower bound for the informationtheoretic privacy case. We present algorithms in the singleand two-server settings in Section 4 and Section 5 respectively. Section 6 shows that public-key cryptography is needed, and we conclude with some open problems in Section 7. For lack of space, some of the results, and some proofs are deferred to supplementary material.

2. Definitions and Preliminaries

We first recall the definition of differential privacy.

Definition 2.1 ( (ε, δ)-Indistinguishability). We say that two random variables Y and Y on a finite set R are (ε, δ) indistinguishable if for for every S R,

Pr[Y S] eε Pr[Y S] + δ,

and Pr[Y S] eε Pr[Y S] + δ.

When two r.v. s are (ε, 0)-indistinguishabile, we will often call them ε-indistinguishable.

Definition 2.2 (Differential Privacy). A mechanism M : Dn R is (ε, δ)-differentially private if for any pair of neighboring datasets x, x , the random variables M(x) and M(x ) are (ε, δ)-indistinguishable.

Here neighboring datasets typically means datasets that differ in the input of one user.

We consider a data stream x = x1, . . . , x T , where each xi D. In this work we will be concerned with the case that D = {0, 1}. A streaming algorithm is defined by a set of functions. The function Initialize (usually left implicit) sets up the state on device, including the state s0, and potentially some state on the server to allow coordination

between the two. We have a sequence of functions, where Statet : D S S is a (possibly randomized) function that takes the input at time t and the current state st 1, and maps to the new state. Given an input stream x1, . . . , x T D and an initial state s0 (we will sometimes omit s0 as an argument for brevity), let st = Statet(xt; st 1) and State(x1, . . . , x T ) = (s0, s1, . . . , s T ).

An estimation algorithm is defined by additional functions Out and A, where Out maps s T to an output space O, and Est takes a vector of n elements from O and computes an estimate of the desired statistic. Definition 2.3 (Local pan-privacy). We say a streaming algorithm defined by a set of functions Statet is ε-locally pan-private if for any pair of streams x = x1, . . . , x T and x = x 1, . . . , x T , the state vectors State(x) and State(x ) are ε-indistinguishable. Remark 4. Several remarks are in order. (a) The definition considers neighboring datasets to differ in the full stream at one device. Thus it provides user-level privacy. (b) We require that privacy holds against an adversary that can monitor the internal state on the device after each event, and all communication out of the device. In other words, we guard against multiple intrusions, or continuous intrusion. The problem becomes easier if we only had to guard against a single intrusion. However, for the examples that motivate this work (shared device such a public computer), restricting the adversary to a single intrusion is unnatural. (c) A natural generalization of our model can allow the device to send multiple messages, while making sure to account for the potential information leakage from the event of sending or not-sending a message (that may be observable by an adversary). This generalization does not make the model stronger, as an algorithm that is locally pan-private in this model can store the messages it would have sent, and send them at step T.1 (d) In some settings, one may only be interested in a smaller set of admissible streams x, and one can naturally adapt the definition above by requiring the streams x and x to be admissible. We have aimed to keep the definition above simple, at the expense of generality. One can replace the quantifier over x, x above to require them to lie in some set X of admissible streams.

The following definitions capture the standard notions of privacy for such algorithms. Definition 2.4. We say an estimation algorithm is (ε, δ)- locally differentially private if for any pair of streams x = x1, . . . , x T and x = x 1, . . . , x T , the distributions Out(State(x)) and Out(State(x )) are (ε, δ)- indistinguishable. Definition 2.5. We say an estimation algorithm is (ε, δ)- aggregator differentially private if for any pair of streams x

1If we were concerned about the size of S, the many-messages version of the model may be more powerful.

Local Pan-Privacy for Federated Analytics

and x , and any set of (n 1) streams {y(j)}n 1 j=1 the distributions defined by Pn 1 i=1 Out(State(y(i)))+Out(State(x)) and Pn 1 i=1 Out(State(y(i))) + Out(State(x )) are (ε, δ)- indistinguishable.

We next define computational indistinguishability. A security parameter λ will control various quantities in these definitions. The adversary will be computationally bounded to be polynomial in λ, and we say a function in λ is negligible if it approaches zero faster than the inverse of any polynomial in λ.

Definition 2.6. Let {Dλ}λ and {D λ}λ be two ensembles of distribution. We say that they are f(λ)-computationally indistinguishable if for any non-uniform probabilistic polynomial time algorithm A,

| Pr z Dλ[A(z) = 1] Pr z D λ [A(z) = 1]| f(λ).

When two ensembles are f(λ)-computationally indistinguishable for negligible function f, we say that they are computationally indistinguishable.

We use a public-key encryption scheme.

Definition 2.7. A public key encryption scheme is defined by the following set of probabilistic polynomial time (p.p.t.) algorithms.

Key Generation Key Gen( ) takes a security parameter in unary 1λ and outputs a pair of keys (kpriv, kpub), each in {0, 1} .

Encryption Enc(m, kpub) takes a message m and a public key kpub and outputs an encryption c {0, 1} .

Decryption Dec(c, kpriv) takes a ciphertext c and a private key kpriv and outputs a message m.

These functions have the following properties:

Correctness Suppose that (kpriv, kpub) Key Gen(1λ) for some λ. Then for any m {0, 1}k, it holds that Dec(Enc(m, kpub), kpriv) equals m.

Semantic Security For any m, m , the encryptions Enc(m, kpub) and Enc(m , kpub) are computationally indistinguishable.

We rely on encryption schemes that allow re-encryption of an encrypted message.2 Informally, a rerandomizable

2This is slightly weaker than the usual notion of rerandomizable encryption, as we allow c and Φr(c, kpub) to be distinguishable. We show that this notion is necessary and sufficient for our purposes.

encryption allows for an encrypted message to be rerandomized , i.e. to be replaced by a new encryption of the same message, that is indistinguishable from a new encryption. Here and in the rest of the paper Φr t( ) denotes the t-fold composition Φr(Φr(. . . (Φr( )))). Definition 2.8. A public key encryption scheme is rerandomizable if there is a function Φr(c, kpub) with the following properties. For any m, m , and any t 0, let c = Φr t(Enc(m, kpub)) and c = Φr t(Enc(m , kpub)), and let c = Φr(c, kpub) and c = Φr(c , kpub). Then Dec(c, kpriv) = Dec( c, kpriv). Furthermore, the tuple (c, c) is computationally indistinguishable from (c, c ).

Note that this definition implies that for any t and any m, m , the distributions Φr t(Enc(m)) and Φr t(Enc(m )) are computationally indistinguishable. We remark that we do not require a rerandomized ciphertext to be indistinguishable from a freshly generated one: it need only be indistinguishable from a rerandomized encryption of any different plaintext (for the same number of rerandomizations t).

Mironov et al. (2009) defined and related different notions of computational differential privacy, and those notions can be extended to local pan-privacy. We state a version of this definition next. Definition 2.9 (Computational (ε, δ)-indistinguishability). Let {Dλ}λ and {D λ}λ be two ensembles of distribution. We say that they are computationally (ε, δ)-indistinguishable if for any non-uniform probabilistic polynomial time algorithm A,

Pr z Dλ[A(z) = 1] eε Pr z D λ [A(z) = 1]| + δ + negl(λ).

When two ensembles of r.v. s are computationally (ε, 0)- indistinguishabile, we will often call them computationally ε-indistinguishable. Definition 2.10 (Computational Local Pan-Privacy,IND-CDP version). We say a streaming algorithm defined by a set of functions Statet is computationally ε-locally pan-private if for any pair of streams x = x1, . . . , x T and x = x 1, . . . , x T , the state vectors State(x) and State(x ) are computationally ε-indistinguishable.

We recall some basic mechanisms that will be useful. We refer the reader to Dwork and Roth (2014) for their privacy proofs. Definition 2.11 (Randomized Response). Let ε > 0. The randomized response mechanism 2RRε : {0, 1} {0, 1} is an ε-DP mechanism defined as:

2RRε(b) = b with probabilty eε 1+eε 1 b with probabilty 1 1+eε

The following observation about implementing randomized response will be useful.

Local Pan-Privacy for Federated Analytics

Observation 5. Let b {0, 1} and ε > 0. Then 2RRε(b) can be implemented by outputting b with probability eε 1

eε+1, and outputting a random bit otherwise.

We will use the following lemma that says that any 2-input local randomizer is a post-processing of a randomized response.

Lemma 2.1. (Kairouz et al., 2015) Let R : {0, 1} S be an ϵ-DP local randomizer. Then there exists a postprocessing function h : {0, 1} S such that R(0) = h(2RRϵ(0)) and R(1) = h(2RRϵ(1)).

The following utility bounds for randomized response are standard (Feldman et al., 2020).

Theorem 6. Let ε0 > 0. Then for any b1, . . . , bn {0, 1}, one can post-process their randomized responses {yi = 2RRε0(bi)} to derive an estimate ˆS of S = P

i bi such that

E[ ˆS] = S; E[| ˆS S|] O

n 1 + eε0 (1+eε0)2 !

Theorem 7. Let (ε, δ) (0, 1). Then there is an ε0 such that for any b1, . . . , bn {0, 1}, the randomized responses {yi = 2RRε0(bi)} are (ε, δ)-DP in the aggregator model. Further their sum can be post-processed to derive an estimate ˆS of S = P

i bi such that

E[ ˆS] = S; E[| ˆS S|] O( q

Let x = x1, . . . , x T be an input stream with each xi {0, 1}. We denote by 1(x) the predicate (maxi xi = 1). For a set of streams {x(i)}n i=1, the COUNTNONZERO value is defined as P

3. Lower Bound

In this section, we prove a lower bound showing that information-theoretic local pan-privacy incurs a non-trivial cost on the achievable accuracy for the basic COUNTNONZERO task. Without local pan-privacy, this task can be solved easily. Each device maintains 1(x1:t), which can be done with a single bit of state. Randomized response on this state after T steps allows us to estimate COUNTNONZERO with additive error O(1/ε) in the aggregator DP setting (Theorem 7), and O( q

n(1 + eε (eε 1)2 )) in the local DP setting (Theorem 6). In contrast, we show that information-theoretic local pan-privacy entails a polynomial dependence on T. This lower bound holds for the case when the input streams are restricted to have at most a single 1 .

Each client receives a stream of inputs x1, . . . , x T {0, 1}, can communicate once to the server, and the goal of the server is to compute the number of clients such that 1(x) =

1. We will prove the following theorem. Note that this means that the correlation between the message a device sends, and 1(x) is at most O(1/

Theorem 8. Let A be an ε-locally pan-private client-side algorithm for the COUNTNONZERO task comprising of the pair State and Out. Then there exists inputs x and x such that 1(x) = 0, 1(x ) = 1, and

TV (Out(State(x)), Out(State(x ))) O((eε 1)/

This bound, coupled with standard techniques (e.g. (Duchi et al., 2013)), yields the following lower bound. This shows that for large T, local pan-privacy must come at a significant cost.

Theorem 9. Let A be an ε-locally pan-private algorithm run on n clients, and let ˆS be any estimate of COUNTNONZERO(x(1), . . . , x(n)) derived from the the outputs of A. For T 16eε, ˆS has expected error Ω( p

n Teε/(eε 1)2).

Algorithm 1 f D

1: Require: State, Out, initial state s0 2: Input: b 3: if b = 0 then 4: Return Out(State((0, . . . , 0); s0)) 5: else 6: Select t Uniform([T]) 7: Set x t = 1 and xt = 0 for t [T]\{ t} 8: Return Out(State((x1, . . . , x T ); s0)) 9: end if

We will now prove Theorem 8. We start by using the locally pan-private algorithm A to construct a randomized function f D from {0, 1} to the output space of the algorithm. On input 0 , this algorithm runs A on the all 0 s stream. On input 1 , it will put a 1 at a uniformly random place in the stream (with other xt s being 0) and run A on the resulting stream. Since 1(x) is different on these two streams, we expect this f D to behave differently enough on 0 and 1. We will argue that the local pan-privacy constraint prevents these distributions from being too far.

Towards this goal, we first argue that the output of a locally pan-private algorithm can be obtained as a post-processing of randomized responses of individual xt s.

Lemma 3.1. Given an initial state s0, there exists a postprocessing function g such that

State((x1, . . . , x T ); s0) = g(2RRϵ(x1), . . . , 2RRϵ(x T )).

Proof. We will first show that if State is ϵ-DP then for all t [T] and any state st 1, Statet( ; st 1) is ϵ-DP.

Local Pan-Privacy for Federated Analytics

Let t [T], st 1 S, and xt, x t {0, 1}. Further, let {xt }t [T ]\{t} {0, 1}T 1 and {st }t [T ]\{t} ST 1, then

Pr(Statet(xt; st 1) = st) Pr(Statet(x t; st 1) = st)

= Pr(Statet(xt; st 1) = st)

Pr(Statet(x t; st 1) = st)

Pr(Statet (xt ; st 1) = st ) Pr(Statet (xt ; st 1) = st )

= Pr(State((x1, . . . , xt, . . . , x T ); s0) = (s1, . . . , s T ))

Pr(State((x1, . . . , x t, . . . , x T ); s0) = (s1, . . . , s T )) eϵ.

Thus the map Statet( ; st 1) can be viewed as a local DP mechanism, and thus Lemma 2.1 implies that it can be written as a postprocessing of a randomized response. Given t [T] and st 1 S, let ht,st 1 : {0, 1} S be such that for b {0, 1}, Statet(b; st 1) = ht,st 1(2RRϵ(b)). Then we can define g(b1, . . . , b T ) = (s1, . . . , s T ) where st = ht,st 1(bt).

We next argue that this, and the fact that our distributions on x are exchangeable implies that the output really is a post-processing of the count of the number of 1s in the randomized responses.

Lemma 3.2. Given any initial state s0, there exists a postprocessing function h such that f D(0) = h(Bin(T, 1 eϵ+1)) and f D(1) = h(Bin(T 1, 1 eϵ+1) + Ber( eϵ eϵ+1)). Further,

TV(f D(0), f D(1)) (1)

TV Bin(T, 1 eϵ+1), Bin(T 1, 1 eϵ+1) + Ber( eϵ eϵ+1)

Proof. By Lemma 3.1, there exists g : {0, 1}T ST such that State((x1, . . . , x T ); s0) can be written as g(2RRϵ(x1), . . . , 2RRϵ(x T )). Under our distribution on x conditioned on b, the random variables xt s are exchangeable, and thus conditioned on the count of 1s in 2RRε(xi) s, all permutations are equally likely. The function h is then described in Algorithm 2. This implies the first part of the claim. The inequality Eq. (2) is a consequence of the data processing inequality. The second inequality is standard. For completeness, we give a proof in Appendix A.

Lemma 3.2 implies Theorem 8 and completes the proof of our lower bound.

Algorithm 2 h

1: Require: g, Out 2: Input: m [T] 3: Sample b uniformly at random from {b {0, 1}T | |b|1 = m}. 4: Return Out(g(b)).

4. The Single-Server Model

In this section, we will discuss the single-server model. We will require a rerandomizable public-key encryption scheme. Our computational local pan-privacy will be achieved by the device storing encryptions of any sensitive state. As the device does not hold the private key, the on-device state is computationally indistinguishable from a sequence of encryptions of 0.

4.1. Counting Devices that have at least one occurrence

Let us first consider the problem of differentially privately computing the number of clients for which the sensitive event occurs at least once. In Section 4.2 we will discuss how to extend our approach to building a histogram of the number of occurrences of the sensitive event.

We start by describing how the count will be stored and updated on device. At the beginning of the collection period, the client initializes the state to be an encryption of 0. At each time step, the device updates the state. If xt is 1, i.e. if the sensitive event has occurred in this time step, the device replaces the state with a fresh encryption of 1, with an appropriate number of rerandomizations applied. If xt is 0, the device rerandomizes the current state. This continues until the end of the time horizon. Pseudo-code is given in Algorithm 3. This algorithm does not reveal anything about whether or when updates have occurred to an intruder, even if the intruder can view the internal state of the device after each time step. The intrusion resistance comes from the fact that an intruder can not distinguish between a fresh (rerandomized) encryption of 1, and a rerandomization a current encrypted value. Formally, the state after t steps is computationally indistinguishable from Φr t(Enc(0)). Finally, the device uses randomized response to send their encrypted bit to the server. This can be done without needing to decrypt the state using Observation 5. The sent message is computationally indistinguishable from Φr T +1(Enc(0)). We remark that for most practical cryptosytems, Φr t(Enc(b)) has the same distribution as Enc(b) so that we can optimize the algorithm by replacing the Φr t(Enc(b)) steps by Enc(b).

At the end of the collection period, the goal of the server is

Local Pan-Privacy for Federated Analytics

Algorithm 3 COUNTNONZERO, Client Algorithm Require: T, ϵ0, Enc, Φr, x = x1, . . . , x T

1: Initialization 2: c = Enc(0)

3: State Update 4: for t = 1 : T do 5: if xt = 1 then 6: c = Φr t(Enc(1)) 7: else 8: c = Φr(c) 9: end if 10: end for

11: Send to Server 12: r = Ber( eϵ0 1

eϵ0+1) 13: if r = 0 then 14: r = Ber(1/2) 15: if r = 1 then 16: c = Φr T +1(Enc(0)) 17: else 18: c = Φr T +1(Enc(1)) 19: end if 20: else 21: c = Φr(c) 22: end if 23: Return c

to compute a differentially private estimate of the number of devices for which the sensitive event occurred at least once. Since they have the private key, they can decrypt the local reports from each client, then aggregate and de-bias the resulting sum in the same way they would for randomized response. The following result follows:

Theorem 10. Let ε0 > 0. Suppose that each client i uses Algorithm 3 on its input x(i). Then the server can estimate COUNTNONZERO on inputs {x(i)}n i=1 with expected

n 1 + eε0 (1+eε0)2 and ε0-local differential

privacy. For any (ε, δ) (0, 1), there is an ε0 such that the mechanism is (ε, δ)-aggregator DP, and has expected error

δ /ε). The client algorithm satisfies computational 0-local pan-privacy.

4.2. Computing Histograms of the Number of Occurrences

In this section we will consider how to compute a histogram of the number of clients that have a particular number of occurrences. We will solve a slightly more general problem, where we are given a k and the goal is to estimate for each

i {0, 1, . . . , k 1} the number of devices with count |x|1 equal to i, as well as the number of devices with count at least k. While one could always set k = T, this generalization can allow more efficient solutions in the regime where T is large and the number of occurrences per device is much smaller than T. To handle this last bucket of count at least k, we will maintain an (encrypted) indicator di for each i, of the event |x|1 i.

At the beginning of the collection period, the device initializes k + 1 counters to be an encryption of the initial histogram, i.e. c0 = Enc(1), c1 = Enc(0), . . . , ck = Enc(0). Additionally, it initializes d0 = Enc(1) and di = Enc(0) for each i = 1, . . . , k. At each time step, if an event has not occurred, all the counters are rerandomized. If an event has occurred then all the counters are rerandomized and shifted by 1. The counter c0 is set to be an Enc(0), and d0 is set Enc(1). At the end of T steps, the device has the desired values (v0, v1, . . . , vk) in (c0, c1, . . . , ck 1, dk), since ci encrypts 1(|x|1 = i) and dk encrypts 1(|x|1 k). It uses randomized response on each of these to send the result to the server. We defer the full pseudocode to Algorithm 5.

Upon receiving the reports from each client, the server can decrypt the randomized responses. We sum these reports and use the standard de-biasing for randomized response to obtain an unbiased estimate of each histogram bucket count. Note that the sensitivity of the vector (v1, . . . , vk) is 1 as at most one of the values can be 1. Thus even though k randomized responses are sent, the noise added does not grow with k. Since we run randomized response on each coordinate of the histogram, Theorem 6 and Theorem 7 implies that

Theorem 11. Algorithm 5 is computationally 0-locally pan-private, and ε0-local DP with respect to the server. It estimates the histogram with expected error

n 1 + eε0 (1+eε0)2 for each bucket count. More-

over, for any (ε, δ) (0, 1), there is an ε0 such that the mechanism is (ε, δ)-aggregator DP, and has expected error

δ /ε) for each bucket count.

4.3. Computing the Average Number of Occurrences

Computing the average number of occurrences per-device can be done using histograms, under the assumption that no count is larger than k. Alternatively, the resulting average can be viewed as an average of a truncation (at k) of the original counts. However using the estimate P

j cj = Pk i=1 i |{j : ci = j}| will result in error that scales as O(k 3 2 ). In Appendix B, we show that using an encryption scheme that has one additional property, we can reduce the error to O(k), matching the bound one would get in the central model.

Local Pan-Privacy for Federated Analytics

5. The Two-Server Model

In this section we will address the two-server model of (Corrigan-Gibbs and Boneh, 2017), where the client sends secret-shares of their data to two servers. Any sensitive information stored locally will be secret-shared with the shares encrypted by the public keys of two separate servers at all times. This scheme is protected against continuous intrusion by an adversary that does not collude with either of the servers.

In the two-server model, we often want to additionally protect the server against malicious clients who seek to poison the result by sending secret-shares of invalid reports. For example, instead of sending a secret-sharing of 0 or 1, a malicious device may send a secret-sharing of a million to skew the result. We will build on zero-knowledge proofs of validity for the predicates of interest. Our construction will maintain encrypted secret-shares of the state. The additional complexity arising from these proofs is that to construct the proof of validity, one needs to know the secret-shared data. To address this, we make use of an important fact. The proofs in Prio depend on the input being secret-shared (as they must), but conditioned on the input, do not depend on the encryptions of the secret-shares. This allows the proofs to remain valid when we rerandomize the encryptions. Thus our algorithms will generate proofs of validity when the relevant secret-shares are created. One can rerandomize the encryptions of the secret-shares and the proofs, without impacting the validity of the proofs.

5.1. Counting Devices that have at least one occurrence

We first consider the problem of counting the number of devices that have at least one occurrence in the two-server model. The on-device and server-side algorithms will both be very similar to the single-server setting but with the addition of secret-sharing of any sensitive information on device, and creating validity proofs. For lack of space, we defer the detailed pseudocode to Algorithm 6 in Appendix D.

We remark that this algorithm can resist an intrusion by an adversary that does not collude with either of the two servers. This can be relaxed to allow the adversary to collude with one of the two servers. The place where the collusion with a server can create a challenge is that a colluding server can help the adversary detect whether its share is changed in step 9 or if only the encryption is rerandomized and the share itself is unchanged (step 14). If we use an additively homomorphic encryption scheme (see Definition B.1), we can create new secret-shares under the encryption instead, so that each c(i) is an encryption of a fresh random field element after each update. This allows for non-interactive proofs, including the SNIPs (Corrigan-Gibbs and Boneh, 2017) that use Beaver triples. Each client sends the secretshares of their contribution to the two servers. Each server

can then decrypt the shares with their private key and aggregate the result. The sum of the shares at the two servers can then be de-biased to give the final result. The servers can also validate the proofs to ensure that the secret-shared values are all in {0, 1}.

5.2. Computing Histograms of the Number of Occurrences

Using the same approach as we did for COUNTNONZERO, we can extend our algorithm for histograms in the singleserver setting to work in the two-server model as well. As with the COUNTNONZERO algorithm, the validity property that is being validated is that each of the k + 1 reported values are in {0, 1}. Thus the same approach to constructing validity proofs suffices. For brevity, we omit a detailed description of the algorithm.

6. On the need for rerandomizable Public-key cryptography

We show that a rerandomizable public-key encryption scheme is necessary for computational 0-local pan-privacy. Recall that any locally pan-private algorithm also has an Initialize operation, that creates some shared state between the client and the server(s). In our implementations, this operation would be one that provides the public keys to the clients, and creates the initial state s0.

Theorem 6.1. Suppose that we have a set of algorithms Initialize, {Statet}T t=1, Out, and Est that define a computationally 0-locally pan-private streaming algorithm that estimates COUNTNONZERO on any set of inputs with error at most n/4, with probability 1 negl(n) for large enough n. Then for any security parameter λ and given a T = poly (λ), we can define functions Key Gen, Enc, Dec that define a public-key encryption scheme, where each of these operations runs in poly (λ) time. The scheme is rerandomizable in the sense of Definition 2.8, supporting up to T 1 rerandomizations.

Proof. We will build an encryption scheme that can encrypt a single bit b. The basic idea of the construction is to simulate running the algorithm on n clients, where for each client i, the first input in the stream x(i) 1 is set to b. The internal state of all the clients will comprise the encryption. The decryption will simulate the state transformations given x(i) t = 0 all the way to T, generating the outputs, and running Est on the outputs. The utility guarantee implies that the decryption recovers the original intended bit. The local pan-privacy implies the security of the scheme. Finally rerandomization is achieved by simulating a single state transformation. We give details next.

For a suitably large n = poly (λ), Key Gen will run the

Local Pan-Privacy for Federated Analytics

Initialize operation n times, and return the set of n client states, including the state s(i) 0 for each client, as a public key kpub, and the n server states as private key kpriv. Additionally, the parameter T will be included in both the keys. Given a bit b, Enc(b, kpub) will simulate for each i, one step of the locally pan-private algorithm on input b starting at state s(i) 0 to derive a set of states s(i) 1 . The encryption will be defined as (1, {s(i) 1 }n i=1). In general, valid ciphertexts will look like (t, {s(i) t }n i=1), for some t T, and some set of states {s(i) t }n i=1. Given such an encryption, the Dec algorithm will simulate, for each i, running the state transformations Statet+1, . . . , State T on s(i) t with input x(i) t+1 = 0, followed by running Out to generate a set of n messages. It then runs Est on the collection of n messages, and returns 0 if the answer is smaller than n/2, and 1 otherwise. Finally, Φr on a ciphertext c = (t, {s(i) t }n i=1) (for t < T) will simulate, for each i, running the state transformations Statet+1 on s(i) t with input x(i) t+1 = 0 to get an updated state s(i) t+1. The updated ciphertext c is then set to (t + 1, {s(i) t+1}n i=1). Any input ciphertexts with t T are rejected by Φr.

It is easy to see that Dec(Enc(b, kpub), kpriv) comprises an exact simulation of running the COUNTNONZERO algorithm on n clients on inputs (b, 0, 0, . . . , 0), followed by rounding the final estimate. Since the correct answer to COUNTNONZERO on these inputs is bn and the estimation algorithm has error n/4 with high probability, we conclude that the encryption scheme satisfies Dec(Enc(b, kpub), kpriv) = b except with negligible probability.

The security of the encryption follows from the computational local pan-privacy. Indeed if we had an efficient algorithm A that can distinguish Enc(0, kpub) and Enc(1, kpub), then by a standard hybrid argument, it can be used to distinguish State(0, s0) and State(1, s0), which violates the computational 0-local pan-privacy.

The rerandomization is essentially simulating one step in the decoding. It is therefore immediate that for any valid ciphertext, Dec(Φr(c, kpub), kpriv) and Dec(c, kpriv) are running exactly the same simulation and thus are identically distributed. Finally, the security of the rerandomization follows once again from the hybrid argument: if we could distinguish iterated rerandomizations of 0 from those of 1, we would get a distinguisher that can learn the first input x1 from the local state at some later time step t.

We note that the proof uses instances which have either zero or one 1 in each input stream. Thus any accurate algorithm for histogram estimation implies one for COUNTNONZERO with the same accuracy, and hence would also

imply a public-key encryption scheme.

We next extend this argument to handle a large class of εlocally pan-private algorithms for ε > 0. This result will apply to locally pan-private algorithms that use at most logarithmic space, and which use the same state transformation function State at all time steps.

Theorem 6.2. Let ε (0, 1). Suppose that we have a set of algorithms Initialize, State, Out, and Est that define a computationally ε-locally pan-private streaming algorithm that estimates COUNTNONZERO on any set of inputs with error at most n/4, with probability 1 negl(n) for large enough n, and for up to T steps, using S bits of space. Then for any security parameter λ, we can define functions Key Gen, Enc, Dec that define a ( ε

T + T negl(λ))- secure public-key encryption scheme, where each of these operations runs in poly (λ, 2S) time. The scheme is rerandomizable in the sense of Definition 2.8, supporting up to T 1 rerandomizations.

We defer the proof to Appendix C. Note that if T 1 is negl(λ) and S is O(log λ), then the resulting public-key encryption scheme is secure.

7. Conclusions

In this work, motivated by privacy concerns on shared devices, we introduce the notion of local pan-privacy. We show that while information-theoretic local pan-privacy may be too strong a requirement for basic telemetry tasks, computational versions of this definition can be achieved without sacrificing on utility. We present algorithms for the fundamental tasks of counting the number of devices where a sensitive event occurs, as well as histograms of event counts, both in the trusted server and the two-server models. Our algorithms use public-key encryption schemes, and we show that such schemes are necessary to achieve computational local pan-privacy.

Our work raises many natural question. Our lower bound in Theorem 8 relies on instances with at most a single 1, and shows a

T gap in the error. We conjecture that this can be strengthened to an Ω(T) gap when one allows the instances to have arbitrarily many 1s. While we have given algorithms for the most common telemetry tasks, other telemetry tasks may raise additional challenges. The validity proofs in the more general setting (when an adversary can collude with one of the servers) in our approach need to be non-interactive. We leave open the question of designing efficient zero-knowledge proofs for other predicates, that are compatible with local pan-privacy.

Local Pan-Privacy for Federated Analytics

Impact Statement

This paper presents work whose goal is to advance the field of Differentially Private Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

Apple and Google. Exposure notification privacypreserving analytics (ENPA) white paper. https://covid19-static.cdn-apple.com/ applications/covid19/current/static/ contact-tracing/pdf/ENPA_White_Paper. pdf, 2021.

Apple s Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 1(9), 2017.

Daniel Berend and Aryeh Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics & Probability Letters, 83(4):1254 1259, 2013. ISSN 01677152. doi: https://doi.org/10.1016/j.spl.2013.01. 023. URL https://www.sciencedirect.com/ science/article/pii/S0167715213000242.

Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan Mc Mahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 17, page 1175 1191, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349468. doi: 10. 1145/3133956.3133982.

Clement Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Journal of Privacy and Confidentiality, 12(1), Jul. 2022. doi: 10.29012/jpc.784. URL https://journalprivacyconfidentiality. org/index.php/jpc/article/view/784.

Karan Chadha, Junye Chen, John Duchi, Vitaly Feldman, Hanieh Hashemi, Omid Javidbakht, Audra Mc Millan, and Kunal Talwar. Differentially private heavy hitter detection using federated analytics. In 2nd IEEE Conference on Secure and Trustworthy Machine Learning, 2024. URL https://openreview.net/forum? id=1HF8t Lzt GX.

Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In Aditya Akella and Jon Howell, editors, 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, pages 259 282. USENIX Association, 2017.

Abraham de Moivre. Miscellanea analytica de seriebus et quadraturis. J. Tonson & J. Watts, 1730.

Persi Diaconis and Sandy Zabell. Closed Form Summation for Classical Distributions: Variations on a Theme of De Moivre. Statistical Science, 6(3):284 302, 1991. doi: 10.1214/ss/1177011699. URL https://doi.org/ 10.1214/ss/1177011699.

Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 17, page 3574 3583, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.

John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429 438, 2013. doi: 10.1109/FOCS.2013. 53.

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211 407, 2014.

Cynthia Dwork, Frank Mc Sherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265 284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy Rothblum, and Sergey Yekhanin. Pan-private streaming algorithms. In Proceedings of The First Symposium on Innovations in Computer Science (ICS 2010). Tsinghua University Press, 2010. URL https://www.microsoft. com/en-us/research/publication/ pan-private-streaming-algorithms/.

Ulfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 14, page 1054 1067, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450329576.

Vitaly Feldman, Audra Mc Millan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. Co RR, abs/2012.12803, 2020. URL https://arxiv.org/ abs/2012.12803. Preliminary version appears in FOCS 2021.

Local Pan-Privacy for Federated Analytics

Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious rams. J. ACM, 43(3):431 473, May 1996. ISSN 0004-5411. doi: 10.1145/233551.233553. URL https://doi.org/ 10.1145/233551.233553.

Christoph G. G unther. An identity-based key-exchange protocol. In Jean-Jacques Quisquater and Joos Vandewalle, editors, Advances in Cryptology EUROCRYPT 89, pages 29 37, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg.

Robert Helmer, Anthony Miyaguchi, and Eric Rescorla. Testing privacy-preserving telemetry with prio. https://hacks.mozilla.org/2018/10/ testing-privacy-preserving-telemetry-with-prio/, 2018.

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. volume 37 of Proceedings of Machine Learning Research, pages 1376 1385, Lille, France, 2015. PMLR.

Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5201 5212. PMLR, 18 24 Jul 2021. URL https://proceedings.mlr.press/ v139/kairouz21a.html.

Daniele Micciancio. Oblivious data structures: applications to cryptography. In Proceedings of the Twenty Ninth Annual ACM Symposium on Theory of Computing, STOC 97, page 456 464, New York, NY, USA, 1997. Association for Computing Machinery. ISBN 0897918886. doi: 10.1145/258533.258638. URL https://doi.org/10.1145/258533.258638.

Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. In Maurizio Lenzerini and Thomas

Schwentick, editors, Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 37 48. ACM, 2011. doi: 10. 1145/1989284.1989290. URL https://doi.org/ 10.1145/1989284.1989290.

Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Shai Halevi, editor, Advances in Cryptology - CRYPTO 2009, pages 126 142, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-03356-8.

Moni Naor and Vanessa Teague. Anti-persistence: history independent data structures. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC 01, page 492 501, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581133499. doi: 10.1145/380752.380844. URL https://doi.org/10.1145/380752.380844.

Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher Choquette, Peter Kairouz, Brendan Mcmahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of gboard language models with differential privacy. In Sunayana Sitaram, Beata Beigman Klebanov, and Jason D Williams, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track), pages 629 639, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.acl-industry. 60. URL https://aclanthology.org/2023. acl-industry.60/.

Yuanbo Zhang, Daniel Ramage, Zheng Xu, Yanxiang Zhang, Shumin Zhai, and Peter Kairouz. Private federated learning in gboard, 2023. URL https://arxiv.org/ abs/2306.14793.

Wennan Zhu, Peter Kairouz, Brendan Mc Mahan, Haicheng Sun, and Wei Li. Federated heavy hitters discovery with differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 3837 3847. PMLR, 2020.

Local Pan-Privacy for Federated Analytics

A. On the TV distance between Binomials

In this section, we will prove the following inequality.

Theorem 12. Let T 2 and p (0, 1

TV (Bin(T, p), Bin(T 1, p) + Bern(1 p)) = 2(1 2p) Tp

Tp Pr[Bin(T, p) = Tp ]

Proof. Note that Bin(T, p) = Bin(T 1, p) + Bern(p). Since we can couple Bern(p) and Bern(1 p) so that they agree with probability 2p, and differ by 1 otherwise, it follows that

TV (Bin(T, p), Bin(T 1, p) + Bern(1 p)) = (1 2p) TV (Bin(T 1, p), Bin(T 1, p) + 1).

We now write

2TV (Bin(T 1, p), Bin(T 1, p) + 1) =

m=0 | Pr[Bin(T 1, p) = m] Pr[Bin(T 1, p) = m 1]|

m=0 | T 1 m

pm(1 p)T 1 m T 1 m 1

pm 1(1 p)T m|

1 Tp(1 p) T m

pm(1 p)T m|p(T m) (1 p)m|

1 Tp(1 p) T m

pm(1 p)T m|p T m|

Letting f(m) denote p T m, we can thus write

2TV (Bin(T 1, p), Bin(T 1, p) + 1) = 1 Tp(1 p) E X Bin(T,p)[|f(X)|].

The value |f(X)| is the absolute deviation of a binomial random variable Bin(T, p) from its expectation. An exact formula for the mean absolute deviation of a binomial was given by de Moivre (1730) (see Diaconis and Zabell (1991) for a historical perspective on this formula). De Moivre showed that

E X Bin(T,p)[|X Tp|] = 2 Tp (1 p) Pr[Bin(T, p) = Tp ]

Tp p T p (1 p)T T p +1.

Plugging this bound gives the claimed equality. To prove the upper bound, we use Jensen s inequality: r

E X Bin(T,p)[|f(X)|] r

E X Bin(T,p)[f(X)2].

Now observe that

E X Bin(T,p)[f(X)2] = E X Bin(T,p)[(X p T))2]

Local Pan-Privacy for Federated Analytics

It follows that

2TV (Bin(T 1, p), Bin(T 1, p) + 1)

1 p(1 p)T ,

TV (Bin(T, p), Bin(T 1, p) + Bern(1 p)) (1 2p)

1 4p(1 p)T .

Berend and Kontorovich (2013) show that the bound from Jensen s inequality above (which is the only inequality in this proof) is tight up to a

2 factor for all p ( 1

T ). When p < 1

T , the mean absolute deviation is bounded by 2Tp and this is tight up to a factor of e. A symmetric bound holds for p > 1 1

B. Averages via Additively Homomorphic Encryption

We recall the definition of additively homomorphic encryption scheme. Several popular public-key encryption schemes or standard variants of those, including Paillier, RSA and El Gamal, and lattice-based schemes, satisfy these properties. Definition B.1. A public key encryption scheme as defined in Definition 2.7 is partially homomorphic over a group (G, ) if there is a p.p.t. algorithm Φ+( , , kpub) with the property that for any pair of valid ciphertexts c1, c2, Dec(Φ+(c1, c2, kpub)) = Dec(c1, kpriv) + Dec(c2, kpriv); and a p.p.t. algorithm Φ that takes a group element and a ciphertext, and outputs another ciphertext with the property that for any c and any α G, Dec(Φ (α, c, kpub), kpriv) = α Dec(c, kpriv).

We will omit kpub as an argument from Φ+ and Φ in the rest of the section and write Φ+(c1, c2, . . . , ck) to mean Φ+(c1, Φ+(c2, . . . , Φ+(ck 1, ck) . . .)).

Given an additively homomorphic encryption scheme, we will build on Algorithm 5 to design a locally pan-private algorithm for means. Recall that the histogram algorithm already gives us encryptions of indicators of |x|1 = j for each j {0, 1, . . . , k}. We will only need to redefine the Send to Server subroutine. Building on these, the client computes an encryption of the number of occurrences by multiplying each encrypted bit by the number of occurrences and summing together. Since only one of the coordinates is an encryption of 1, the sum is the number of occurrences. The client can then privatize by adding discrete Gaussian noise (Canonne et al., 2022; Kairouz et al., 2021) to the encrypted sum before sending to the server.

Algorithm 4 Averaging, Client Algorithm Require: k, T, Enc, Φ+, Φ , x, σ2

1: Send to Server 2: for i = 0,1,. . . ,k do 3: si = Φ (i, ci) 4: end for 5: r NZ(0, kσ2) 6: sk+1 = Enc(r) 7: Return Φ+(s0, , sk+1)

Upon receiving the reports from each client, the server simply decrypts and takes the average of the noisy reports. For an appropriate choice of σ is easy to show the following. Theorem 13. There is a computationally 0-locally pan-private for estimating the sum, which is (ε0, δ0)-local DP with

respect to the server. It estimates the sum with expected error O k q

δ 0/ε0 . Moreover, for any (ε, δ) (0, 1), there

is an σ such that the mechanism is (ε, δ)-aggregator DP, and has expected error O(k q

C. Proof of Theorem 6.2

We recall Theorem 6.2

Local Pan-Privacy for Federated Analytics

Theorem 6.2. Let ε (0, 1). Suppose that we have a set of algorithms Initialize, State, Out, and Est that define a computationally ε-locally pan-private streaming algorithm that estimates COUNTNONZERO on any set of inputs with error at most n/4, with probability 1 negl(n) for large enough n, and for up to T steps, using S bits of space. Then for any security parameter λ, we can define functions Key Gen, Enc, Dec that define a ( ε

T + T negl(λ))-secure public-key encryption scheme, where each of these operations runs in poly (λ, 2S) time. The scheme is rerandomizable in the sense of Definition 2.8, supporting up to T 1 rerandomizations.

Proof. We will use an encryption scheme very similar to the one in the proof above. For encryption, we will set xt to one for a random t {1, 2, . . . , T/2}, instead of setting x1 to one in the proof of Theorem 6.1. The encryption algorithm simulates the state transformation up to T/2 steps. Lemma 3.2 then allows us to argue the security of the encryption scheme. The decryption simulates the state transforms up to step T and the correctness proof is as before. The additional challenge is to argue that Enc, Dec run in polynomial time. This uses the fact that the result of applying the same randomized transform τ times, on a state of size S can be computed in time exp(O(S)) log(τ). We give details next.

As before, Key Gen will run the Initialize operation n times, and return the set of n client states, including the state s(i) 0 for each client, as a public key kpub, and the n server states as private key kpriv. Additionally, the parameter T will be included in both the keys. To define Enc, we consider the following randomized process. Given a bit b, we first create n independent random streams which are zero everywhere, except for a randomly picked ti {1, . . . , T/2}, where x(i) is b. We then simulate, for each i, T/2 steps of the locally pan-private algorithm on x(i) starting at state s(i) 0 to get s(i) T/2. Enc(b, kpub)

is then defined as (T/2, {s(i) T/2}n i=1). In general, valid ciphertexts will look like (t, {s(i) t }n i=1), for some t [T/2, T], and

some set of states {s(i) t }n i=1. Given such an encryption, the Dec algorithm will simulate, for each i, running the state transformations State (T t) times on s(i) t with input x(i) t+1 = 0, followed by running Out to generate a set of n messages. It then runs Est on the collection of n messages, and returns 0 if the answer is smaller than n/2, and 1 otherwise. As before, Φr on a ciphertext c = (t, {s(i) t }n i=1) (for t < T) will simulate, for each i, running the state transformations State on s(i) t with input x(i) t+1 = 0 to get an updated state s(i) t+1. The updated ciphertext c is then set to (t + 1, {s(i) t+1}n i=1).

As before, Dec(Enc(b, kpub), kpriv) comprises an exact simulation of running the COUNTNONZERO algorithm on n clients, where the input streams satisfy 1(x(i)) = b, followed by rounding the final estimate. Since the correct answer to COUNTNONZERO on these inputs is bn and the estimation algorithm has error n/4 with high probability, we conclude that the encryption scheme satisfies Dec(Enc(b, kpub), kpriv) = b except with negligible probability.

Now Lemma 3.2 implies that if the streaming algorithm was information-theoretically ε-locally pan-private, then the TV distance between the distributions Enc(0, kpub) and Enc(1, kpub) would be O(ε/

T). Mironov et al. (2009) show that computational (ε, δ)-indistinguishability (Definition 2.9) is equivalent the existence of distributions D0 and D1 such that D0 and D1 are O(ε/

T)-indistinguishable, and Db and Enc(b, kpub) are computationally indistinguishable. It follows that Enc(0, kpub) are Enc(1, kpub) are computationally (0, O(ε/

T + T negl(λ)))-indistinguishable.

The rerandomization, as before, is essentially simulating one step in the decoding. It is therefore immediate that for any valid ciphertext, Dec(Φr(c, kpub), kpriv) and Dec(c, kpriv) are running exactly the same simulation and thus are identically distributed. Finally, the security of the rerandomization follows once again from the hybrid argument: if we could distinguish iterated rerandomizations of 0 from those of 1, we would get a distinguisher that can learn the b from the local state at some later time step t.

Finally, we argue computational efficiency. The Enc and Dec algorithms need to simulate applying Stateτ on input 0τ, for a suitable τ, at most 2n times each. For a state space of size S, the transformation is defined by a stochastic matrix M of size 2S 2S. Applying this Markov kernel defined by M τ times is equivalent to applying M τ. Since computing M τ can be done in time poly(2S) log τ by repeated squaring, and thus we get the claimed run time for the scheme.

D. Deferred Pseudocode for algorithms

Local Pan-Privacy for Federated Analytics

Algorithm 5 Counter, Client Algorithm Require: k, T, Enc, Φr, x = x1, x2, . . . , x T .

1: Initialization 2: c0 = Enc(1); d0 = Enc(1) 3: for i = 1 : k do 4: ci = Enc(0); di = Enc(0) 5: end for

6: State Update 7: for t = 1 : T do 8: if xt = 0 then 9: for i = 0 : k do 10: ci = Φr(ci), di = Φr(di). 11: end for 12: else 13: c0 = Φr t(Enc(0)); d0 = Φr t(Enc(1)) 14: for i = 1 : k do 15: ci = Φr(ci 1); di = Φr(di 1) 16: end for 17: end if 18: end for

19: Send to Server 20: for i = 0 : k 1 do 21: vi = Φr(ci) 22: end for 23: vk = Φr(dk) 24: for i = 0 : k do 25: r = Ber(2/(eϵ0 + 1) 26: if r = 0 then 27: r = Ber(1/2) 28: if r = 1 then 29: vi = Φr T +1(Enc(0)) 30: else 31: vi = Φr T +1(Enc(1)) 32: end if 33: end if 34: end for 35: Return (v0, . . . , vk)

Local Pan-Privacy for Federated Analytics

Algorithm 6 COUNTNONZERO, Client Algorithm, Two-server model Require: T, Enc1, Φr1, Enc2, Φr2, x = x1, . . . , x T

1: Initialization 2: (s(1), s(2)) = Secret Share(0) 3: (π(1), π(2)) = Validity Proof(s(1), s(2)) 4: (c(1), c(2)) = (Enc1(s(1)), Enc2(s(2))) 5: (p(1), p(2)) = (Enc1(π(1)), Enc2(π(2)))

6: State Update 7: for t = 1 : T do 8: if xt = 1 then 9: (s(1), s(2)) = Secret Share(1) 10: (π(1), π(2)) = Validity Proof(s(1), s(2)) 11: (c(1), c(2)) = (Φt r1(Enc1(s(1))), Φt r2(Enc2(s(2)))) 12: (p(1), p(2)) = (Φt r1(Enc1(π(1))), Φt r2(Enc2(π(2)))) 13: else 14: (c(1), c(2)) = (Φr1(c(1)), Φr2(c(2))) 15: (p(1), p(2)) = (Φr1(p(1)), Φr2(p(2))) 16: end if 17: end for

18: Send to Server 19: r = Ber(2/(eϵ0 + 1) 20: if r = 0 then 21: r = Ber(1/2) 22: if r = 1 then 23: (s(1), s(2)) = Secret Share(0) 24: (π(1), π(2)) = Validity Proof(s(1), s(2)) 25: (c(1), c(2)) = (ΦT +1 r1 (Enc1(s(1))), ΦT +1 r2 (Enc2(s(2)))) 26: (p(1), p(2)) = (ΦT +1 r1 (Enc1(π(1))), ΦT +1 r2 (Enc2(π(2)))) 27: else 28: (s(1), s(2)) = Secret Share(1) 29: (π(1), π(2)) = Validity Proof(s(1), s(2)) 30: (c(1), c(2)) = (ΦT +1 r1 (Enc1(s(1))), ΦT +1 r2 (Enc2(s(2)))) 31: (p(1), p(2)) = (ΦT +1 r1 (Enc1(π(1))), ΦT +1 r2 (Enc2(π(2)))) 32: end if 33: end if 34: (c(1), c(2)) = (Φr1(c(1)), Φr2(c(2))) 35: (p(1), p(2)) = (Φr1(p(1)), Φr2(p(2))) 36: Return (c(1), p(1), c(2), p(2))