Local Pan-privacy for Federated Analytics
Authors: Vitaly Feldman
Audra McMillan
Guy N. Rothblum
Kunal Talwar
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Pan privacy
Primary area: social_aspects->privacy
TL;DR: Maintaining differential privacy under intrusion on the local state.

Abstract: 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 {\em local pan-privacy}, where privacy should be retained under repeated unannounced intrusions {\em 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.

Local Pan-Privacy for Federated Analytics
Vitaly Feldman "1
Audra McMillan
Guy N. Rothblumm Kunal Talwar"
Abstract
butions from the server computing the aggregate (Bonawitz et al., 2017; Conrigan- Gibbs and Boneh, 2017). Finally, the aggregate itself protects individual contributions by noise addition to provide a differential privacy guarantee.
Pan-privacy was proposed by (Dwork et al., 2010) as an approach to designing a private analyties sys- tem that retains its privacy properties in the face of intrusions that expose the system's '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 de- vice. We show that under reasonable constraints, dif-
In some applications, one may want to additionally protect against an attacker that has access to the device. For ex- ample, a computer in a public library may be accessed by one user, and later by another. In such case, 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 on- device intruder. We call this model local pan-privacy, as it aims to protect against an intrusion the local device, much as pan-privacy protects against an intrusion the server.
the goal of providing ferential 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.
We study locally pan-private algorithms for some fundamen- tal statistical tasks in 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 feature, may or may not occur. Thus, each device's 's input is a sequence of I'' 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 bit corresponding to whether on not the event occurred at any of the T steps. Such proto- col 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 trusted server, or where the secure aggregation system uses a two-server architecture as in PRIO (Corrigan-Gibbs and Boneh, 2017).
1. Introduction
Private federated telemetry systems allow for collection of aggregate statistics from a population, while ensuring 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 metries (Helmer al., 2018), collect operating system telemetry (Ding 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 ap- propriate times, taking part in a protocol that computes an aggregate. These protocols use eneryption to protect this data from an eavesdropper. In some cases, additional cryp- tographic protocols are used protect the individual contri-
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-uss algorithms in the local privacy model, based on the Laplace mechanism (Dwork
'quual contribution 'Apple, Cupertino, CA, USA. Correspon- dence to: Kunal Talwar <kttalarr@ appl..com>. <ktalwarrrpplle.co>>>>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Local Pan-Privacy for Federated Analyties
et al., 2006) and on RAPPOR (Erlingsson et al., 2014) re- spectively. We remark that these simple tasks underpin large number of private federated statistics, and can en- able 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.
In a rerandomizable encryption scheme, a ciphertext can be "rerandomized" (using only the public key) create new ciphertext encrypting the same plaintext, which is indistin- guishable from 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).
We show that local pan-privacy severely limited if we in- cntemmation-theoretttn differential privacy in the face of intrusions. Our lower bound shows that for the COUNTNONZERO task, the error of any algorithm must be VT 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.
sist on providing
At high level, this is achieved by maintaining 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 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 public- key 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- -an-private by keeping the state encrypted at all times and operating on the encrypted state. However, this is overkill: FHE schemes incur large space and time overhead, and in this work we strive to rely on more minimal and more efficient cryptographic primitives.
Theorem (Informal version of Theorem 9). Any locally pan- nan-private algorithm (for & for COUNTNONZERO on n devices, for large enough T, must incur additive error M MMVTT) even though local DP algorithm can estimate COUNTNONZERO with additive error 22 (Vn)).
We then show that under standard cryptographic assump- tions, local pan-pring pan-privacy can be ensured without this over- head. We present algorithms for all of the aforementioned problems, for both the single- and the two-server models, showing that local pan-privacy comes at no additional cost in the privacy-utility trade-off. Our protocols need a public- key encryption scheme, with 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 pan- privacy does not increase the complexity of the required assumptions. While we can define local pan-privacy broadly as a computational differential privacy guarantee against local intruder, our protocols actually provide stronger semantic security guarantee.
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 the state of the device before and after each update. In our example of 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 public-key encryption scheme necessary for the existence of an accurate locally pan- private algorithm for COUNTNONZERO.
Theorem 2 (Informal version of Theorem 10). Suppose that we have public-key encryption scheme that is reran- domizable. Then there is a streaming algoritim for COUNT- NONZERO in the single-server and in the two-server model with the following properties.
Theorem 3 (Informal version of Theorem 6.1). Suppose that we have a locally pan-private algorithm for COUNT- NONZERO that has additive error less than n/4 with high probability. Then we can build public key encryption scheme.
The on-device algorithu satisfies computational local pan-privacy; the on-device sequence of states on any pair of input streams are computationally indistinguish- able.
1.1. Related Work
The on-device state consists of 0(1) ciphertexts, and the device sends one message consisting of O(1) ci- phertexts.
Pan-privacy (Dwork et al., 2010) was proposed as an ap- proach to designing data analysis algorithms that do not maintain disclosive internal state. In particular, they main- tain 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 in- trusions on a user's device is common to several settings.
In the local and aggregator model of differential pri- vacy, the algorithm achieves privacy-utility trade-offs that are within constant factors of algorithms without the local pan-privacy, constraint.
2

---

Local Pan-Privacy for Federated Analyties
Examples include web browsing, where several popular browsers offer 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 infor- mation 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 represen- tation of 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 Secreey (Günther, 1990) addresses similar goal of protecting old communications from future intrusions.
between the two. We have a sequence of functions, where State; DxS - S is (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 21...., FT E D and an initial state 80 (we will sometimes omit so as an argument for brevity), let 3 = State; 8t-1) and State State( = (50, 81,- STT)...
An estimation algorithm is defined by additional functions Out and A, where Out maps 8r to 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 State; is E-locally pan-private if for any pair of streams x -I1....,22 FT and x' = II:...,, 27p, the state vectors State(x) and State(x') are e-indistinguishall.
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), restrict- ing 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 step T.! 1 (d) In some settings, one may only be in- terested 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.
Organization:
We present some preliminaries and definitions in Section 2. Section 3 presents lower bound for the information- theoretic privacy case. We present algorithms in the single- and two-server settings in Section 4 and Section 5 respec- tively. Section 6 shows that public-key cryptography is needed, and we conclude with some open problems in Sec- tion 7. For lack of space, some of the results, and some proof' are deferred to supplementary material.
2. Definitions and Preliminaries
We first recall the definition of differential privacy.
Definition 2.1 ( (e, J--Indisstiguishabblttt))) We say that two random variables Y and Y' on a finite set R are (e, 8) indistinguishable if for for every S C R.
Pr|y E S e Pr[Y' E 6, and Pr|Y' E S Pr +8.
When two r.v's are (E, iiiitiiiiinnullllllll, we will often call them e- inndisinguisshbb.
Definition 2.2 (Differential Privacy). A mechanism M : D + R is (e, (e.))-dijh 8)-differentially private if for any pair of neighboring datasets x, x', the random variables Mx) and (x') are (e, indistinnguiihabee.
The following definitions capture the standard notions of privacy for such algorithms.
Definition 2.4. We say an estimation algorithm is (c, locally differentially private if for any pair of streams x II...., 2T and x' = Iy....,Z'p the dis- tributions (ut((tat)(x)) and Out(State(x))) are (E, indistinguishable.
Here neighboring datasets typically means datasets that dif- fer in the input of one user.
We consider data stream x 21.... Fr, where each J; E 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 im- plicit) sets up the state on device, including the state so, and potentially some state on the server to allow coordination
Definition 2.5. We say an estimation algorithu is (e, aggregator differentially private for any pair of streams
'If were conceredd about the size of S, the many-msssages version of the model may be more powerful.
3

---

Local Pan-Privacy for Federated Analyties
and x', and any set of (n 1) streams {yl1 the distri- butions defined by Ei=1 Out (Statee)(()()) (St(Stat)(x) and Σ Out( (State(y(()) + (ut(State(xx)) are (E, indistinguishable.
encryption allows for an encrypted message be "reran- domized",, i.e. to be replaced by new eneryption of the same message, that is indistinguishable from new encryp- tion. Here and in the rest of the paper Φ," (.) denotes the I-fold composition Φ, (..((..)..()))))
We next define computational indistinguishability. A "se- curity" parameter À will control various quantities in these definitions. The adversary will be computationally bounded to be polynomial in A, and we say function in À is neg- ligible if it approaches zero faster than the inverse of any polynomial in A.
Definition 2.8. public key encryption scheme is reran- domizable if there is a finction (e, kpub) with the fol- lowing properties. For any m, m', and any t 2 O, let D, ''(Ennmmm kpub)) and c' de,'(Enc(mm kppb)), and let ē = (c, kipub) and è = D,(c', Kipub). Then Dec(c, Kpris) = Dec(E, Kyrio). Furthermore, the tuple (c, C) is computationally indistinguishable from (c,
Definition 2.6. Let {Da}a and {D'}> be two ensembles of distribution. We say that they are f(A) computationally indistinguishable for any non-uniform probabilistic poly- nomial time algorithm A,
Note that this definition implies that for any and any m, m', the distributions +, ",'(Enn (()nc(m)) and Φ ((Enc(mm) are com- putationally indistinguishable. We remark that we do not re- quire a rerandomized ciphertext to be indistinguishable from freshly generated one: it need only be indistinguishable from a rerandomized encryption of any different plaintext (for the same number of rerandomizations t).
Pr [A(2) m~D>
1] Pr [A(2)= 1]1 S f()). D'D'
When two ensembles are compuuaamta indistin- guishable for functionn f. we say that they are
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 version of this definition next.
computationally indistinguishable.
We use a public-key encryption scheme.
Definition 2.7. public key encryption scheme is defined by the following set of probabilistic polynomial time (p.p.t.) algorithms.
Definition 2.9 (Computational (e, oj-inndistinguisaabiity... Let Let (D>}> and {D'} be two ensembles of distribution. We say that they are computationally (c, 5) -indistinguisaable if for any non-uniform probabilistic polynomial time algo- rithu A,
Key Generation KeyGen(.) takes a security parameter in unary 1A and outputs a pair of keys (kipius kpub), each in {0.1)²
Pr - 5e. Dn
Pr = + 1(]) 2-D2
(X)
Encryption Enc(m, kpub) takes message and a public key kiput and outputs an encryption e {0,
When two ensembles of rv''s are computationally (e. 0)- indistinguishabile, we will often call them computationally e-indistinguishable.
Decryption
Dec(c, kprio) takes a ciphertext and a pri- vate key kprio and outputs a message m.
(Computational Local Pan-Pri- vacy,IND- CDP version). We say a streaming algoritim de- fined by a set of functions State; is computationally s-locally pan-private if for any pair of streams x = II...., DT and x' = x ,'i.... z/1- the state vectors State(x) and State(x') are computationally E-indistinguishable
Definition 2.10
These functions have the following properties:
Correctness Suppose that (Kipiio kpub) <- (eyGen(1>) for some X. Then any m E 13,, it holds that Dec(Enc(m, kypb), k equals m.
We recall some basic mechanisms that will be useful. We refer the reader to Dwork and Roth (2014) for their privacy proofs.
Semantic Security For any m,m', m', the encryptions Enc(m, kyub) and Enc(m', lipub) are computation- ally indistinguishabl.
Definition 2.11 (Randomized Response). Let E > 0. The randomized response mechanism 2RR, : {0, 1} + {0. 1] is s-DP mechanism defined as:
We rely on encryption schemes that allow re-encryption of an encrypted message. Informally, a rerandomizable
{ b
with probabilty iite
2RR = { 1 -
with probabilty Itc
"This is slightly weaker than the usual notion of rerandomizable encryption, as we allow and & (c, kpus) to be distinguishable. We show that this notion is necessary and sufficient for our pur- poses.
The following observation about implementing randomized response will be useful.
4

---

Local Pan-Privacy for Federated Analyties
Observation 5. Let be {0, and e > O. Then 2RR,(0 (b) can be implemented by outputting b with probability of -1 e441
1. We will prove the following theorem. Note that this means that the correlation between the message device sends, and 1 (x) is at most O(1/VT)
and outputting a random bit otherwise.
Theorem 8. Let A be an E-locally pan-private client-side algorithu for the COUNTNONZERO task comprising of the pair State and Out. Then there exists inputs x and x' such that 1 (xx = 1(x') = and
We will use the following lemma that says that any 2-input local randomizer is post-processing of a randomized re- sponse.
Lemma 2.1. (Kairouz et al., 2015) Let R: {0,1} + S be an e-DP local randomizer. Then there exists a post- processing function h {0, + S such that R())
TV (Out((ttate(() Out (ut(State(x()) S <(((e= 1)/VTet
((2RR.(0) and R1) = (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 a significant cost.
The following utility bounds for randomized response are standard (Feldman et al., 2020).
Theorem 6. Let Eo > O. Then for any bi....,by bn E 1), one can post-process their randomized responses {yi = 2RRe [b,)] to derive an estimate S of S = E, by such that
Theorem 9. Let A be s-locally pan-private algo- rithm run clients, and let S be any estimate of COUNTNONZERO(x x(! derived from the the outputs of A. For T 2 16e S has expected error MVTTT f(ee - 1)3).
cs ( (1+ (1+ (Iteray))
E[S]- = S; EIS -1s $0
Theorem 7. Let (5 E (0.1). 1). Then there is an Eo such that for any bj. by...., bn E {0. 13. the randomized responses {ys = 2RRco (b:)} are (E, DDP in the aggregator model. Further their sum can be post-processed to derive an esti-
Algorithm 1 fD
Require: State, Out, initial state su Input: b
3: if 0 then
mate á of == =Ebb, by such that
4: Return Out(State((O.....) 50))
5: else
B = 8; ElJs - 1118-11]: 51150y log /E).
6:
Select ~ Un form(
7: Set 2; = 1 and xy = 0 for t E (T) (t)
8: Return (St 80))
Let x = ZI...., be an input stream with each z; E {0, 13. We denote by 1(x) the predicate (max, o; = 1). For set of streams (x()) Ji the COUNTNONZERO value is defined as E, 1 (x(1)).
end if
We will now prove Theorem 8. We start by using the locally pan-private algorithm A to construct randomized function fo from {0. }} to the output space of the algorithm. On input '0', this algorithm runs A on the all 0's stream. On input 'I', it will put a 1 at a uniformly random place in the stream (with other xx, being 0) and run A on the resulting stream. Since 1(x) is different on these two streams, we expect this fo to behave differently enough on 0 and 1. We will argue that the local pan-privacy constraint prevents these distributions from being too far.
3. Lower Bound
In this section, we prove a lower bound showing that information-theorete local pan-privacy incurs a non-trivial cost on the achievable accuracy for the basic COUNT- NoNZERO task. Without local pan-privacy, this task can be solved easily. Each device maintains 1(x1:)), which can be done with single bit of state. Randomized response on this state after T' steps allows us to estimate COUNT- NONZERO with additive error Õ(1/s) in the aggregator DP setting (Theorem 7), and Ö( /n(1+ 0(y/((1
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 x xt's.
(<())))) in the local DP setting (Theorem 6). In contrast, we show that information-theoreee local pan-privacy entails polynomial dependence on T. This lower bound holds for the case when the input streams are restricted to have at most single '1'.
Lemma 3.1. Given an initial state so, there exists a post- processing function g such that
State ( 2i.::...,,,));;) so) =
(0:3:)))=g((__(( 9(2RR, (2R.
Each client receives a stream of inputs F,...., IT E {0, 1}. can communicate once to the server, and the goal of the server is to compute the number of clients such that 1 (xx) =
Proof. We will first show that if State is e-DP then for all t E [T] and any state 8t-1, State; 8t-1) is eDD..
5

---

Local Pan-Privacy for Federated Analyties
Let [7], 8t-1 S, and #f [0,1). Further, let (xr Me(TNN)) E (0, 10,1)--1 and {st)eetTMe ST-1, then
Algorithm 2 h
Require: g. Out
Input: E [T]
(1) 8t) Pr(Stater 81-1) 84)
3: Sample b uniformly at random from {b
{0, 1)7 | [b]] = m}.
Pr(State: (Iei 82 (T = 8t)
4: Return Out(g(b)).
Pr(State, (1/) 8-1) = 8t)
Pr Pr(State; s1- = 5pr)
II PE(TMM
Pr(Statey ( (1risr-1) sp- -1] = 5v)
Pr(State((m) (11.. Ft. Ft,..., ,T 80) = (81 8T)
4. The Single-Server Model
se Pr(Staaee (I1, (z1....., 2/ 2/y.... TT); 80) ($1 ST)
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 O.
Thus the map State,(;) can be viewed as local DP mechanism, and thus Lemma 2.1 implies that it can be written as a postprocessing of randomized response. Given I E [7] and 8:-1 E S, let h =(0,1 - S be such that for be E {0, 1]. State;(b; 8;-1 = h (2RB, (6)). Then we can define g(b1....,,br = (s1,..., ST) where
4.1. Counting Devices that have at least one occurrence
8t ht, (b.).
D
Let us first consider the problem of differentially privately computing the number of clients for which the sensitive event occurs least once. In Section 4.2 we will discuss how extend our approach to building histogram of the number of occurrences of the sensitive event.
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 is the randomized responses.
Lemma 3.2. Given any initial state so, there exists a post- processing function h such that (0) = h(Bin(T, +11))
We start by describing how the count will be stored and updated on device. At the beginning of the collection pe- riod, the client initializes the state to be an encryption of O. At each time step, the device updates the state. x; is 1, i.e. if the sensitive event has occurred in this time step, the device replaces the state with fresh encryption of 1, with appropriate number of rerandomization applied. If 2, is O, 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 fresh (reran- domized) encryption of 1, and rerandomization current encrypted value. Formally, the state after steps is compu- tationally indistinguishable from T,, (Enn 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 com- putationally indistinguishable from T T+ (Enc(()). We remark that for most practical cryptosytems, &, ((En((b) has the same distribution as Enc(b) so that we can opti- mize the algorithm by replacing the o, (Enc(b)) steps by Enc(b).
and fD(1) h(BinnT o11 + Ber( () Further, IV,T(OO),
S TV (Bin(T, ( Bin Bin cr+1 ( + Ber( cr+1
= =0 (6 1)
(3)
Tea
Proof. By Lemma 3.1, there exists 9 : 1)
ST such that State((z)....,. so) can be written as ((1) (xT)) Under our distribution on x conditioned on 6, the random variables x2 's are exchange- able, and thus conditioned on the count of 1s in 2RR (ar;) 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) a consequence of the data processing inequality. The second inequality is standard. For completeness, we give a proof in Appendix A.
Lemma 3.2 implics Theorem and completes the proof of our lower bound.
At the end of the collection period, the goal of the server
6

---

Local Pan-Privacy for Federated Analyties
E {0, 10,,,...; k 1} the number of devices with count |x|1 equal to i, well as the number of devices with count least k. While one could always set k = T, this generaliza- tion 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 de for each i, of the event [x1 2 i.
Algorithm 3 COUNTNONZERO, Client Algorithm
Require: T, Co, Enc, 9,, x 21,..,, FT
1: Initialization
2: =Enc(O)
3: State Update
4: for t T do
5: if x; 1 then
6:
= Φ, (Enc(1))
At the beginning of the collection period, the device initial- izes k + 1 counters to be an encryption of the initial his- togram, i.c. co Enc(1), C1 = Enc(O).... .....
7: else
8:
c= (c)
(nc(
9: end if
Additionally, it initializes do = E1c(1) and d; = Enc(O) for each = 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 co is set to be an Enc(O), and du is set (nc(1). At the end of T steps, the device has the de- sired values (No, ... 1%) in (Co, c1...., Ck-1, dx). since e encrypts [[x i) and da encrypts (|x 2 k). It uses randomized response on each of these to send the result to the server. We defer the full pseudocode to Algorithm
10: end for
11: Send to Server
12: r= Ber( e50
13: if then
14: r' Ber(1/2)
15: if r' = then
16:
= Φ, ++1 (0)
17:
else
18: c= Φr
T+ (Enc(L))
19: end if
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 (ui,..., v&k is 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 Since we run randomized response on each coordinate of the histogram, Theorem 6 and Theorem 7 implies that
20: else
21: c= (c)
22: end if
23: Return
to compute a differentially private estimate 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 11. Algorithm 5 is computationally O-locally pan-private, and Eo-local DP with respect to the server. It estimates the histogram with expected error (yr (1+ ( over, for any (c, E (0,1), there is an Eo such that the mechunism is (e, (-)-gg)regator DP, and has expected error Oly 0(y1og log / for each bucket count.
en (11 for each bucket count. More-
Theorem 10. Let eo > O. Suppose that each client i uses Algorithmm 3 on its input x.). Then the server can esti- mate COUNTNONZERO on imputs (x(0) y with expected error o (V (1+ (1++))000)) ( and En-local differential privacy. For any (c, E 1), there is an En such that the mechanism is (e,8)-ur Sagggregaao DP, and has expected error Oly log 1 /E). The client algorithm satisfies computational O-local pan-privacy.
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 count is larger than k. Alternativel,, the resulting av- erage can be viewed as average of truncation (at k) of the original counts. However using the estimate Σ, D i. Ki scales as O(k)). In Appendix B, we show that using an encryption scheme that has one additional property, we can reduce the error to Okk). matching the bound one would get in the central model.
4.2. Computing Histograms of the Number of Occurrences
j}l will result in error that
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 and the goal is to estimate for each
7

---

Local Pan-Privacy for Federated Analyties
5. The Two-Server Model
can then decrypt the shares with their private key and ag- gregate 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].
In this section we will address the two-server model of (Corrigan-Gibe Gibbs and Boneh, 2017), where the client sends secret-shares of their data to two servers. Any sensi- tive 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.
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 single- server 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 + 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.
In the two-server model, we often want to additionally pro- tect the server against malicious clients who seek poison the result by sending secret-shares of invalid reports. For example, instead of sending secret-sharing of 0 or 1, 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 construct the proof of validity, one needs to know the secret-shared data. To address this, we make use of 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 eneryptions. 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.
6. On the need for rerandomizable Public-key cryptography
We show that a rerandomizable public-key encryption scheme is necessary for computational O-local pan-privacy Recall that any locally pan-private algorithm also has an Initialize operation, that creates some shared state be- tween 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 80-
Theorem 6.1. Suppose that we have a set of algorithms Initialize, (State:) YT= Out, and Est that define a com- putationally O-locally pan-private streaming algorithm that estimates COUNTNONZERO on any set of inputs with er- ror at most n/4, with probability - -negl (n) for large enough n. Then for any security parameter and given a T = poly (A), we can define functions KeyGen, Enc, Dec that define a public-key encryption scheme, where each of these operations runs in poly (X) time. The scheme is reran- domizable in the sense of Desinition 2.8, supporting up to T 1 rerandomizations.
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 addi- tion 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 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 is an encryption of a fresh random field element after each update. This allows for non-interactive proofs, including the SNIPs (Corrigan-Gibee Gibbs and Boneh, 2017) that use Beaver triples. Each client sends the secret- shares of their contribution to the two servers. Each server
Proof. We will build an encryption scheme that can encrypt single bit b. The basic idea of the construction is to sim- ulate running the algorithm on n clients, where for each
client i, the first input in the stream (6) is set to b. The internal state of all the clients will comprise the encryp- tion. The decryption will simulate the state transformations given 2 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 (A), KeyGen will run the
8

---

Local Pan-Privacy for Federated Analyties
Initialize operation n times, and return the set of n client states, including the state ( for each client, as a public key kput, and the n server states as private key kiprén. Addi- tionally, the parameter will be included in both the keys. Given a bit b, Enc(b, kyub) will simulate for each i, one step of the locally pan- pan-private algorithm imput b starting
imply a public-key encryption scheme.
We next extend this argument to handle large class of e- locally pan-private algorithms for ε > 0. This result will apply to locally pan pan-private algorithms that use at most log- arithmic space, and which use the same state transformation function State at all time steps.
(6) at state 50 to derive a set of states o(4) The encryption will be defined (1, {s{ (0) 11 }==)). In general, valid cipher- texts will look like (t, {st (s)) (0) Ii=1), for some < T. and some set of states {s]") [0
Theorem 6.2. Let E E (0, Suppose that we have a set of algorithmss Initialize, State, Out, and Est that define a computationally E-locally pan-private streaming algorithm that estimates COUNTNONZERO 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 X, we can define functions ne))
Ji-1- Given such encryption, the Dec algorithm will simulate, for each i, running the state (6) with input - = 0, followed by running Out to generate set of n messages. It then runs Est on the collection of n messages, and returns 0 the answer is smaller than n/2, and oth- erwise. Finally, 2, on ciphertext c (t, (5( ( )==) (for t T) will simulate, for each i, running the state transfor-
transformations State Stater on st
any set of inputs with
KeyGen, Enc, Dec that define a (VT + T- +T secure public-key encryption scheme, where each of these operations runs in poly (X, 25) time. The scheme is reran- domizable in the sense of Definition 2.8, supporting up to T 1 rerandomizations.
(8) with input 4++1
get an updated state $441. The updated ciphertext c' is then set to (t+ 1, (+++1)==1) )=1)) Any input ciphertexts with 2 T are rejected by 4,.
mations State;+1 on St
It is easy to see that (bc(EEc kput), kpriu) comprises an exact simulation of running the COUNTNONZERO al- gorithm on clients on inputs 0,,,0,,... 0). followed by rounding the final estimate. Since the correct an- swer to COUNTNONZERO on these inputs is bn and the estimation algorithm has error n/4 with high proba- bility, we conclude that the eneryption scheme satisfies (Enc kpub), kprso)= = b except with negligible prob- ability.
We defer the proof to Appendix C. Note that if 7-1 is neg1 (A) and S is Ollo A), then the resulting public-key encryption scheme is secure.
7. Conclusions
In this work, motivated by privacy concerns on shared de- vices, we introduce the notion of local pan- cun-privacy. We show that while information theoretic local pan-privacy may be too strong requirement for basic telemetry tasks, compu- tational versions of this definition can be achieved without sacrificing on utility. We present algorithms for the funda- mental 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.
The security of the encryption follows from the com- putational local pan-privacy. Indeed if we had an effi- cient algorithm A that can distinguish Enc(O, kpu)) and Enc(1, kppb),, then by a standard hybrid argument, it can be used to distinguish State(O, 8o) and State(1, 8o), which violates the computational O-local pan- pan-privacy.
The rerandomization is essentially simulating one step in the decoding. It is therefore immediate that for any valid ciphertext, ( (c, kpwb), kprie) and Dec(c, kprie) 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 x from the local state at some later time step t.
Our work raises many natural question. Our lower bound in Theorem 8 relies on instances with at most single 1, and shows a /T gap in the error. We conjecture that this can be strengthened to an Q(T) gap when one allows the instances to have arbitrarily many 1s. While we have given algo- rithms 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 col- lude with one of the servers) in our approach need to be non-interacttve. We leave open the question of designing efficient knollee proofs for other predicates, that are compatible with local pan-privacy.
L
We note that the proof uses instances which have either zero or one 'I' in each input stream. Thus any accurate algorithm for histogram estimation implies one for COUNT- NONZERO with the same accuracy, and hence would also

---

Local Pan-Privacy for Federated Analyties
Impact Statement
Abraham de Moivre. Miscellanea analytica de seriebus quadraturis. J. Tonson & J. Watts, 1730.
This paper presents work whose goal 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.
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/117701 1699. URL https: //o::////o.... .oo.ooooo/oooooooooooooooooooooo 10.
References
Apple and Google. Exposure notification privacy-
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Proceedings of the 31st International Conference on Neural Informa- tion Processing Systems, NIPS' 17, page 3574-3583, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860966
preserving analytics (ENPA) white paper.
https:://covidl9-ttattt wan-:pccneeaeeeeeeaeea com/
applications/ cowind//cooo/l//// http:///////urree///ttttttt
contact- contact-tracing//dte http:///d/EEE/AAA/AEe Whitt_eaper..... pdf, 2021.
Apple's Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 1(9), 2017.
John C. Duchi, Michael Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pages 429-438, 2013. doi: 10.1 F0.1S00/0.S..01... 53.
Daniel Berend and Aryeh Kontorovich. A sharp estimate of the binomial mean absolute devia- tion with applications. Statistics & Probabil- ity Letters, 83(4):125411259 2013. ISSN 0167- 7152. doi:
Cynthia Dwork and Aaron Roth. The algorithmic founda- tions of differential privacy. Found. Trends Theor. Comput. Sci., 933-4)2211-409 2014.
023. URL htwp:tttpe///w...iiinneeeeeeeee com/ ssience/arrtcee//////17711111112
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelherg.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, 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 978 doi: 10.
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: wtt.wwwwwwooo.tco..o/// http://ntuu/rreeeerrcc///plllolo aaa--ppiaatesstrreammnnnggggggi-
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//pe.784. URL
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- prreacy-peeservngg ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Securiy, CCS '14, page 1054-1067, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450329576.
https: http:///pp/attccl/ee//////////
org/index. phtp
Karan Chadha, Junye Chen, John Duchi, Vitaly Feldman, Hanich Hashemi, Omid Javidbakht, Audra McMillan, and Kunal Talwar. Differentially private heavy hitter detection using federated analytics. In 2nd IEEE Con- ference on Secure and Trustworthy Machine Learning, 2024. URL https:tt////....... /tpen//////ee/evvieeeeeee net. forum? id=1HF8t
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hid- ing among the clones: A simple and nearly optimal analysis of privacy amplification by shufiling. CoRR, abs/2012. 12803, 2020. URL https: / /atss///arriii /ttaaxivvvorr abs / 10122.18803 Preliminary version appears in FOCS 2021.
Henry Corrigan-Gii Gibbss and Dan Bonch. Prio: Private, ro- bust, and scalable computation of aggregate statistics. In Aditya Akella and Jon Howell, editors, 14th USENIX Symposium on Networked Systems Design and Implemen- tation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, pages 259-282. USENIX Association, 2017.
10

---

Local Pan-Privacy for Federated Analyties
Oded Goldreich and Rafail Ostrovsky. Software pro- tection and simulation oblivious rams. J. ACM,
Schwentick, editors, Proceedings of the 30th ACM SIGMOD-SIGAACTSSIGAARI Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 37-48. ACM, 2011. doi: 10. URL https: /tle:://dooorggge
43(3):431-473, May 1996. ISSN 0004-5411. doi:
10.1145/23355512233333 URL https://doi.ors .233553.
1 1145/198928 10. N0.1145/1989288 .1999299.
Christoph G. Günther. An identity- based key-exchange pro- tocol. In Jean-Jacques Quisquater and Joos Vandewalle, editors, Advances in Cryptology - EUROCRYPT '89, pages 29-37, Berlin, Heidelberg, 1990. Springer Berlin Heidelberg.
Nya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Shai Halevi, editor, Advances in Cryptolggy CRYPTO 2009, pages 126-142. Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-644-03356-5
Robert Helmer, Anthony Miyaguchi, and Eric Rescorla. Testing privacy-preserving telemetry with prio. https://hacce wttps//m.............///////// http:rpppivaaaypprrrrrrvin--eeee 2018.
Moni Naor and Vanessa Teague. Anti-persistence: his- tory independent data structures. In Proceedings of the [bbjrryyThhrd Annual ACM Symposium on Theory of Computing, STOC '01, page 492-501, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581 doi: 10. 10.144554005,,,338444, URL https: http://ii.rgg/////////
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.
org/ 10. 11.............. 11111111755222 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 Ja- D Williams, editors, Proceedings of the 61st An- nual Meeting of the Association for Compulational Lin- guistics (Volume 5: Industry Track), pages 629-639, Toronto, Canada, July 2023. Association for Computa- tional Linguistics. doi: 10.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for feder- ated learning with secure aggregation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learn- ing Research, pages 5201-5212. PMLR, 18 24 Jul 2021. URI. hww.hhttss//ppreeeeeeee ngs ml .tt.s.sss.p..////// w139/kairroz22lahhtm html.
60. URL https:/ haapss//aalaaaae http///aaaaathloooooo/o www.aanthhwooooooo//222e22.22 acl hel-industry.co 60/.
Daniele Micciancio. Oblivious data structures: applica- tions cryptography. In Proceedings of the Twenty- Ninth Annual ACM Symposium on Theory of Comput- ing. STOC '97, page 456-464, New York, NY, USA, 1997. Association for Computing Machinery. ISBN 0897918886. doi: 10.1145/258533.255666 https://dol /tw.g//..100 1ttp:/...111//25580 1111115525555 258638.
Yuanbo Zhang, Daniel Ramage, Zheng Xu, Yanxiang Zhang, Shumin Zhai, and Peter Kairouz. Private federated learn- ing in gboard, 2023. URL https://arxiv..rrt abs/20 2006/2306.0 14793.
URL
Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li. Federated heavy hitters discovery with differential privacy. In International Conference on Artifi- cial Intelligence and Statistics, pages 3837-3847. PMLR, 2020.
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statis- tics on sketches. In Maurizio Lenzerini and Thomas

---

Local Pan-Privacy for Federated Analyties
A. On the TV distance between Binomials In this section, we will prove the following inequality.
Theorem 12. Let T 2 and (0. 2) Then
[Tpl
TV (Bin Bin 1, + Bern(1 p)) = -2p) Pr[Bin(T.p)) [Tyl]
Tp
Σ (1 - 2pp/ - p)T)
Proof. Note that Bin(T. Bin 1. + Bern(p). Since we can couple Bern(p) and Bern(1 p) so that they
agree with probability 2p, and differ by otherwise, it follows that
(V(Bin(T. p), Bin(T 1,p) + Bern(1 p)) = (1 2p) (B - 1,p), Bin 1,p) + 1).
We now write
T
(Bi 1,p), (T - 1,p) + 1) =
Pr (r[Bin(T-11) - = m] - Pr[Bin(T 1,p) m 1]1
m=U
T
pm (1 -p) T- (T' (T-1) 3m--111- - p)
-
m=0
T
(T))
pn (1 p) 7 - m p( m) (1 p)ml
Tp(1
m
M=0
T
Σ
nd (T p) mm
m pT ml
Tp(1 p)
m
Letting f(m) denote pT m, we can thus write
E (Bin - 1,p), Bin(T 1,p) + Tp(1 p) Bin(TTT.pp))
[I(())]-
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 historical perspective on this formula). De Moivre showed that
E
X - [-TTp] = Pr
Tp]]
X p-
2 T ((Tp)) [Tplp [Tp] --1r11++
Plugging this bound gives the claimed equality. To prove the upper bound, we use Jensen's inequality:
V E [[(()]] V Xin(TTT.
/ E [S(X)2]
(x~Bin(T.p)
Now observe that
E
[f(x)²]
E
[[X - pT))
X~Bin(T.pp)
X~Bin(TTp))
p(1 p)T.
12

---

Local Pan-Privacy for Federated Analyties
It follows that
2TV(Bin - 1,),, (i 1,p) + +1]= 1 V p(1 - -p)
so that
1
(V Bin 1.p) + Bern(1 - p)) S (1 2p)
4p
p)T
Berend and Kontorovich (2013) show that the bound from Jensen's 's inequality above (which is the only inequality in this proof) is tight up to a 2 factor for all p E ( ). When < T the mean absolute deviation is bounded by 27p and this is tight up to factor of e. A symmetric bound holds for p T
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 buttice-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 () if there a p.p.t. algorithm $ Dec(++(c1, C2 kpab)) Dec(c1, Kprio) + Dec(C2, kppsu); and a p.p.t. algorithm &, that takes group element and ciphertext, and outputs another ciphertext with the property that for any and any or E G, Dec P.. (ax, c, Ripub), kirii) * Dec(e, kprie).
with the property that for any pair of valid ciphertexts 0ı C2.
We will omit kpus as an argument from ++ and $ in the rest of the section and write (C1, C2,,.. C+ to mean (c (c2..... (c( (x)...)) (c))
Given an additively homomorphic encryption scheme, we will build on Algorithm design locally pan-private algorithm for means. Recall that the histogram algorithm already gives encryptions of indicators of |a: j for each j E {0, 10.1..... kj. 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 Averaging, Client Algorithm
Require: k Enc, 4+, 4., o²
1: Send to Server
2: for i 0,1......... do
3:
s; = =,= (1.
4: end for
5: r (0, k
6: 9841 Enc(r)
7: Return (50. . .k+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 easy to show the following.
Theorem 13. There is computationally O-locally pan-prine annpprivate for estimating the sum, which is (Eo, 6locl DP with respect the server. It estimates the sum with expected error O (R./n log /0o Moreover, for any (E, (0, there is an a such that the mechanism is (e, 8)aggrregtt DP, and has expected error O(k Vlog t/)..
C. Proof of Theorem 6.2
We recall Theorem 6.2
13

---

Local Pan-Privacy for Federated Analyties
Theorem 6.2. Let & 1). Suppose that we have set of algorithms
Staiiaaliz,,,tttaa Out, and Est that define computationally e-locally pan-private streaming algorithm that estimates COUNTNONZERO on any set of inputs with error at most n/4, with probability 1 negi(n) (n) for large enough T, and for up to T steps, using S bits of space. Then for any security parameter X, we can define functions KeyGen, Enc, Dec that define a ( ( + T negl(A)) secuue public-key encryption scheme, where each of these operations runs in poly (x. ) time. The scheme is rerandomizable in the sense of Defimition 2.8, supporting up to T 1 rerandomizutions.
Proof. We will use an encryption scheme very similar to the one in the proof above. For encryption, we will set 2, to one for a random E (1, T/2), instead of setting I1 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 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(r). We give details next.
As before, KeyGen will run the Initialize operation n times, and return the set of n client states, including the state sp for each client, as public key kpud. and the 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 independent random streams which are zero everywhere, except for randomly picked f. E
where x( is 6. We then
simulate, for each i, T/2 steps of the locally pan-private algorithm on x(9 starting at state si to get $1/2 Enc kpab)
(6)
is then defined as (7/2, ( (8=))===) In general, valid ciphertexts will look like (4, {o] >r=1), for some / E (7/2, T7, and (6)
some set of states {s, Ji= Given such an encryption, the Dec algorithm will simulate, for each i, rumning the state
(t) transformations State (T - t) times on 8t with input (.()) = 0, followed by running Out to generate a set of n messages. then runs Est on the collection of n messages, and returns 0 if the answer is smaller than n/22, and 1 otherwise. As before, +, on ciphertext c = (1, { (1) )i=) (for I. < T) will simulate, for each i, running the state transformations State on s) (8) (i) with input (1()) ++1 = to get an updated state $111 The updated ciphertext c' is then set to (t + 1, (2(2) 1
As before, Dec(Enc(b, Kppb), kprio) comprises an exact simulation of running the COUNTNONZERO algorithm on clients, where the input streams satisfy 1 (xx(1) = 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(bb,,
(iprse) = b except with negligible probability.
Now Lemma 3.2 implies that if the streaming algorithm was information-thhorrtiialll theoretically e-locally pan-private, then the TV distance between the distributions (nc(O, kput) and Enc A(pu)) would be O(e/vT /T). Mironov et al. (2009) show that computational (e, in-iiiiiiinnuussabllltt (Definition 2.9) is equivalent the existence of distributions Do and D1 such that Da and D1 O(s/VT)) -id)t-nniiitinguuhhabll. and Dj and Enc(b, kpub) computationally indistinguishable. It follows that Enc k are (1 kpub) are computationally (0, Oee/VT + T negl (A))) -indistinguishabbl...
The rerandomization, as before, is essentially simulating one step in the decoding. It is therefore immediate that for any valid ciphertext, (ec kipu), kprso) and Dec(c, kpräu) 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 7, at most 2n times each. For state space of size S, the transformation is defined by a stochastic matrix M of size 2 2.. Applying this Markov kernel defined by M T times is equivalent to applying M Since computing M can be done in time poly(2 log r by repeated squaring, and thus get the claimed run time for the scheme.
O
D. Deferred Pseudocode for algorithms
14

---

Local Pan-Privacy for Federated Analyties
Algorithm 5 Counter, Client Algorithm
Require: Enc, 4 x 21, T2...., FT.
I: Initialization
2: cp (1c ); do Enc(1)
3: = 1: k do
4: C Enc( d; = Enc(0)
5: end for
6: State Update
7: for t 1: T:::Tol do
8:
r; = then
9:
for i = 0: do
C: (c))). di (d))).
11:
end for
12:
else
13:
co Φ, (EnEC()());; do = &, (,n(Enn(1))
14:
for i = 1 k do
15:
= (,(())) 1): d; = (d:-1)
16:
end for
end
end for
Send to Server
for i 0:
1 do
21: U; (c:)
22: end for
23:
(dx)
24: for = 0: k do
25: r Ber(2/(e"5 + 1)
26:
if r = 0 then
(1/2)
28:
if r' then
29:
4 T+1 (Enc(0))
30:
else
31:
= Φ T+1 (Enc(1))
32:
end
33:
end
end for
35:
Return (Vo...., vk)
15

---

Local Pan-Privacy for Federated Analyties
Algorithm 6 COUNTNONZERO, Client Algorithm, Two-server model
Require: T, 1, r1 Enc2, 9,2, x = ,1,-..,,TT
Initialization
2: (s(t), s(2))
SecretShare())
3: (n(1), x(2) ValidityProof((" s(2)
4: (e(1) c(2)) (Enci(s(U), Enc2(s(2))
5: (p(), p()) = (Enci()()) (
6: State Update
7: for t = 1 T do
8: if ,4 = 1 then
(s(1), (s())s(2)) SecretShare(()
9:
(1()), x(2) = Va ValidityProof(()) )(t))
(c(1), c(2)) (0t (Bncc(s) & (Encg(s(()))
12:
(p(1) 2(2) (Enci (1) o (
13: else
(c(1), c(2) = (L)(((()), )
14:
15:
p()) = ((2))
(p(1((())), (p!2))
16: end if
17: end for
18: Send to Server
19: Ber(2/(e* + 1)
20: if then
r' Ber(1/2)
22: ifr r' then
23:
(s(1), (())
SecretSharee()
(1(1 (2(2) Validity ValidityProof(s!l s(2))
24:
(c(1) c(4) ( 1+ (Enci )), T (Ence(s(2)))
25:
(p(1) p(2) = ( (Ency (T (1))) $ d (Enc2(T
7
26:
else
(s(1) ((2) SecretShare(1)
28:
(n(1) (2)) Val ValidityProof(ft s(2)
29:
(c(1) c(2)) = (Ø (Enc & T+1
(Enc)(s(21))
30:
31:
(p(1) (2)) (Φ7) (Enci (T (1))
o 72
+1 (Ency(T(2)))
32:
end if
33: end if
34: (c()), cl2)) (4r) (c((((())) 2 (c2((())))
(p(), .(2)) p1 ()) ), 2 (p(2)))
36: Return (c(1), (1)) (2 (212)
16


Reviews:
[{"review_id": "k7LYtFzYGd", "reviewer": "Reviewer_5Xk2", "summary": "The paper introduces and examines the concept of *local pan-privacy*, which assumes that an adversary can eavesdrop on a local device’s internal memory. As a result, clients must ensure that their *internal states* remain secure. Under this constraint, the authors investigate (federated) analytics problems such as *count-nonzero* and *count-histogram* in a streaming setting, where each client observes a bit stream. The goal is to privately release either the total number of nonzero bits or a histogram of bit occurrences while maintaining local pan-privacy.  \n\nThe paper makes two key contributions. First, it establishes an information-theoretic lower bound, demonstrating that for the *count-nonzero* problem, local pan-privacy introduces an error proportional to $\\sqrt{T}$, where $T$ is the length of the bit stream. In contrast, standard local differential privacy (DP) does not impose this additional error. Second, the authors propose a *computational* pan-DP approach that circumvents this fundamental limitation. Their method is conceptually simple: it encrypts the internal memory, decrypts it when needed, and then applies a privatization mechanism before transmitting data to the server.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback.\n\n**Threat model**: We will clarify, motivate and illustrate the threat model. Our main motivating example is a shared device: a computer in a public library, a shared device in a home or other setting. The attacker is another user of the device, who can observe its state regularly. This is the same kind of attack model that private browsing modes in browsers are designed to address. A stolen device may also lead to an attack of this kind. In our schemes, it is important that only the public encryption (and re-randomization) key is held on the device: even if an attacker sees the entire internal state, it still cannot decrypt ciphertexts.\n\n**Tightness of lower bound**: Our lower bound instances have the property that each stream has at most a single ‘1’, and the lower bound can be shown to be tight for this case. We conjecture that in the general case where the stream may have multiple ‘1’s, the lower bound would be larger by a $\\sqrt{T}$ factor. We discuss this briefly in the Conclusions section, and will elaborate on this.", "claims_and_evidence": "The proofs of the theorems are correct to my best knowledge.", "methods_and_evaluation_criteria": "N/A since this is a theory paper.", "theoretical_claims": "The proofs of the theorems are correct to my best knowledge.", "experimental_designs_or_analyses": "N/A since this is a theory paper.", "relation_to_broader_scientific_literature": "The references seem to be adequate.", "essential_references_not_discussed": "The references seem to be adequate.", "other_strengths_and_weaknesses": "**Strengths:**  \nWhile the two key contributions of the paper—the information-theoretic lower bound and the computational upper bound—are relatively simple, the central message is intriguing. The paper highlights that by relaxing the definition of differential privacy from an information-theoretic to a computational setting, one can reduce the estimation error by a factor of $\\sqrt{T}$ in the count-nonzero problem. This result establishes an interesting distinction between information-theoretic and computational differential privacy.  \n\n**Weaknesses:**  \nAlthough the paper presents an interesting theoretical result, I have concerns about its practical applicability, particularly given the strong assumptions of the threat model. If an adversary has the capability to eavesdrop on internal states and memory, wouldn’t the public-key encryption system also be vulnerable to compromise? Related to that, I would appreciate if the authors can elaborate on the threat model in the framework.", "other_comments_or_suggestions": "See the above comments.", "questions_for_authors": "Is the information-theoretic lower bound established in Theorem 9 tight in an information-theoretic sense? In other words, does there exist an information-theoretic pan-privacy scheme that consistently achieves this error for any input stream? Note that the mechanism constructed in Lemma 3.1 is *not* $\\varepsilon$-local DP, as in the worst-case scenario, every bit in $x_1, \\dots, x_T$ could change. Consequently, while Theorem 9 provides a valid lower bound, it remains unclear whether it is a tight one.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KpzmVvvQO6", "reviewer": "Reviewer_BCZA", "summary": "This paper introduces a privacy protection model termed local pan-privacy, aiming to address privacy leakage issues in federated analytics when local devices are subject to continuous intrusions. The authors first theoretically prove that achieving pan-privacy in an information-theoretic sense leads to estimation errors at least  times larger than traditional local differential privacy methods. To overcome this limitation, they propose a computationally secure Local Pan-Privacy model based on rerandomizable public-key encryption schemes. Specifically, this method protects privacy by storing encrypted states locally, updating the encrypted state via rerandomization, and using the randomized response mechanism to securely transmit ciphertexts to the server. This design enables accurate computation of the number of devices experiencing a particular event (COUNTNONZERO) and the histogram of event occurrences, without significant loss in practical performance. Moreover, the proposed approach is effective in both single-server and two-server aggregation settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback.\n\n**Choice of tasks**: In this work, we have focused on the simplest and most natural tasks in this new model. These histogram-type tasks have also been used in federated analytics applications to enable a larger class of statistical tasks. To our knowledge, nearly all implemented federated analytics systems build on histograms as the basic building block. We leave to future work more complex tasks, and believe that the techniques in this work would be useful for other tasks as well.\n\n**The need for PKC**: We will discuss the implications of Theorem 3 in more detail. Constructing public-key crypto (PKC) from symmetric key encryption of hashing is a major and long-standing open problem in cryptography, and it is widely believed that PKC is \"harder\" to build. Theorem 3 implies that constructing accurate algorithms for countnonzero under local pan-privacy from symmetric-key crypto or hashing is at least as hard as constructing PKC from these primitives (and thus at the very least it requires resolving a central and long-standing open question in crypto).", "claims_and_evidence": "(1)Overall, both the theoretical claims and methods put forward in this paper are supported by clear and rigorous mathematical proofs, and thus enjoy a relatively high level of credibility at the theoretical level. Nevertheless, the “no additional cost” mentioned in the paper, despite being proven at the theoretical level, lacks sufficient support from real-life scenarios or experiments and awaits further verification.\n(2)The paper clearly expounds on the deficiencies of the existing local differential privacy and traditional pan-privacy methods in the scenario of “privacy protection when client devices in federated analytics are subject to continuous intrusions”, and puts forward an improved scheme based on cryptography. However, the authors did not clearly present experimental verification.\n(3)The theoretical derivation and proof process in the paper are logically clear, and no obvious errors or derivation problems have been found. For example, it is proved in the paper that the cost of pan-privacy under the information theory is relatively high, while the local pan-privacy based on cryptography has no significant overhead.\n(4)The paper does not include any experimental section.\nThe supplementary materials provide proofs for Theorem 12, Theorem 13 and Theorem 6.1. Meanwhile, the pseudocodes of Algorithm 4, Algorithm 5 and Algorithm 6 are also supplemented. These are mainly used to support Theorem 8, Theorem 9, Lemma 3.1 and Lemma 3.2.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "(1)The local pan-privacy proposed in this paper is an innovative extension based on the classic differential privacy and the existing pan-privacy theories. Meanwhile, this research also ingeniously applies the existing rerandomizable public-key encryption schemes in the field of cryptography. The application of such schemes is a further innovative integration based on the existing cryptographic theories and practices like PRIO.\n(2)The scope and relevance of the citations in the paper are currently good. No work that is highly relevant to the paper has been found to be uncited yet.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "(1)This paper demonstrates strong theoretical originality and plays an important role in promoting the development of the privacy field. This paper demonstrates strong theoretical originality and plays an important role in promoting the development of the privacy field.", "other_comments_or_suggestions": "no", "questions_for_authors": "(1)The paper mainly focuses on some simple statistical tasks, such as the COUNTNONZERO mentioned. But does it also have applicability or limitations in more complex statistical or machine learning tasks?\n(2)Theorem 3 states that exact local pan-privacy algorithms require a public key encryption scheme. Does this rule out the possibility of using lightweight cryptography, such as symmetric encryption or hash functions? Or does it imply that public-key encryption is the only viable option or the best choice in the context of the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DX6zHTtUCl", "reviewer": "Reviewer_DG5N", "summary": "This paper explores three fundamental problems within the framework of local pan differential privacy: estimating the number of non-zero entries, calculating the mean, and constructing histograms. The authors begin by establishing a lower bound for counting non-zero entries, which includes a $\\sqrt{T}$ factor, indicating that local pan privacy may be significantly more challenging than local differential privacy. They then showed how to remove this dependence by relaxing to computational local pan privacy: they proposed an algorithm leveraging rerandomizable public-key encryption, and extended the result to other two problems. Finally, they presented a theorem suggesting that the rerandomizable public-key encryption scheme is necessary for computational 0-local pan-privacy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback, and for pointing out the typos in Thm 7, Thm 6.1, and in Algorithm 6. We will fix those in the updated version.\n\n**Public-key vs. FHE**: the existing implementations of these primitives have very large gaps. Indeed the public-key encryption based aggregation schemes are already used, both in the single-server and the two-server setting. These schemes in practice incur a fairly small overhead in run-time and communication and our algorithms requiring re-randomization at each step would add a small additional overhead. FHE implementations currently incur very large overheads, not just for computation but also for communication. E.g. in Google’s FHE library, the encryption of a single bit is nearly 3kB, compared to 256 bytes for encrypting a field element that are currently used in HPKE. From a computational point of view, our algorithms just add re-randomization operations at each step, which are relatively inexpensive. We will add a more detailed discussion of these costs in an updated version. We also remark that our algorithms effectively implement the standard algorithms for counting and histogram estimation in the local DP model and thus incur no overhead in terms of utility. Indeed for these applications, these algorithms are known to be optimal in terms of privacy-utility trade-offs.", "claims_and_evidence": "The proofs presented in the paper are clearly articulated and well-structured, effectively supporting the authors' claims.", "methods_and_evaluation_criteria": "Yes, estimation error serves as the standard metric for assessing the performance of a differentially private algorithm.", "theoretical_claims": "I reviewed all the proofs and found no significant flaws.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper introduces algorithms for several fundamental problems, which could serve as foundational components for addressing othertasks within the realm of local pan differential privacy.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written, making it accessible to non-experts.\n\n2. The results are intriguing. Although the techniques used to prove them are not particularly sophisticated, they effectively illustrate the fundamental limits of pan privacy within the local model.\n\nWeakness:\n\nThe paper lacks experimental results. While this is acceptable for a theoretical study, including simulations or even a basic complexity analysis (e.g., time and space considerations) could enhance the demonstration of the proposed methods' advantages over fully homomorphic encryption (FHE).", "other_comments_or_suggestions": "1. In Theorem 7, it appears that one $\\delta$ is missing -- the aggregator algorithm should be $(\\varepsilon,\\delta)$-DP.\n\n2. In the \"if r = 0\" part of Algorithm 6, the superscripts are incorrect -- you wrote $t$ instead of $T$. Additionally, should it be $T+1$ as in Algorithm 3?\n\n3. In Theorem 6.1, should the number of allowed rerandomizations be $T - 1$? Because after creating the ciphertext using $x_1$, there are only $T-1$ transitions left.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a model that combines the restrictions of local privacy (where data is distributed among devices and there is no trusted central server), and pan privacy (where the state of a device can be observed by an intruder). The main results are an information theoretic lower bound, and an upper bound against computationally bounded adversaries using cryptographic techniques.

The model is intriguing. The results are a good first step, although perhaps a little too simple in terms of techniques.
Decision: Accept (poster)