Patent Publication Number: US-10776242-B2

Title: Collection of sensitive data—such as software usage data or other telemetry data—over repeated collection cycles in satisfaction of privacy guarantees

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Patent Application No. 62/442,927, filed on Jan. 5, 2017, which is hereby incorporated by reference in its entirety. 
    
    
     BACKGROUND 
     “Telemetry data” refers to collecting information describing the operation of a remote system, and transmitting it to a central point for analysis and/or long-term storage. The systems whose operation telemetry data describes can be of a variety of types, including hardware systems and software systems. For example, telemetry data for an access control door hardware system may include the number of times the door was unlocked during a particular time period. The telemetry data for a software system may reflect the number of times an operating system was booted or an application was launched during a particular time period, or the portion of that period of time for which the operating system or app was running. 
     SUMMARY 
     This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This summary is not intended to identify key factors or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. 
     A facility for reporting on one or more original values on behalf of each of a plurality of users—each original value falling within a domain partitioned into a plurality of segments of uniform size—is provided. For each of the plurality of users, the facility (a) randomly selects an upward-rounding window size that is smaller than the segment size; (b) for each source value in a domain, randomly determines a mapping of each segment of the domain to a segment identifier value; (c) determines an original value for the user; (d) adds the upward-rounding window size to the original value determined for the user to obtain a window-augmented original value; (e) identifies a segment containing the window-augmented original value; (f) uses the determined mapping to identify a segment identifier value mapped-to from the identified segment; and (g) transmits a reporting communication on behalf of the user that reports a value based at least in part on the identified segment identifier value. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a data flow diagram showing private data collection performed using a local model of differential privacy. 
         FIG. 2  is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility operates. 
         FIG. 3  is a flow diagram showing a process performed by the facility in some examples to transform a user&#39;s private values into the response that is communicated to the data collector for the user. 
     
    
    
     DETAILED DESCRIPTION 
     1. Problem Statement 
     Differential privacy (DP) is a mechanism for enforcing privacy guarantees against the collection of private data. In the context of telemetry collection, it is common to use algorithms that exhibit differential privacy in the local model, also sometimes called randomized response model, γ-amplification, or FRAPP.  FIG. 1  is a data flow diagram showing private data collection performed using a local model of differential privacy. Randomized algorithms    ε   110  are invoked on each user&#39;s device to turn user&#39;s private value x i    101 - 104  into a response z i    121 - 124  that is communicated  130  to a data collector—such as via the Internet or another network. The randomized algorithms have the property that the likelihood of any specific algorithm&#39;s output varies little with the input, thus providing users with plausible deniability. Guarantees offered by locally differentially private algorithms, though very strong in a single round of telemetry collection, quickly degrade when data is collected over time. This is a very challenging problem that limits the applicability of DP in many contexts. 
     In telemetry applications, privacy guarantees typically need to hold in the face of continuous data collection. Ú. Erlingsson, V. Pihur, and A. Korolova. RAPPOR: randomized aggregatable privacy-preserving ordinal response; in CCS, pages 1054-1067, 2014, proposed a framework based on “memoization” to tackle this issue. Erlingsson&#39;s techniques allow one to extend single round DP algorithms to continual data collection and protect users whose values stay constant or change very rarely. The key limitation of Erlingsson is that its approach cannot allow for even very small but frequent changes in users&#39; private values, making it inappropriate for collecting counter data. 
     To overcome these deficiencies of conventional approaches to enforcing a specified level of privacy in data collection, the inventors have conceived and reduced to practice a software and/or hardware facility (the “facility”) that provides mechanisms with formal privacy guarantees in the face of continuous collection of counter data. These guarantees are particularly strong when users&#39; behavior remains approximately the same, varies slowly, or varies around a small number of values over the course of data collection. 
     In some examples, the facility uses simple 1-bit response mechanisms in the local model of DP for single-round collection of counter data for mean and histogram estimation. 
     In some examples, the facility uses a rounding technique called “α-point rounding” that allows memoization to be applied in the context of private collection of counters while avoiding substantial losses in accuracy or privacy. The facility provides rigorously defined privacy guarantees when the data is collected continuously for an arbitrarily long period of time. 
     1.1 Preliminaries and Problem Formulation 
       FIG. 2  is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility operates. In various embodiments, these computer systems and other devices  100  can include server computer systems, desktop computer systems, laptop computer systems, netbooks, mobile phones, personal digital assistants, televisions, cameras, automobile computers, electronic media players, etc. In various embodiments, the computer systems and devices include zero or more of each of the following: a central processing unit (“CPU”)  201  for executing computer programs; a computer memory  202  for storing programs and data while they are being used, including the facility and associated data, an operating system including a kernel, and device drivers; a persistent storage device  203 , such as a hard drive or flash drive for persistently storing programs and data; a computer-readable media drive  204 , such as a floppy, CD-ROM, or DVD drive, for reading programs and data stored on a computer-readable medium; and a network connection  205  for connecting the computer system to other computer systems to send and/or receive data, such as via the Internet or another network and its networking hardware, such as switches, routers, repeaters, electrical cables and optical fibers, light emitters and receivers, radio transmitters and receivers, and the like. While computer systems configured as described above are typically used to support the operation of the facility, those skilled in the art will appreciate that the facility may be implemented using devices of various types and configurations, and having various components. 
     In some cases, the facility operates in an environment in which there are n users, and each user i at time t has a private (integer or real) counter with value x i (t)∈[0,m]. A data collector collects these counter values {x i (t)} i∈[n]  at each time stamp t to do statistical analysis, such as by applying mean, median, maximum, and/or other aggregation functions. For telemetry analysis, for example, understanding the mean and the distribution of counter values (e.g., app usage) can be very important to IT companies. 
     Local model of differential privacy (LDP). In some cases, users require formal privacy guarantees before they are willing to communicate their values to the data collector. Hence, a DP model that first collects all users&#39; data and then injects noise in the analysis step, is not applicable in our setup. In this work, we adopt the local model of differential privacy, where each user randomizes private data using a randomized algorithm (mechanism)   locally before sending it to data collector. 
     Definition 1. A randomized algorithm  : →  is ε-locally differentially private (ε-LDP) if for any pair of values v, v′∈  and any subset of output  ∈ , we have that
 
 Pr [ ( v )∈ S ]≤ e   ε   ·Pr [ ( v ′)∈ S ]  (1)
 
     LDP formalizes a type of plausible deniability: no matter what output is released, it is approximately equally as likely to have come from one point v∈  as any other. 
     Statistical Estimation Problems. 
     In various examples, the facility is focused on two estimation problems: 
     Mean estimation: For each time stamp t, the data collector obtains an estimation {circumflex over (σ)}(t) for 
               σ   ⁡     (       x   →     t     )       =       1   n     ·       ∑     i   ∈     [   n   ]                 ⁢         x   i     ⁡     (   t   )       .               
The error of an estimation algorithm for mean is defined to be max {right arrow over (x)}     t     ∈[m]     n   |{circumflex over (σ)}({right arrow over (x)} t )−σ({right arrow over (x)} t )|—in other words, a worst case analysis. We use σ(t) to mean σ({right arrow over (x)} t ) for a fixed input {right arrow over (x)} t .
 
     Histogram estimation: Suppose the domain of counter values is partitioned into k buckets (e.g., with equal widths), and that a counter value x i (t)∈[0,m] can be mapped to a bucket number v i (t)∈[k]. For each time stamp t, the data collector estimates frequency of 
                 v   ∈     [   k   ]       :       h   t     ⁡     (   v   )         =         1   n     ·          {       i   :       v   i     ⁡     (   t   )         =   v     }            ⁢           ⁢   as   ⁢           ⁢           h   ^     t     ⁡     (   v   )       .             
The error of a histogram estimation is measured by max v∈[k] |ĥ(v)−h t (v)|. Again, this reflects a worst case analysis.
 
     1.2 Repeated Collection and Overview of Privacy Framework 
     Privacy Leakage in Repeated Data Collection. 
     Although LDP is a very strict notion of privacy, its effectiveness decreases if the data is collected repeatedly. If counter values of a user i are collected for T time stamps by executing an ε-LDP mechanism   independently on each time stamp, x i (1) x i  (2) . . . x i (T) can be only guaranteed indistinguishable to another sequence of counter values, x i ′(1) x i ′(2) . . . x i ′(T), by a factor of up to e T·ε , which may in some cases be regarded as too large to be reasonable as T increases. 
     Hence, in applications such as telemetry, where data is collected periodically or continuously, privacy guarantees provided by an LDP mechanism for a single round of data collection are often not sufficient. A formalized privacy guarantee to enhance LDP for repeated data collection is described below in Section 3. Intuitively, the facility ensures that every user blends with a large set of other users who have very different behaviors. 
     Framework Overview. 
     In some examples, the facility operates in accordance with a framework for mean and histogram estimation that has four main components:
         1-bit mechanisms that provide local ε-LDP guarantees and good accuracy for a single round of data collection are described in Section 2.   An α-point rounding scheme to randomly discretize users private values prior to applying memoization to conceal small changes, while keeping the expectation of discretized values intact is described in Section 3.   Memoization of discretized values using the 1-bit mechanisms to avoid privacy leakage from repeated data collection is described in Section 3.   Output perturbation (also known as “instantaneous noise”) to protect exposing the transition points due to large changes in user&#39;s behavior and attacks based on auxiliary information is described in Section 4.       

       FIG. 3  is a flow diagram showing a process performed by the facility in some examples to transform a user&#39;s private values into the response that is communicated to the data collector for the user. The facility begins with user i&#39;s private value x for time t, x i (t)  301 . The facility subjects value  301  to an α-point rounding scheme  310  to randomly discretize users private values prior to applying memoization to conceal small changes, while keeping the expectation of discretized values intact. This produces a rounded value {circumflex over (x)} i (t)  311 . To value  311 , the facility performs memoization  320  using the 1-bit mechanisms to avoid privacy leakage from repeated data collection to obtain memorized value b i (t)  321 . The facility subjects value  320  to output perturbation  330  to obtain perturbed value b i ′(t)  331 , which the facility communicates as value z i  to the data collector. 
     Those skilled in the art will appreciate that the acts shown in  FIG. 2  may be altered in a variety of ways. For example, the order of the acts may be rearranged; some acts may be performed in parallel; shown acts may be omitted, or other acts may be included; a shown act may be divided into subacts, or multiple shown acts may be combined into a single act, etc. 
     2. Single-Round LDP Mechanisms for Mean and Histogram Estimation 
     We first describe our 1-bit LDP approach to mean and histogram estimation. This approach is applied to single-bit counters each supplied by a single user. Some aspect of this 1-bit LDP approach are based on one or more of J. C. Duchi, M. J. Wainwright, and M. I. Jordan, Local privacy and minimax bounds, Sharp rates for probability estimation, in  NIPS , pages 1529-1537, 2013; J. C. Duchi, M. I. Jordan, and M. J. Wainwright, Local privacy and statistical minimax rates, in  FOCS , pages 429-438, 2013; J. C. Duchi, M. J. Wainwright, and M. I. Jordan, Minimax optimal procedures for locally private estimation, in CoRR, abs/1604.02390, 2016; and R. Bassily and A. D. Smith, Local, private, efficient protocols for succinct histograms, in  STOC , pages 127-135, 2015. 
     2.1 1-Bit Mechanism for Mean Estimation 
     Collection Mechanism. 
     1 BitMean: When the collection of counter x i (t) at time t is requested by the data collector, each user i (that is, the computing device operating on behalf of user i) sends one bit b i (t), which is independently drawn from the distribution: 
     
       
         
           
             
               
                 
                   
                     
                       b 
                       i 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             , 
                             
                               
                                 
                                   with 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   probablity 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     1 
                                     
                                       
                                         e 
                                         ɛ 
                                       
                                       + 
                                       1 
                                     
                                   
                                 
                                 + 
                                 
                                   
                                     
                                       
                                         x 
                                         i 
                                       
                                       ⁡ 
                                       
                                         ( 
                                         t 
                                         ) 
                                       
                                     
                                     m 
                                   
                                   · 
                                   
                                     
                                       
                                         e 
                                         ɛ 
                                       
                                       - 
                                       1 
                                     
                                     
                                       
                                         e 
                                         ɛ 
                                       
                                       + 
                                       1 
                                     
                                   
                                 
                               
                               ; 
                             
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                             
                               otherwise 
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Mean Estimation. 
     Data collector obtains the bits {b i (t)} i∈[n]  sent by n users and estimates σ(t) as 
     
       
         
           
             
               
                 
                   
                     
                       σ 
                       ^ 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     
                       m 
                       n 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                       ⁢ 
                       
                         
                           
                             
                               
                                 b 
                                 i 
                               
                               ⁢ 
                               
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                                 · 
                                 
                                   ( 
                                   
                                     
                                       e 
                                       ɛ 
                                     
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                             - 
                             1 
                           
                           
                             
                               e 
                               ɛ 
                             
                             - 
                             1 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     For the 1-dimensional mean estimation, Laplace mechanism is asymptotically optimal for the mini-max error. However, the communication cost per user in Laplace mechanism is Ω(log m) bits, and our experiments show it also leads to larger error compared to our 1-bit mechanism. We prove following results for the above 1-bit mechanism. 
     Theorem 1. 
     For single-round data collection, the mechanism 1 BitMean in (2) preserves ε-LDP for each user. Upon receiving the n bits {b i (t)} i∈[n]′  the data collector can then estimate the mean of counters from n users as {circumflex over (σ)}(t) in (3). With probability at least 1−δ, we have 
     
       
         
           
             
                
               
                 
                   
                     σ 
                     ^ 
                   
                   ⁡ 
                   
                     ( 
                     t 
                     ) 
                   
                 
                 - 
                 
                   σ 
                   ⁡ 
                   
                     ( 
                     t 
                     ) 
                   
                 
               
                
             
             ≤ 
             
               
                 m 
                 
                   
                     2 
                     ⁢ 
                     n 
                   
                 
               
               · 
               
                 
                   
                     e 
                     ɛ 
                   
                   + 
                   1 
                 
                 
                   
                     e 
                     ɛ 
                   
                   - 
                   1 
                 
               
               · 
               
                 
                   
                     log 
                     ⁢ 
                     
                       2 
                       δ 
                     
                   
                 
                 . 
               
             
           
         
       
     
     2.1A Proof of Theorem 1 
     Theorem 2.1. 
     The algorithm 1 BitMean is ε-DP of every user. 
     Proof. 
     Observe that each user contributes only a single bit b i  to data collector. By formula (11) the probability that b i =0 varies from 
               1       e   ɛ     +   1       ⁢           ⁢   to   ⁢           ⁢       e   ɛ         e   ɛ     +   1             
depending on the private value x i . Similarly, the probability that b i =1 varies from
 
               1       e   ɛ     +   1       ⁢           ⁢   to   ⁢           ⁢       e   ɛ         e   ɛ     +   1             
with x i . Thus the ratios of respective probabilities for different values of x i  can be at most e ε .
 
     Recall the definition of {circumflex over (σ)}. 
     
       
         
           
             
               
                 
                   σ 
                   = 
                   
                     
                       1 
                       n 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         i 
                       
                       ⁢ 
                       
                         x 
                         i 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     Lemma 3. 
     {circumflex over (σ)}(t) in Equation (3) is an unbiased estimator for σ. 
     Proof. 
     Observe that 
     
       
         
           
             
               
                 
                   
                     E 
                     ⁡ 
                     
                       [ 
                       
                         
                           σ 
                           ^ 
                         
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                       ] 
                     
                   
                   = 
                     
                   ⁢ 
                   
                     
                       m 
                       n 
                     
                     · 
                     
                       
                         
                           e 
                           ɛ 
                         
                         + 
                         1 
                       
                       
                         
                           e 
                           ɛ 
                         
                         - 
                         1 
                       
                     
                     · 
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               
                                 [ 
                                 n 
                                 ] 
                               
                             
                           
                           ⁢ 
                           
                             E 
                             ⁡ 
                             
                               [ 
                               
                                 
                                   b 
                                   i 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                               ] 
                             
                           
                         
                         - 
                         
                           n 
                           
                             
                               e 
                               ɛ 
                             
                             + 
                             1 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     
                       m 
                       n 
                     
                     · 
                     
                       
                         
                           e 
                           ɛ 
                         
                         + 
                         1 
                       
                       
                         
                           e 
                           ɛ 
                         
                         - 
                         1 
                       
                     
                     · 
                     
                       ( 
                       
                         
                           ∑ 
                           
                             i 
                             ∈ 
                             
                               [ 
                               n 
                               ] 
                             
                           
                         
                         ⁢ 
                         
                           
                             
                               
                                 x 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             m 
                           
                           · 
                           
                             
                               
                                 e 
                                 ɛ 
                               
                               - 
                               1 
                             
                             
                               
                                 e 
                                 ɛ 
                               
                               + 
                               1 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     σ 
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
               
             
           
         
       
     
     Lemma 4. 
     Let {circumflex over (σ)}(t) and σ be as in Equations (3, 4). Let θ∈(0,1) be arbitrary. 
     
       
         
           
             
               
                 
                   
                     Pr 
                     ⁡ 
                     
                       [ 
                       
                         
                            
                           
                             
                               
                                 σ 
                                 ^ 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             - 
                             
                               σ 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                            
                         
                         ≥ 
                         
                           δ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           m 
                         
                       
                       ] 
                     
                   
                   ≤ 
                   
                     2 
                     · 
                     
                       
                         e 
                         
                           
                             - 
                             2 
                           
                           ⁢ 
                           
                             
                               δ 
                               2 
                             
                             · 
                             n 
                             · 
                             
                               
                                 ( 
                                 
                                   
                                     
                                       e 
                                       ɛ 
                                     
                                     - 
                                     1 
                                   
                                   
                                     
                                       e 
                                       ɛ 
                                     
                                     + 
                                     1 
                                   
                                 
                                 ) 
                               
                               2 
                             
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     Proof. 
     Clearly, for every i∈[n], 
     
       
         
           
             
               E 
               ⁡ 
               
                 [ 
                 
                   
                     b 
                     i 
                   
                   ⁡ 
                   
                     ( 
                     t 
                     ) 
                   
                 
                 ] 
               
             
             = 
             
               
                 1 
                 
                   
                     e 
                     ɛ 
                   
                   + 
                   1 
                 
               
               + 
               
                 
                   
                     
                       x 
                       i 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   m 
                 
                 · 
                 
                   
                     
                       
                         e 
                         ɛ 
                       
                       - 
                       1 
                     
                     
                       
                         e 
                         ɛ 
                       
                       + 
                       1 
                     
                   
                   . 
                 
               
             
           
         
       
     
     Let 
     
       
         
           
             
               
                 
                   μ 
                   = 
                   
                     
                       E 
                       ( 
                       
                         
                           ∑ 
                           
                             i 
                             ∈ 
                             
                               [ 
                               n 
                               ] 
                             
                           
                           
                               
                           
                         
                         ⁢ 
                         
                           
                             b 
                             i 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                       ) 
                     
                     = 
                     
                       
                         n 
                         
                           
                             e 
                             ɛ 
                           
                           + 
                           1 
                         
                       
                       + 
                       
                         
                           
                             n 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               σ 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           m 
                         
                         · 
                         
                           
                             
                               
                                 e 
                                 ɛ 
                               
                               - 
                               1 
                             
                             
                               
                                 e 
                                 ɛ 
                               
                               + 
                               1 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     Applying the Chernoff-Hoeffding bound to independent {0,1}-random variables {b i (t)} i∈n , for all t&gt;0, 
     
       
         
           
             
               
                 
                   
                     Pr 
                     [ 
                     
                       
                          
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 
                                   [ 
                                   n 
                                   ] 
                                 
                               
                               
                                   
                               
                             
                             ⁢ 
                             
                               
                                 b 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           - 
                           μ 
                         
                          
                       
                       ≥ 
                       t 
                     
                     ] 
                   
                   ≤ 
                   
                     2 
                     · 
                     
                       
                         e 
                         
                           - 
                           
                             
                               2 
                               ⁢ 
                               
                                 t 
                                 2 
                               
                             
                             n 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     Combining (7) and (6) produces 
     
       
         
           
             
               
                 
                   
                     Pr 
                     [ 
                     
                       
                          
                         
                           
                             
                               ∑ 
                               
                                 i 
                                 ∈ 
                                 
                                   [ 
                                   n 
                                   ] 
                                 
                               
                               
                                   
                               
                             
                             ⁢ 
                             
                               
                                 b 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           - 
                           
                             n 
                             
                               
                                 e 
                                 ɛ 
                               
                               + 
                               1 
                             
                           
                           - 
                           
                             
                               
                                 n 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 σ 
                               
                               m 
                             
                             · 
                             
                               
                                 
                                   e 
                                   ɛ 
                                 
                                 - 
                                 1 
                               
                               
                                 
                                   e 
                                   ɛ 
                                 
                                 + 
                                 1 
                               
                             
                           
                         
                          
                       
                       ≥ 
                       t 
                     
                     ] 
                   
                   ≤ 
                   
                     
                       e 
                       
                         - 
                         
                           
                             2 
                             ⁢ 
                             
                               t 
                               2 
                             
                           
                           n 
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     Combining (8), (4), and (3) produces 
     
       
         
           
             
               
                 
                   
                     Pr 
                     [ 
                     
                       
                          
                         
                           
                             
                               σ 
                               ^ 
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                           - 
                           
                             σ 
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                          
                       
                       ≥ 
                       
                         t 
                         · 
                         
                           m 
                           n 
                         
                         · 
                         
                           
                             
                               e 
                               ɛ 
                             
                             + 
                             1 
                           
                           
                             
                               e 
                               ɛ 
                             
                             - 
                             1 
                           
                         
                       
                     
                     ] 
                   
                   ≤ 
                   
                     2 
                     · 
                     
                       
                         e 
                         
                           - 
                           
                             
                               2 
                               ⁢ 
                               
                                 t 
                                 2 
                               
                             
                             n 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     Thus setting 
               t   =     θ   ⁢           ⁢     n   ·         e   ɛ     -   1         e   ɛ     +   1             ,         
we obtain
 
                       Pr   [                σ   ^     ⁡     (   t   )       -     σ   ⁡     (   t   )              ≥     θ   ⁢           ⁢   m       ]     ≤     2   ·     e       -   2     ⁢       θ   2     ·   n   ·       (         e   ɛ     -   1         e   ɛ     +   1       )     2               ,           (   10   )               
which concludes the proof.
 
     Proof. 
     [Proof of Theorem 1] For any δ∈[0,1], set 
             δ   =     2   ·       e       -   2     ⁢       θ   2     ·   n   ·       (         e   ɛ     -   1         e   ɛ     +   1       )     2           .             
Then, error
 
               θ   ⁢           ⁢   m     =     ≤       m       2   ⁢   n         ·         e   ɛ     +   1         e   ɛ     -   1       ·         log   ⁢           ⁢     2   δ         .               
This fact combined with Lemmas (2,4) complete the proof.
 
     2.2 d-Bit Mechanism for Histogram Estimation 
     Now consider the problem of estimating histograms of counter values in a discretized domain with k buckets with LDP to be guaranteed. 
     In order to have a smooth trade-off between accuracy and communication cost (as well as the ability to protect privacy in repeated data collection, which will be introduced in Section 3), in some examples, the facility uses a randomized response mechanism using subsampling by buckets. Some aspects of this “histogram estimation” approach are based on J. C. Duchi, M. J. Wainwright, and M. I. Jordan, Local privacy and minimax bounds: Sharp rates for probability estimation, in  NIPS , pages 1529-1537, 2013. 
     Collection Mechanism 
     dBitFlip: Each user i (that is, the computing device operating on behalf of user i) randomly draws d bucket numbers without replacement from [k], denoted by j 1 , j 2 , . . . , j d . When the collection of discretized bucket number v i (t)∈[k] at time t is requested by the data collector, each user i sends a vector: 
                   b   i     ⁡     (   t   )       =     [       (       j   1     ,       b     i   ,     j   1         ⁡     (   t   )         )     ,     (       j   2     ,       b     i   ,     j   2         ⁡     (   t   )         )     ,   …   ⁢           ,     (       j   d     ,       b     i   ,     j   d         ⁡     (   t   )         )       ]       ,         
where
 
               b     i   ,     j   p         ⁡     (   t   )           
is a random 0-1 bit,
 
     with 
     
       
         
           
             
               Pr 
               ⁡ 
               
                 [ 
                 
                   
                     
                       b 
                       
                         i 
                         , 
                         
                           j 
                           p 
                         
                       
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   1 
                 
                 ] 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           e 
                           
                             ɛ 
                             / 
                             2 
                           
                         
                         / 
                         
                           ( 
                           
                             
                               e 
                               
                                 ɛ 
                                 / 
                                 2 
                               
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               v 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                         = 
                         
                           j 
                           p 
                         
                       
                     
                   
                   
                     
                       
                         1 
                         / 
                         
                           ( 
                           
                             
                               e 
                               
                                 ɛ 
                                 / 
                                 2 
                               
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                     
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               v 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                         ≠ 
                         
                           j 
                           p 
                         
                       
                     
                   
                 
                 , 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     for 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     p 
                   
                   = 
                   1 
                 
                 , 
                 2 
                 , 
                 … 
                 ⁢ 
                 
                     
                 
                 , 
                 
                   d 
                   . 
                 
               
             
           
         
       
     
     Under the public coin model, each user i only needs to send to the data collector d bits 
                 b     i   ,     j   1         ⁡     (   t   )       ,       b     i   ,     j   2         ⁡     (   t   )       ,   …   ⁢           ,       b     i   ,     j   d         ⁡     (   t   )             
in b i (t), as j 1 , j 2 , . . . , j d  can be generated using public coins.
 
     Histogram Estimation. 
     Data collector estimates histogram h t  as: for v∈k, 
     
       
         
           
             
               
                 
                   
                     
                       
                         h 
                         ^ 
                       
                       t 
                     
                     ⁡ 
                     
                       ( 
                       v 
                       ) 
                     
                   
                   = 
                   
                     
                       k 
                       nd 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             
                               b 
                               
                                 i 
                                 , 
                                 v 
                               
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           is 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           received 
                         
                       
                       ⁢ 
                       
                         
                           
                             
                               
                                 b 
                                 
                                   i 
                                   , 
                                   v 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             · 
                             
                               ( 
                               
                                 
                                   e 
                                   
                                     ɛ 
                                     / 
                                     2 
                                   
                                 
                                 + 
                                 1 
                               
                               ) 
                             
                           
                           - 
                           1 
                         
                         
                           
                             e 
                             
                               ɛ 
                               / 
                               2 
                             
                           
                           - 
                           1 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     The privacy guarantee is straightforward. In terms of the accuracy, the intuition is that for each bucket v∈[k], there are roughly nd/k users each responding with a 0-1 bit b i,v (t). The following result can be proven. 
     Theorem 2. 
     For single-round data collection, the mechanism dBitFlip preserves ε-LDP for each user. Upon receiving the d bits 
               {       b     i   ,     j   p         ⁡     (   t   )       }       p   ∈     [   d   ]             
from each user i, the data collector can then estimate then histogram h i  as ĥ i  in (11). With probability at least 1−δ, we have,
 
     
       
         
           
             
               
                 max 
                 
                   v 
                   ∈ 
                   
                     [ 
                     k 
                     ] 
                   
                 
               
               ⁢ 
               
                  
                 
                   
                     
                       h 
                       t 
                     
                     ⁡ 
                     
                       ( 
                       v 
                       ) 
                     
                   
                   - 
                   
                     
                       
                         h 
                         ^ 
                       
                       t 
                     
                     ⁡ 
                     
                       ( 
                       v 
                       ) 
                     
                   
                 
                  
               
             
             ≤ 
             
               
                 
                   
                     5 
                     ⁢ 
                     k 
                   
                   nd 
                 
               
               · 
               
                 
                   
                     e 
                     
                       ɛ 
                       / 
                       2 
                     
                   
                   + 
                   1 
                 
                 
                   
                     e 
                     
                       ɛ 
                       / 
                       2 
                     
                   
                   - 
                   1 
                 
               
               · 
               
                 
                   log 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       6 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       k 
                     
                     δ 
                   
                 
               
             
             ≤ 
             
               
                 O 
                 ( 
                 
                   
                     
                       k 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         log 
                         ⁡ 
                         
                           ( 
                           
                             k 
                             / 
                             δ 
                           
                           ) 
                         
                       
                     
                     
                       
                         ɛ 
                         2 
                       
                       ⁢ 
                       nd 
                     
                   
                 
                 ) 
               
               . 
             
           
         
       
     
     2.2A Proof of Theorem 2 
     The privacy guarantee ε-LDP is straightforward from the construction. To analyze the error bound |h t (v)−ĥ t (v)| for each v∈[k], consider the set of users U(v) each of whom sends (v,b i,v (t)) to the data collector. Let n v =|U(v)|, and based on how each user chooses j 1  . . . , j d , 
               n   v     =     k   nd           
is known in expectation. Consider
 
                 h   t   ′     ⁡     (   v   )       =       1     n   v       ·          {       i   ⁢     :     ⁢       v   i     ⁡     (   t   )         =   v                 
and i∈U(v)}|: since U(v) can be considered as a uniform random sample from [n], it can be shown that, Hoeffding&#39;s inequality,
 
                        h   t     ⁡     (   v   )       -       h   t   ′     ⁡     (   v   )              ≤     O   (         k   ⁢           ⁢     log   ⁡     (     1   /   δ     )         nd       )           
with probability at least 1−δ/2
 
     From (11) and, again, Hoeffding&#39;s inequality, 
                        h   t   ′     ⁡     (   v   )       -         h   ^     t     ⁡     (   v   )              ≤     O   (         k   ⁢           ⁢     log   ⁡     (     1   /   δ     )             ɛ   2     ⁢   nd         )           
with probability at least 1−δ/2
 
     Combining these using the union bound of probability and trangle inequality produces 
                        h   t     ⁡     (   v   )       -         h   ^     t     ⁡     (   v   )              ≤     O   (         k   ⁢           ⁢     log   ⁡     (     1   /   δ     )             ɛ   2     ⁢   nd         )           
with probability at least 1−δ
 
     The bound of the max error max v∈[k] |ht(v)−ĥt(v)| follows from union bound over the k buckets. 
     3. Memoization for Continual Collection of Counter Data 
     One important concern regarding the use of ε-LDP algorithms (e.g., in Section 2.1) to collect counter data pertains to privacy leakage that may occur if user&#39;s data is collected repeatedly (say, daily) and user&#39;s private value x i  does not change or changes little. Depending on the value of ε, after a number of rounds, data collector will have enough noisy reads to estimate x i  with high accuracy. 
     Memoization is a simple rule that says that: At the account setup phase each user pre-computes and stores his responses to data collector for all possible values of the private counter. At data collection users do not use fresh randomness, but respond with pre-computed responses corresponding to their current counter values. To a certain degree, memoization takes care of situations when the private value x i  stays constant. Note that the use of memoization can in some cases violate differential privacy. If memoization is employed, data collector can easily distinguish a user whose value keeps changing from a user whose value is constant, no matter how small s is. However, privacy leakage is limited: when data collector observes that user&#39;s response had changed, this only indicates that user&#39;s value had changed, but not what it was and not what it has changed to. 
     As observed in Section 1.3, using memoization technique in the context of collecting counter data can be problematic for the following reason: often, from day to day, private values x i  do not stay constant, but rather experience small changes (e.g., one can think of app usage statistics reported in seconds). Note that naively using memoization adds no additional protection to the user whose private value varies but stays approximately the same, as data collector would observe many independent responses corresponding to it. 
     One way to address the issue above is to use discretization: pick a large integer (segment size) s that divides m; consider the partition of all integers into segments [ls,(l+1)s]; and have each user report his value after rounding the true value x i  to the mid-point of the segment that x i  belongs to. This approach takes care of the issue of leakage caused by small changes to x i  as users values would now tend to stay within a single segment, and thus trigger the same memorized response; however accuracy loss may be extremely large. For instance, in a population where all x i  are ls+1 for some l, after rounding every user would be responding based on the value ls+s/2 
     Subsection 3.1 describes a different, randomized rounding technique (termed α-point rounding) that rigorously addresses the issues discussed above. We first consider the mean estimation problem. 
     3.1 a-Point Rounding for Mean Estimation 
     Rounding seeks to discretize the domain where users&#39; counters take their values. Discretization reduces domain size, and users that behave consistently take fewer different values, which allows the use of memoization to get a strong privacy guarantee. 
     Discretization may be particularly detrimental to accuracy when users&#39; private values are correlated. In some examples, the facility addresses this issue by making the discretization rule independent across different users. This ensures that when all users have the same value, some users round it up and some round it down, facilitating a smaller accuracy loss. 
     In some examples, the facility extends the basic algorithm 1 BitMean and employs both α-point rounding and memoization. For counter values that range in [0,m].
         1. At the algorithm design phase, we specify an integer s (our discretization granularity). We assume that s divides m. In some examples, the facility sets s rather large compared to m, say s=m/20 or even s=m depending on the particular application domain.   2. At the setup phase, each user i∈[n] (that is, the computing device operating on behalf of user i) independently at random picks a value α i ∈{0, . . . , s−1}, that is used to specify the rounding rule.   3. User i invokes the basic algorithm 1 BitMean with range m to compute and memorize 1-bit responses to data collector for all       

               m   s     +   1         
values x i  in the arithmetic progression
 
     
       
         
           
             
               
                 
                   A 
                   = 
                   
                     
                       
                         { 
                         ls 
                         } 
                       
                       
                         0 
                         ≤ 
                         l 
                         ≤ 
                         
                           m 
                           s 
                         
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
         
         
           
             4. Consider a user i with private value x i  who receives a data collection request. Let x i ∈[L,R), where L,R are the two neighboring elements of the arithmetic progression 
           
         
       
    
                 {   ts   }       0   ≤   l   ≤       m   s     +   1         .         
The user x i  rounds value to L if x i +α i &lt;R; otherwise, the user rounds the values to R. Let y i  denote the value of the user after rounding. In each round, user responds with the memorized bit for value y i . Note that rounding is always uniquely defined.
 
     We now establish the properties of the algorithm above. 
     Lemma 1. 
     Define 
               σ   ′     :=       1   n     ⁢       ∑   i     ⁢       y   i     .               
Then, E[σ′]=σ, where σ is defined by (7).
 
     Proof. 
     Let a=x i −L and b=R−x i . Define a random variable z i  as follows. Let z i =b with probability a/(a+b) and z i =−a with probability b/(a+b). Then, E[z i ]=0. Random variable y i  can be rewritten as y i :=x i +z i . The proof the lemma follows from the linearity of expectation and the fact that E[z i ]=0. 
     Perhaps a bit surprisingly, using α-point rounding does not lead to additional accuracy losses independent of the choice of discretization granularity s. 
     Theorem 3. 
     Independent of the value of discretization granularity s, at any round of data collection, the algorithm above provides the same accuracy guarantees as given in Theorem 1. 
     Proof. 
     It suffices to show that independent of the s i  each output bit b i  is still sampled according to the distribution given by formula (2). We use the notation of Lemma 1. By formula (2) and the definition of b i  we have: 
                     Pr   ⁡     [       b   i     =   1     ]       =       ⁢         b     a   +   b       ⁢     (       1       e   ɛ     +   1       +       L   m     ·         e   ɛ     -   1         e   ɛ     +   1           )       +       b     a   +   b       ⁢     (       1       e   ɛ     +   1       +       R   m     ·         e   ɛ     -   1         e   ɛ     +   1           )                     =       ⁢       1       e   ɛ     +   1       +       (         b     a   +   b       ·     L   m       +       a     a   +   b       ·     R   m         )     ·     (         e   ɛ     -   1         e   ɛ     +   1       )                     =       ⁢       1       e   ɛ     +   1       +       1   m     ·     (         b   ⁡     (       x   i     -   a     )       +     a   ⁡     (       x   i     +   b     )           a   +   b       )     ·     (         e   ɛ     -   1         e   ɛ     +   1       )                       =       ⁢       1       e   ɛ     +   1       +         x   i     m     ·         e   ɛ     -   1         e   ɛ     +   1             ,               
which concludes the proof.
 
     3.2 Privacy Definition Using Permanent Memoization 
     In what follows we detail privacy guarantees provided by the facility where employing α-point rounding and memoization in conjunction with the ε-DP 1-bit mechanism of Section 2.1 against a data collector that receives a very long stream of user&#39;s responses to data collection events. 
     Let U be a user and x(1), x(T) be the sequence of U&#39;s private counter values. 
     Given user&#39;s private value α i , each of {x(j)} j∈[T]  gets rounded to the corresponding value {y(j)} j∈[T]  in the set A (defined by (4)) according to the rule given in Section 3.1. 
     Definition 2. 
     Let B be the space of all sequences {z(j)} j∈[T] ⊆A p , considered up to an arbitrary permutation of the elements of A. We define the behavior pattern b(u) of the user U to be the element of B corresponding to {y(j)} j∈[T] . We refer to the number of distinct elements y(j) in the sequence {y(j)} j∈[T]  as the width of b(U). 
     We now discuss our notion of behavior pattern, using counters that carry daily app usage statistics as an example. Intuitively, users map to the same behavior pattern if they have the same number of different modes (approximate counter values) of using the app, and switch between these modes on the same days. For instance, one user that uses an app for 30 minutes on weekdays, 2 hours on weekends, and 6 hours on holidays, and the other user who uses the app for 4 hours on weekdays, 10 minutes on weekends, and does not use it on holidays will likely map to the same behavior pattern. Because the mapping from actual private counter values {x(j)} to behavior patterns is randomized, though, there is a likelihood that some users with identical private usage profiles may map to different behavior patterns. This is a positive feature of Definition 2 that increases entropy among users with the same behavior pattern. 
     Theorem 4 below shows that the algorithm of Section 3.1 makes users with the same behavior pattern blend with each other from the viewpoint of data collector (in the sense of differential privacy). 
     Theorem 4. 
     Consider users U and V with sequences of private counter values {x U (1), . . . , x U (T)} and {x V (1), . . . , x V (T)}. Assume that both U and V respond to T data collection events using the algorithm presented in Section 3.1, and b(U)=b(V) with the width of b(U) equal to w. Let s U ,s V ∈{0,1} T  be the random sequences of responses generated by users U and V; then for any binary string s∈{0,1} T  in the response domain, we have:
 
 Pr [ s   U   =s ]≤ e   wε·Pr [ s   V   =s ].  (13)
 
     Proof. 
     Let {y U (1), . . . , y U (T)} and {y V (1), . . . , y V (T)} be the sequences of U&#39;s and V&#39;s counter values after applying α-point rounding. Since the width of b(U) is w, the set {y U (j)} j∈[T]  contains w elements {y U (j 1 ), . . . , y U (j w )}. Similarly, the set {y V (j)} j∈[T]  contains w elements {y V (j 1 ), . . . , y V (j w )}. Note that vectors s U  and s V  are each determined by w bits that are U&#39;s (V&#39;s) memorized responses based corresponding to counter values {y U (j s )} s∈[w]  and {y V (j s )} s∈[w] . By the ε-LDP property of the basic algorithm 1 BitMean of Section 2.1 for all values of y,y′∈[0, . . . , m] and all b∈{0,1}, we have
 
 Pr [1BitMean( y )= b ]≤ e   ε   ·Pr [1BitMean( y ′)= b ].
 
     Thus the probability of observing some specific w responses of A can increase by at most e wε  as we vary the inputs. 
     3.2.1 Setting Parameters 
     The ε-LDP guarantee provided by Theorem 4 ensures that each user is indistinguishable from other users with the same behavior pattern (in the sense of LDP). The exact shape of behavior patterns is governed by the choice of the parameter s. Setting s very large, say s=m or s=/2 reduces the number of possible behavior patterns and thus increases the number of users that blend by mapping to a particular behavior pattern. It also yields stronger guarantee for blending within a pattern since for all users U we necessarily have b(U)≤m/s+1 and thus by Theorem 4 the likelihood of distinguishing users within a pattern is trivially at most e (m/s+1)−ε . At the same time, there are cases where one can justify using smaller values of s. In fact, consistent users, i.e., users whose private counter always land in the vicinity of one of a small number of fixed values enjoy a strong LDP guarantee within their patterns irrespective of s (provided it is not too small), and smaller s may be advantageous to avoid certain attacks based on auxiliary information as the set of all possible values of a private counter x i  that lead to a specific output bit b is potentially more complex. 
     The ε-LDP guarantee established in Theorem 4 is not a panacea, however, and in particular it is a weaker guarantee (provided in a much more challenging setting) than just the ε-LDP guarantee across all users that we provide for a single round of data collection. In particular, while LDP across all population of users is resilient to any attack based on auxiliary information, LDP across a sub population may be vulnerable to such attacks and therefore be a candidate for additional levels of protection. In particular, if data collector observes that user&#39;s response has changed; data collector knows with certainty that user&#39;s true counter value had changed. In the case of app usage telemetry, this implies that app has been used on one of the days. This attack is mitigated by the output perturbation technique that is discussed in Section 4. 
     3.2.2 Experimental Study 
     We performed an experimental study using, for each of 3 million users, the user&#39;s daily usage of two apps (App A and B) collected (in seconds) over a continuous period of 31 days to demonstrate the mapping of users to behavior patterns. For each behavior pattern (Definition 2), we calculate its support as the number of users with their sequences in this pattern (y-axis). We vary the parameter s in permanent memoization from m (maximizing blending) to m/3 and report the corresponding distributions of pattern supports. 
     For every behavior pattern there is a very large set of sequences of private counter values {x(t)} t  that may map to it (depending on α i ). Users tend to be approximately consistent and therefore simpler patterns, i.e., patterns that mostly stick to a single rounded value y(t)=y correspond to larger sets of sequences {x i (t)} t , obtained from a real population. In particular, for each app there is always one pattern (corresponding to having one fixed y(t)=y across all 31 days) which blends the majority of users (&gt;2 million). However, more complex behavior patterns have less users mapping to them. In particular, there always are some lonely users (1%-5% depending on s) who land in patterns that have support size of one or two. From the viewpoint of data collector such users can only be identified as those having a complex and irregular behavior, however the actual nature of that behavior by Theorem 4 remains uncertain. 
     3.3 Example 
     One specific example of counter collection problem that has been identified as being non-suitable but can be easily solved using our methods is to repeatedly collect age in days from a population of users. When we set s=m and apply the one-bit mean collection and estimation algorithm described above, we can collect such data for T rounds with high accuracy. Each user necessarily responds with a sequence of bits that has form z t ∘ z   T-t , where 0≤t≤T. Thus data collector only gets to learn the transition point, i.e., the day when user&#39;s age in days passes the value m−α i , which is safe from privacy perspective as α i  is picked uniformly at random by the user. 
     3.4 Continual Collection for Histogram Estimation Using Permanent Memoization 
     Since the facility discretizes the range of values and map each users value to a small number of k buckets, α-point rounding is not needed for histogram estimation. Typical single-round LDP mechanisms send out a 0-1 random response for each bucket: send 1 with probability e ∈/2 /(e ∈/2 +1) if the counter value is in this bucket, with probability 1/(e ε/2 +1) if not. This mechanism is ε-LDP. Each user can memorize a mapping f k : [k]→{0,1} k  by running this mechanism once for each v∈[k], and always respond f k (v) if the users&#39; value is in bucket v. However, this memoization schema leads to very serious privacy leakage. There is a situation where one has auxiliary information that can deterministically correlate a user&#39;s value with the output z∈{0,1} k  produced by the algorithm: more concretely, if the data collector knows that the app usage value is in a bucket v and observes the output z in some day, whenever the user sends z again in future, the data collector can infer that the bucket number is v with almost 100% probability. 
     To avoid such privacy leakages, in some examples the facility applies permanent memoization on our d-bit mechanism d BitFlip (Section 2.2). Each user runs d BitFlip once for each bucket number v∈[k] and memorizes the response in a mapping f d : {0,1} d . The user will always send f d  (v) if the bucket number is v. This is mechanism is denoted by d BitFlipPM, and the same estimator (3) can be used to estimate the histogram upon receiving the d-bit response from every user. This scheme avoids several privacy leakages that arise due to memoization, because multiple (Ω(k/2 d ) w.h.p.) buckets are mapped to the same response. This protection is the strongest when d=1. Definition 2 about behavior patterns and Theorem 4 can be generalized here to provide similar privacy guarantee in repeated data collection. 
     4. Output Perturbation 
     One of the limitations of memoization approach is that it does not protect the points of time where a user&#39;s behavior changes significantly. Consider a user who doesn&#39;t use an app for a long time, and then starts using it. When this happens, suppose the output produced by our algorithm changes from 0→1. Then the data collector can learn with certainty that the user&#39;s behavior changed, (but not what this behavior was or what it became). Output perturbation is one possible mechanism of protecting the exact location of the points of time where user&#39;s behavior has changed. As mentioned earlier, output perturbation is sometimes used as a way to mitigate privacy leakage that arises due to memoization. The main idea behind output perturbation is to flip the output of memorized responses with a small probability 0≤γ≤1. This ensures that data collector will not be able to learn with certainty that behavior of a user changed at certain time stamps. Suppose b i (t) denote the memorized response bit for user i at time t. Then, 
     
       
         
           
             
               
                 
                   
                     
                       
                         b 
                         ^ 
                       
                       i 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 b 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 with 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 probability 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 1 
                               
                               - 
                               γ 
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               1 
                               - 
                               
                                 
                                   b 
                                   i 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             otherwise 
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     Note that output perturbation is done at each time step t on the memorized responses. For any arbitrary T&gt;0, fix a time horizon [1, 2, . . . T] where the counter data is collected. Let z and z′ be two vectors in [m] T . Let H(z) and H(z′) denote the output produced by our 1-bit algorithm+Memoization+output perturbation, where z and z′ see the same memorized responses but see different randomness in the output perturbation step. Suppose the Hamming-distance between z and z′ is at most S. Then, 
     Theorem 5. 
     Let S be a vector in {0,1} T . Then, 
     
       
         
           
             
               
                 P 
                 ⁡ 
                 
                   [ 
                   
                     
                       
                         A 
                         ′ 
                       
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     S 
                   
                   ] 
                 
               
               
                 P 
                 ⁡ 
                 
                   [ 
                   
                     
                       
                         A 
                         ′ 
                       
                       ⁡ 
                       
                         ( 
                         
                           x 
                           ′ 
                         
                         ) 
                       
                     
                     = 
                     S 
                   
                   ] 
                 
               
             
             ≥ 
             
               
                 γ 
                 δ 
               
               . 
             
           
         
       
     
     Recall that in the output perturbation step, we flip each output bit  (x(t)) independently with probability γ. This implies, 
                   P   ⁡     [         A   ′     ⁡     (   x   )       =   S     ]         P   ⁡     [         A   ′     ⁡     (     x   ′     )       =   S     ]         =       ∏     t   =   1     T     ⁢       P   ⁡     [         A   ′     ⁡     (     x   ⁡     (   t   )       )       =     S   ⁡     (   t   )         ]         P   ⁡     [         A   ′     ⁡     (       x   ′     ⁡     (   t   )       )       =     S   ⁡     (   t   )         ]             ,         
where S(t)∈{0,1} denotes the value of S at the t th coordinate. For a t∈[T] for which  (x(t))= (x′(t)), we have
 
                   P   ⁡     [         A   ′     ⁡     (     x   ⁡     (   t   )       )       =     S   ⁡     (   t   )         ]         P   ⁡     [         A   ′     ⁡     (       x   ′     ⁡     (   t   )       )       =     S   ⁡     (   t   )         ]         =   1     ;         
this is true, since the probability used to flip the output bits is same for both the strings. Therefore,
 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               A 
                               ′ 
                             
                             ⁡ 
                             
                               ( 
                               x 
                               ) 
                             
                           
                           = 
                           S 
                         
                         ] 
                       
                     
                     
                       P 
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               A 
                               ′ 
                             
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 ′ 
                               
                               ) 
                             
                           
                           = 
                           S 
                         
                         ] 
                       
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         
                           t 
                           : 
                           
                             t 
                             ∈ 
                             
                               [ 
                               T 
                               ] 
                             
                           
                         
                         , 
                         
                           
                             A 
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                               ) 
                             
                           
                           ≠ 
                           
                             A 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   x 
                                   ′ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                     ⁢ 
                     
                       
                         
                           P 
                           ⁡ 
                           
                             [ 
                             
                               
                                 
                                   A 
                                   ′ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     ⁡ 
                                     
                                       ( 
                                       t 
                                       ) 
                                     
                                   
                                   ) 
                                 
                               
                               = 
                               
                                 S 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                             
                             ] 
                           
                         
                         
                           P 
                           ⁡ 
                           
                             [ 
                             
                               
                                 
                                   A 
                                   ′ 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       x 
                                       ′ 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       t 
                                       ) 
                                     
                                   
                                   ) 
                                 
                               
                               = 
                               
                                 S 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                             
                             ] 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     Now notice that for a t∈[T] for which  (x(t))≠ (x′(t)), we have 
                 P   ⁡     [         A   ′     ⁡     (     x   ⁡     (   t   )       )       =     S   ⁡     (   t   )         ]         P   ⁡     [         A   ′     ⁡     (       x   ′     ⁡     (   t   )       )       =     S   ⁡     (   t   )         ]         ≥     γ   .           
Thus, the lemma follows from Eq. (15) and from our assumption that |{t:t∈[T], (x(t))≠ (x′(t))}|≤δ.
 
     The theorem implies that if the user behavior changed at time t, then there is an interval of time [t−δ,t+δ] where the data collector would not be able to differentiate if the user behavior changed at time t or any other time t′∈[t−δ,t+δ]. Consider a user i and let x i  be a vector in [m] T  that denotes the values taken by i in the interval [1, 2, . . . , T]. Suppose the user&#39;s behavior remains constant up to time step t, and it changes at time t, and then remains constant. Without loss of generality, let us assume that x i (t′)=a for all t′&lt;t, and x i (t′)=b for all t′≥t. Consider the case when the output produced by our memoization changes at time t; that is, using the notation from above paragraph  (x i (a))≠ (x i (b)). Without output perturbation, the data collector will be certain that user&#39;s value changed at time t. With output perturbation, we claim that the data collector would not be able to differentiate if the user&#39;s behavior changed at time t or any other time t′∈[t−δ,t+δ], if δ is sufficiently small. (Think of δ as some small constant.) Consider another pattern of user&#39;s behavior x i ′∈[m] T ,x i ′(t′)=a for all t′&lt;t* and x i ′(t′)=b for all t′≥t*. Further, if t*∈[t−δ,t+δ], then 
                 P   ⁡     [         A   ′     ⁡     (     x   i     )       =   S     ]         P   ⁡     [         A   ′     ⁡     (     x   i   ′     )       =   S     ]         ≥       γ   δ     .           
This is true because of the following reason. Consider the case t*≥t. Then, in the interval [t,t+δ], the output of 1-bit mechanism+memoization can be different from the strings x i ,x i ′. However, Hamming distance of  (x i ) and  (x i ′) is at most δ. Thus, we conclude from Theorem 5 that
 
                 P   ⁡     [         A   ′     ⁡     (     x   i     )       =   S     ]         P   ⁡     [         A   ′     ⁡     (     x   i   ′     )       =   S     ]         ≥       γ   δ     .           
The argument for the case t*&lt;t is exactly the same. Thus, output perturbation can help to protect learning exact points of time where the users&#39; behavior changes.
 
     We also establish following properties for our algorithm. 
     Theorem 6. 
     The algorithm presented above is ln 
               (           (     1   -     2   ⁢   γ       )     ⁢     (       e   ∈         e   ∈     +   1       )       +   γ           (     1   -     2   ⁢   γ       )     ⁢     (     1       e   ∈     +   1       )       +   γ       )     .         
Furthermore, for each round t of data collection, with probability at least (1−δ) the error of mechanism presented above is at most
 
               (     m   ·         e   ∈     +   1         (     1   -     2   ⁢   γ       )     ⁢     (       e   ∈     -   1     )         ·           1     2   ⁢   n       ·   log     ⁢     2   δ           )     ,         
where δ is an arbitrary constant in [0,1].
 
     4.1 Proof of Theorem 6 
     To prove Theorem 6 we observe that the distribution produced by output perturbation equivalent to 1 BitMean algorithm without the output perturbation but with the following modification: 
     
       
         
           
             
               
                 
                   
                     
                       b 
                       i 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             , 
                           
                         
                         
                           
                             
                               
                                 with 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 probability 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     1 
                                     - 
                                     
                                       2 
                                       ⁢ 
                                       γ 
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       1 
                                       
                                         
                                           e 
                                           ɛ 
                                         
                                         + 
                                         1 
                                       
                                     
                                     + 
                                     
                                       
                                         
                                           
                                             x 
                                             i 
                                           
                                           ⁡ 
                                           
                                             ( 
                                             t 
                                             ) 
                                           
                                         
                                         m 
                                       
                                       · 
                                       
                                         
                                           
                                             e 
                                             ɛ 
                                           
                                           - 
                                           1 
                                         
                                         
                                           
                                             e 
                                             ɛ 
                                           
                                           + 
                                           1 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                               
                               + 
                               γ 
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                             otherwise 
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     Data collector obtains the values {b i (t)} i∈[n]  and outputs 
     
       
         
           
             
               
                 
                   
                     
                       σ 
                       ^ 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             ∑ 
                             
                               i 
                               ∈ 
                               
                                 [ 
                                 n 
                                 ] 
                               
                             
                           
                           ⁢ 
                           
                             
                               b 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                         - 
                         
                           
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   γ 
                                 
                               
                               ) 
                             
                             ⁢ 
                             n 
                           
                           
                             
                               e 
                               ɛ 
                             
                             + 
                             1 
                           
                         
                         - 
                         
                           γ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           n 
                         
                       
                       ) 
                     
                     · 
                     
                       
                         
                           e 
                           ɛ 
                         
                         + 
                         1 
                       
                       
                         
                           e 
                           ɛ 
                         
                         - 
                         1 
                       
                     
                     · 
                     
                       m 
                       n 
                     
                     · 
                     
                       
                         1 
                         
                           1 
                           - 
                           
                             2 
                             ⁢ 
                             γ 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     Now to prove Theorem 6, we simply invoke Theorem 1. 
     5. Empirical Evaluation 
     We compare our mechanisms (with permanent memoization) for mean and histogram estimation with previous mechanisms for one-time data collection. Note that all the mechanisms we compare here provide one-time ε-LDP guarantee; however, our mechanisms provide additional protection for each individual&#39;s privacy during the repeated data collection (as introduced in Sections 3-4). These experiments show that our mechanisms, with such additional protection, are no worse than or comparable to the state-of-the-art LDP mechanisms in terms of estimation accuracy. The dataset we use is the same as the one described in Section 3.2.2. 
     Mean Estimation. 
     We implement our 1-bit mechanism (introduced in Section 2.1) with α-point Randomized Rounding and Permanent Memoization for repeated collection (Section 3), denoted by 1 BitRRPM, and output perturbation to enhance the protection for usage change (Section 4), denoted by 1 BitRRPM+OP(γ). We compare it with the Laplace mechanism for LDP mean estimation, denoted by Laplace. We vary the value of ε(ε=0.1-10) and the number of users (n=0.1, 0.3, 3×10 6  by randomly picking subsets of all the 3 million users), and run all the mechanisms 3000 times on the 31-day usage data with three counters. Recall that the domain size is m=24 hours. In the average of absolute errors (in seconds) with one-standard deviation (one-STD)m 1 BitRRPM is consistently better than Laplace with smaller errors and narrower STDs. Even with a perturbation probability γ= 1/10, they are comparable in accuracy. When γ=⅓, output perturbation is equivalent to adding an additional uniform noise from [0, 24 hours] independently on each day to provide very strong protection on usage change—even in this case, 1 BitRRPM+OP(⅓) gives us tolerable accuracy when the number of users is large. 
     Histogram Estimation. 
     We create k=32 buckets on [0, 24 hours] with even widths to evaluate mechanisms for histogram estimation. We implement our d-bit mechanism (Section 2.2) with permanent memoization for repeated collection (Section 3.4), denoted by d BitFlipPM. In order to provide protection on usage change in repeated collection, we use d=1, 2, 4 (strongest when d=1). We compare it with state-of-the-art one-time mechanisms for histogram estimation: BinFlip [8, 9], KFlip [22], and BinFlip+ [3]. When d=k, d BitFlipPM has the same accuracy as BinFlip. KFlip is sub-optimal for small ε [22] but has better performance when ε is Ω(ln k). In contrast, BinFlip+ has good performance when ε≤2. We repeat the experiment 3000 times, and average histogram error (maximum error across all bars in a histogram) with one-STD for different algorithms with ε=0.1-10 and n=0.3, 3×10 6  confirms the above theoretical results. BinFlip (equivalently, 32 BitFlipPM) has the best accuracy overall. With enhanced privacy protection in repeated data collection, 4 bitFlipPM-1 bitFlipPM are comparable or even better than one-time collection mechanisms KFlip (when s is small) and BinFlip+ (when ε is large). 
     In some examples, the facility provides a method in a computing system for reporting on one or more original values on behalf of each of a plurality of users, each original value falling within a domain partitioned into a plurality of segments of uniform size, the method comprising: for each of the plurality of users, randomly selecting an upward-rounding window size that is smaller than the segment size; for each of the plurality of users, for each source value in a domain, randomly determining a mapping of each segment of the domain to a segment identifier value; for each of the plurality of users, determining a first original value for the user; adding the upward-rounding window size to the first original value determined for the user to obtain a first window-augmented original value; identifying a first segment containing the first window-augmented original value; using the determined mapping to identify a first segment identifier value mapped-to from the first identified segment; and transmitting a first reporting communication on behalf of the user that reports a value based at least in part on the identified first segment identifier value. 
     In some examples, the facility provides one or more memories collectively having contents configured to cause a computing system to perform a method for reporting on one or more original values on behalf of each of a plurality of users, each original value falling within a domain partitioned into a plurality of segments of uniform size, the method comprising: for each of the plurality of users, randomly selecting an upward-rounding window size that is smaller than the segment size; for each of the plurality of users, for each source value in a domain, randomly determining a mapping of each segment of the domain to a segment identifier value; for each of the plurality of users, determining a first original value for the user; adding the upward-rounding window size to the first original value determined for the user to obtain a first window-augmented original value; identifying a first segment containing the first window-augmented original value; using the determined mapping to identify a first segment identifier value mapped-to from the first identified segment; and transmitting a first reporting communication on behalf of the user that reports a value based at least in part on the identified first segment identifier value. 
     In some examples, the facility provides a computing system for reporting on one or more original values on behalf of each of a plurality of users, each original value falling within a domain partitioned into a plurality of segments of uniform size, the computing system comprising: a processor; and a memory having contents that are executable by the processor to perform a method, the method comprising: for each of the plurality of users, randomly selecting an upward-rounding window size that is smaller than the segment size; for each of the plurality of users, for each source value in a domain, randomly determining a mapping of each segment of the domain to a segment identifier value; for each of the plurality of users, determining a first original value for the user; adding the upward-rounding window size to the first original value determined for the user to obtain a first window-augmented original value; identifying a first segment containing the first window-augmented original value; using the determined mapping to identify a first segment identifier value mapped-to from the first identified segment; and transmitting a first reporting communication on behalf of the user that reports a value based at least in part on the identified first segment identifier value. 
     It will be appreciated by those skilled in the art that the above-described facility may be straightforwardly adapted or extended in various ways. While the foregoing description makes reference to particular embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein.