PRIVATE DECAYED SUM ESTIMATION UNDER CONTINUAL OBSERVATION

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
15Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method for providing privacy protection, comprising:
 accessing dynamic data from a database;
selecting a decay sum model;
initiating an algorithm adapted to produce a polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent;
assembling the dynamic data in a dyadic tree structure;
adding a nonuniformity component to nodes of the dyadic tree structure;
constructing differentially private estimators for fixed steps of time; and
applying the differentially private estimators to a query to enhance privacy protection from potential adversaries.
1 Assignment
0 Petitions
Accused Products
Abstract
Described herein is a method and system for providing privacy guarantees with an improved privacyaccuracy tradeoff. Dynamic data can be accessed from a database. A sum model is selected from window sum, exponential decay sum, and polynomial decay sum. An algorithm is initiated that produces polylogarithmic bounded error in the range of a sum function associated with the selected sum model and independent of time steps. The data can be assembled in a dyadic tree structure. A nonlinearity component can be added to nodes of the dyadic tree structure. For example, this can be a noise components or a weight applied to the update. This can be done, for example, to different nodes differently. Differential private estimators can be constructed for fixed steps of time. The differential private estimators can be applied to a query means or filtering system to enhance privacy protection from potential adversaries.
22 Citations
View as Search Results
Privacy Preserving Statistical Analysis on Distributed Databases  
Patent #
US 20140281572A1
Filed 03/14/2013

Current Assignee
Mitsubishi Electric Research Laboratories

Sponsoring Entity
Mitsubishi Electric Research Laboratories

Emoji frequency detection and deep link frequency  
Patent #
US 9,705,908 B1
Filed 09/24/2016

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Emoji frequency detection and deep link frequency  
Patent #
US 9,712,550 B1
Filed 09/24/2016

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Emoji frequency detection and deep link frequency  
Patent #
US 9,894,089 B2
Filed 06/19/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Learning new words  
Patent #
US 10,133,725 B2
Filed 04/03/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Privacy preserving statistical analysis on distributed databases  
Patent #
US 10,146,958 B2
Filed 03/14/2013

Current Assignee
Mitsubishi Electric Research Laboratories

Sponsoring Entity
Mitsubishi Electric Research Laboratories

Emoji frequency detection and deep link frequency  
Patent #
US 10,154,054 B2
Filed 06/30/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Efficient implementation for differential privacy using cryptographic functions  
Patent #
US 10,229,282 B2
Filed 09/23/2016

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

System and method for privacy management of infinite data streams  
Patent #
US 10,366,249 B2
Filed 10/14/2016

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

Emoji frequency detection and deep link frequency  
Patent #
US 10,454,962 B2
Filed 10/12/2018

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Efficient implementation for differential privacy using cryptographic functions  
Patent #
US 10,552,631 B2
Filed 03/08/2019

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

User experience using privatized crowdsourced data  
Patent #
US 10,599,867 B2
Filed 11/07/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

User experience using privatized crowdsourced data  
Patent #
US 10,599,868 B2
Filed 11/07/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Learning new words  
Patent #
US 10,701,042 B2
Filed 10/12/2018

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Differential privacy using a multibit histogram  
Patent #
US 10,726,139 B2
Filed 09/30/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

FORWARD DECAY TEMPORAL DATA ANALYSIS  
Patent #
US 20110066600A1
Filed 09/15/2009

Current Assignee
ATT Intellectual Property I LP

Sponsoring Entity
ATT Intellectual Property I LP

DIFFERENTIAL PRIVACY PRESERVING RECOMMENDATION  
Patent #
US 20110064221A1
Filed 09/11/2009

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

SYSTEM AND METHOD FOR DISTRIBUTED PRIVACY PRESERVING DATA MINING  
Patent #
US 20100268734A1
Filed 05/23/2007

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Domain knowledgeassisted information processing  
Patent #
US 7,542,969 B1
Filed 11/03/2005

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

SYSTEMS AND METHODS OF MONITORING THE ACOUSTIC COUPLING OF MEDICAL DEVICES  
Patent #
US 20090326609A1
Filed 04/21/2009

Current Assignee
Cardiac Pacemakers Incorporated

Sponsoring Entity
Cardiac Pacemakers Incorporated

Differential data privacy  
Patent #
US 20070143289A1
Filed 12/16/2005

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Selfoptimizing network attached storage for multiple geographic locations  
Patent #
US 20070168405A1
Filed 01/17/2006

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

20 Claims
 1. A method for providing privacy protection, comprising:
accessing dynamic data from a database; selecting a decay sum model; initiating an algorithm adapted to produce a polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent; assembling the dynamic data in a dyadic tree structure; adding a nonuniformity component to nodes of the dyadic tree structure; constructing differentially private estimators for fixed steps of time; and applying the differentially private estimators to a query to enhance privacy protection from potential adversaries.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
 9. A system for providing privacy protection, comprising:
a query module configured to access a database having continuously updated data; an analysis module configured to select a decay sum model; the analysis module configured to initiate an algorithm adapted to produce polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent; the analysis module configured to assemble the dynamic data in a dyadic tree structure; the analysis module configured to add a nonuniformity component to nodes of the dyadic tree structure; the analysis module configured to construct differentially private estimators for fixed steps of time; and an output module configured to apply the differentially private estimators to a query to enhance privacy protection from potential adversaries.  View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
 17. A computer readable medium bearing instructions for protecting privacy of data, comprising:
instructions for accessing dynamic data from a database; selecting a decay sum model; initiating an algorithm adapted to produce polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent; assembling the dynamic data in a dyadic tree structure; adding a nonuniformity component to nodes of the dyadic tree structure; constructing differentially private estimators for fixed steps of time; and applying the differentially private estimators to a query to enhance privacy protection from potential adversaries.  View Dependent Claims (18, 19, 20)
1 Specification
This application claims the benefit of U.S. provisional application No. 61/524,905, filed Aug. 18, 2011, the contents of which are hereby incorporated by reference herein.
Nearly any nontrivial physical, hardware or software system has a dashboard continually observing the system variables, and updating various measurements. Such data analysis applications deal with dynamic data: data arrives over time, and there is a need to continually output the result of some analysis f on data seen thus far D_{j }for each time instant j. This challenges privacy of analysis because the same function is computed on several deltas of the data and the collection of these function values has more potential to leak information than even several queries to different portions of static data.
The notion of differential privacy was extended to address this challenge. In particular, studies of differential privacy with continual observation and analysis identified the problem of computing the running sum of a series of 0/1 updates as an important technical primitive, formulated differential privacy of computing these running sums, and presented upper and lower bounds on accuracy of εdifferentially private algorithms for computing running sums. It was shown that an additive accuracy of
with constant probability is possible for the running sums problem, and that Ω(log T) additive error was necessary to answer accurately all running sum queries for all time steps jε└1,T┘. The sums problem is a rich problem capable of capturing many analyses by applying suitable predicates to the data items that map them to 0/1.
Algorithms for tracking statistics on dynamic data while preserving privacy under continual observation have been shown. In particular, an algorithm for privacy under continual observation has been presented for the running sum problem. For any fixed time step, the algorithm achieves additive error of
with constant probability, where T is an upper bound on the maximum size of the input and is assumed to be known to the algorithm. Another continually private algorithm for the running sum problem does not need to be given an upper bound on input size, and uses a dyadic tree data structure. However, the additive error of the algorithm does grow as the size of the processed input grows: at a fixed time step j, it can guarantee an additive error of
with constant probability, matching the bound of the former algorithm without the need to specify an explicit bound T.
A general transformation of a single output (pan) private streaming algorithm that satisfies a monotonicity property to an algorithm that is (pan) private under continual observation has also been presented. However, such a property is not satisfied by algorithms that provide accurate estimates of decayed sums. Furthermore, it has also been shown that functions that change their value by d at least k times for some input and don'"'"'t change their value on update 0 cannot be approximated to within an additive factor better than O(kd) while satisfying privacy under continual observation.
Described herein is a method and system for providing privacy guarantees with an improved privacyaccuracy tradeoff. Initially, dynamic data can be accessed from a database that has entries collected and/or generated over time. A sum model is selected from the following group of models: window sum, exponential decay sum, and polynomial decay sum. An algorithm is initiated that is adapted to produce bounded error which is polylogarithmic in the range of a sum function associated with the selected sum model and independent of time steps. The data can be assembled in a dyadic tree structure. A noise component can be added to nodes of the dyadic tree structure. For example, different noise components can be added to different nodes. Alternatively, a weight can be added to the contribution of an update. This can be done, for example, to different nodes differently. Differential private estimators can be constructed for fixed steps of time. The differential private estimators can be applied to a query means or filtering system to enhance privacy protection from potential adversaries.
A method is disclosed for providing privacy protection that comprises: accessing dynamic data from a database; selecting a decay sum model; initiating an algorithm adapted to produce a polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent; assembling the dynamic data in a dyadic tree structure; adding a nonuniformity component to nodes of the dyadic tree structure; constructing differentially private estimators for fixed steps of time; and applying the differentially private estimators to a query to enhance privacy protection from potential adversaries. The decay sum model can be selected from the group of sum models consisting of window sum, exponential decay sum, and polynomial decay sum. The dyadic tree structure can be a sequence of dyadic trees and the nonuniformity component can be a noise component. The noise component can be a different noise component for different nodes of the dyadic tree structure and the nonuniformity component can be a weight applied to an update. Also, multiple instances of a window sum algorithm can be run in parallel on a condition that the selected decay sum model is a polynomial decay sum.
Also, a system for providing privacy protection is disclosed that comprises: a query module configured to access a database having continuously updated data; an analysis module configured to select a decay sum model; the analysis module configured to initiate an algorithm adapted to produce polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent; the analysis module configured to assemble the dynamic data in a dyadic tree structure; the analysis module configured to add a nonuniformity component to nodes of the dyadic tree structure; the analysis module configured to construct differentially private estimators for fixed steps of time; and an output module configured to apply the differentially private estimators to a query to enhance privacy protection from potential adversaries. The decay sum model can be selected from the group of sum models consisting of window sum, exponential decay sum, and polynomial decay sum and the dyadic tree structure is a sequence of dyadic trees.
A more detailed understanding can be had from the following description, given by way of example in conjunction with the accompanying drawings wherein:
It is to be understood that the figures and descriptions of embodiments have been simplified to illustrate elements that are relevant for a clear understanding, while eliminating, for the purpose of clarity, many other elements. Those of ordinary skill in the art can recognize that other elements and/or steps are desirable and/or required in implementing the present invention. However, because such elements and steps are well known in the art, and because they do not facilitate a better understanding of the present invention, a discussion of such elements and steps is not provided herein.
The reality in many monitoring applications is that recent data is more important than distant data. Thus, the sums problem for well known decay models of data, from window to exponential and polynomial decay, can be used for privacy under continual observation scenarios. Such “decayed sums” are challenging because (a) while accuracy is needed in analysis with respect to the window or decayed sum, differential privacy is also needed; (b) sums within windows and decayed sums in general are not monotonic or even nearmonotonic as previously studied, and many nonmonotonic functions cannot be accurately estimated privately. As shown herein, the decay sum functions, which do change their value on update 0, can be well approximated in the continual privacy model despite their inherent nonmonotonicity.
Methods and systems for implementing algorithms are described herein for decayed sum in each model which are edifferentially private, and are accurate. For window and exponential decay sums, the algorithms are accurate up to additive 1/ε and polylog terms in window parameters; for polynomial decay sums which is technically more challenging because partial solutions don'"'"'t compose easily, the algorithms have additional relative error. Further, lower bounds are shown that are tight within polylog factors and tight with respect to the number of estimates required to be simultaneously accurate. Previously known algorithms have error at time step j that is dependent on j; by contrast, the algorithms described herein have bounded error, polylogarithmic in the range of the decay sum function, and independent of. The results obtained herein are via a natural dyadic tree that is maintained on dynamic data, but the crux is that the tree data structure is treated in a nonuniform manner: either adding different noise at different nodes, or weighing the contribution of an update to different nodes differently.
As stated above, monitoring applications emphasize recent data more than data long past. For example, monitoring applications typically consider a “window” of continual observations such as, last T time units, or last W updates. More generally, these monitoring applications discount past items based on how far they are in the past, and analyze decayed data.
The methods and systems herein consider differential privacy of continual observations over windows and decayed data. Formally, differential privacy over the entire history of data can be required, but can additionally require stricter accuracy over the window or decayed data. The window stream model lies between incrementing only updates where all data seen thus far is considered, and fully dynamic updates where updates are comprised of arbitrary inserts and deletes, since a shifting window can be thought of as adding a data item on the “right” and deleting a specific item, the one on the “left”. It is known in streaming that certain problems that cannot be solved with fully dynamic data can be solved on window streams. A similar issue arises with differential privacy, i.e., do the window or decayed functions, which are nonmonotonic in a specific way, lie between the monotonic functions studied thus far for which differentially private and accurate solutions are possible, and arbitrary nonmonotonic functions where such solutions are not possible.
In general, at each time step i the algorithm receives a bit x_{i}; at each time step j, the algorithm is required to report an approximation {circumflex over (F)}(x_{1}, . . . , x_{j}) to a function F(x_{1}, . . . , x_{j}) and be differentially private. A parameter q is introduced that denotes the number of queries required to be simultaneously accurate with constant probability. The guarantees are valid for any set of q queries, irrespective of their position in the stream: such guarantees are not known for the running sum problem. The results for sufficiently large q are summarized herein below.
In the case of window sum, the window sum problem with window size W requires estimating
F_{w}(j,W)=Σ_{i=j−W+1}^{i}x_{i }
for each j. Further, the whole sequence F_{w }of outputs, for all j, should be εdifferentially private. The window sum algorithm is accurate to within an additive term in
the regime q≧W. The algorithm can approximate window sum simultaneously for all window sizes W and for each W, achieves error comparable to the specialized algorithm. A lower bound of
is shown. Note that the dependence on the number q of simultaneously accurate queries is optimal. The W/2 term in the lower bound is unavoidable, as the trivial algorithm which outputs W/2 at every time step achieves additive approximation W/2 and is perfectly private.
In the case of the exponential decay sum, the exponential decay sum problem is to estimate
F_{e}(j,α)=Σ_{i=1}^{j}x_{i}α^{j−i }
accurately, while the whole sequence F_{e }of outputs, for all j, should be εdifferentially private. The algorithm is accurate to within an additive term
and has a lower bound of
The dependence on the number q of simultaneously accurate queries is optimal.
In the case of polynomial decay, the polynomial decay sum problem is to estimate
accurately, while the whole sequence F_{e }of outputs, for all j, should be ε differentially private. The algorithm returns
and has a lower bound of
Polynomial decay presents a greater challenge than window sums or exponential decay, as there is no easy way to combine a polynomial decay sum over an interval [a,b] and a polynomial decay sum over another interval [b,c] into a polynomial decay sum over [a.c]. A general technique is described herein that works on a large class of decay sum functions, (including polynomial decay), and reduces the problem of estimating the decay sum to keeping multiple window sums in parallel. The technique results in a bicriteria approximation, because of which our lower and upper bounds are incomparable for this problem.
In comparison with the simple randomized response strategy, (i.e. with probability 1/2ε/2 change update x_{i }to 1−x_{i }and keep exact statistics of the changed input), the algorithms achieve exponentially smaller additive error. The randomized response leads to estimators with standard deviation proportional to the energy of the decay function, while the estimators described herein have standard deviation polylogarithmic in the energy. Technically, the algorithms keep dyadic tree data structures. However, in order to provide estimates with error polylogarithmic in the range of the decay function, the partial sums framework is extended and the dyadic tree data structure is treated in nonuniform manner by either adding different noise at different nodes, or weighing the contribution of an update to different nodes differently.
The lower bounds also extend the lower bounds of earlier algorithms in two ways: 1) they apply to decay sum problems that have not been considered before; and 2) they apply against the weaker accuracy guarantee that q queries need to be simultaneously accurate, (rather than all queries). All lower bounds are derived from a common framework that is inspired by work on differentially private combinatorial optimization.
Described herein are details for the window sum, exponential decay sum and polynomial decay algorithms. The notation and other preliminary information are presented initially. With regard to the computational model, we consider online problems with binary input: at each time step i the algorithm receives a bit x_{i}; at each time step j, the algorithm is required to report an approximation {circumflex over (F)}(x_{1}, . . . , x_{j}) to a function F(x_{1}, . . . , x_{j}).
Described herein are the decayed sum definitions. The functions Fwe are interested in approximating are decayed sum functions. Consider a nonincreasing function
g:
→
^{+}
such that g(0)=1. The decayed sum induced by g is the function:
where is the convolution of the input x_{1}, x_{2}, . . . and a nonincreasing function g. The decayed sum problems that are considered are: when
the window sum problem (with window size W):
to simplify notation, in the above definition we assume that x_{i}=0−x_{i }for all i≦0; when
g(i)=α^{i }
(α<1), the exponential decay sum problem:
(c>1), the polynomial decay sum problem:
The last three problems have not been considered in the differential privacy literature before, and specifically not in the continual observation model.
Described herein is differential privacy. We use the standard definition of differential privacy, applied to the online model of computation specified above, where the definition states: Let A be a randomized online algorithm that at time step j outputs {circumflex over (F)}(x_{1}, . . . , x_{j})ε.
A satisfies εdifferentially privacy if for all Tε,
for all measurable subsets S⊂^{T},
and all possible inputs x_{1}, . . . , x_{T }and all j we have
Pr[({circumflex over (F)}(x_{1}, . . . ,x_{j}, . . . ,x_{k}))_{k=1}^{T}εS]≦ε^{E}Pr[({circumflex over (F)}(x_{1}, . . . ,1−x_{j}, . . . ,x_{k}))_{k=1}^{T}εS], (6)
where probability is taken over the coin throws of A.
This is the basic definition of differential privacy but with the modification that the algorithm is required to produce output at every time step, and the whole sequence of outputs is available to an adversary. This model of privacy for online algorithms operating on time series data is termed privacy under continual observation.
The following basic facts about differential privacy can be used as applicable. The first theorem gives a simple way to achieve differential privacy for algorithms with numerical output based on adding random noise scaled according to the sensitivity of the statistic being computed. Theorem 1 states that for a function F:{0,1}^{T}→^{d},
let the sensitivity of F, S_{F }be the smallest real number that satisfies
∀x_{1}, . . . ,x_{T},∀jε[T]L∥F(x_{1}, . . . ,x_{j}, . . . ,x_{T})−F(x_{1}, . . . ,1−x_{j}, . . . ,x_{T})∥_{1}≦S_{F} (7)
Then an algorithm that on input x_{1}, . . . x_{T }outputs
{circumflex over (F)}(x_{1}, . . . ,x_{T})=F(x_{1}, . . . ,x_{T})+Lap(S_{F}/ε)^{d }
satisfies εdifferentially privacy, where
Lap(λ)^{d }
is the distribution of d independent Laplace random variables with mean 0 and scale parameter λ.
The second fact is that composing multiple privacy mechanisms results in incremental (smooth) privacy loss. Theorem 2 states that let algorithm A_{1 }satisfy ε_{1}differentially privacy and algorithm A_{2 }satisfy ε_{2}differentially privacy. Then an algorithm A that on inputs x={x_{1}, . . . , x_{T}}outputs (_{1}(x),_{2}(x)) satisfies (ε_{1}+ε_{2})differential privacy.
Described herein is the dyadic tree data structure. In the sequel, the following dyadic tree data structure will be used repeatedly. This data structure is a balanced augmented search tree. In this instance, let (L,U) be a complete binary tree, where the leaves are indexed by the integers L, L+1, . . . , U, and if two sibling nodes are indexed by the intervals [l_{1},u_{1}] and [l_{1}=u_{1}+1,u_{2}],
then their parent is indexed by [l_{1},u_{2}]. Note that at level k of the tree, (the leaves being at level 1), the indexing intervals have the form [L+(i−1)2^{k−1}, L+i2^{k−1}−1] for iε[1,2^{h−k+1}].
A node whose indexing interval precedes its sibling'"'"'s indexing interval is termed a left node; the sibling of a left node is a right node. With each node a variable is associated: for the node indexed by [l,u], the associated variable is denoted C_{lu}. Given a tree =(L,U) and a prefix interval [L,u], we define the function s(u,) recursively. If [L,u] indexes a node in , then s(u, )=c_{Lu}. Otherwise, let u′ be the largest integer less than u such that [L,u′] indexes some node in . Equivalently, u′ is the largest integer such that u′=L+2^{k}−1<u.
Let be the subtree of rooted at the node indexed by [u′+1,(u′+1)+(L−u′)] (i.e. the sibling of [L,u′]); then s(u, )=c_{Lu′}+s(u, ′).
The following assertion is made. Assertion 1 states that there exist r≦log(u−L+1) inters L=u_{0},u_{1}, . . . u_{T},u_{T+1}=u such that
Furthermore, all nodes indexed by [u_{k},u_{k+1}] are left nodes in , and each node is in a different level of .
The integers u_{1}, . . . u_{r }are given directly by the recursive definition of s(u, ). To bound r, consider that at each step in the recursion, unless [L,u] indexes a node in , the tree ′ has at most half the number of leaves of the smallest subtree of that contains u as a leaf. The condition that all nodes are left siblings is easily verified from the definition of s(u, ). Finally, notice that the only way to pick two nodes on the same level is if after picking u′ in the next step of the recursion we pick the root of ′. However, in this case we could have picked the parent of [L,u′] instead of [L,u′]a contradiction.
The following Chernoff bound for sums of independent Laplace random variables will be used. The bound is proven using standard techniques. Lemma 1 state that: Let s_{1}, . . . , s_{n }be independent Laplace random variables such that s_{i}˜Lap(b_{i}). Denote S=Σ_{i=1}^{n}s_{i }and σ=2√{square root over (Σ_{i=1}^{n}b_{i}^{2})}. Then, for all
we have
Pr[S≧tσ]≦exp(0.9λ^{2}σ^{2}−λtσ). (9)
Described herein is the upper bounds for the window sum. A differentially private estimator {circumflex over (F)}(j,W) is constructed such that at any fixed time step j with good probability {circumflex over (F)}_{w}(j,W)−F_{w}(j,W)≦ε and ε is such that 1), ε<<W and 2) independent of j. A logarithmic dependence on the number q of estimates required to be simultaneously accurate is shown. Note that an algorithm that satisfies property 2 above is not known for the running sum problem.
Unlike with running sum, only the lowest log W+1 layers of the dyadic tree are needed to compute window sum. However, if a dyadic tree is kept for every window of size W, each update will contribute to more than W variables, resulting in data structures with large sensitivity, which, for differential privacy, translates into more noise. Instead of keeping a dyadic tree for every window, the window can be divided into blocks of size W, and windows can be viewed that span two blocks as the union of a suffix and a prefix of two blocks. This only requires a constant factor of more counters to estimate a single window sum.
An example algorithm for window sum is shown in Table 1.
The above leads to theorem 3 which states that the algorithm WindowSum satisfies edifferentially privacy. Furthermore, for any set Q⊂ of size q, with probability 2/3, we have:
W≧q∀jεQ:{circumflex over (F)}_{v}(j,W)−F_{w}(j,W)≦O(log^{1.5}W log^{0.5}q) (11)
W<q∀jεQ:{circumflex over (F)}_{w}(j,W)−F_{w}(j,W)≦O(log W log q) (12)
A proof of the privacy aspect is presented. Observe that any variable c_{lu }used to compute {circumflex over (F)}_{w}(j,W) satisfies l≦u≦j. Therefore, the counters c_{lu }that contribute to {circumflex over (F)}_{w}(j,W) will not be updated after time step j and {circumflex over (F)}_{w}(j,W) will be identically distributed if it is computed at any time step T≧j. Next we fix T and argue that WindowSum is εdifferentially private for inputs of size T Since the choice of T is arbitrary, privacy for all T follows. For this purpose, let c(x) be the vector of the values of all variables (in an arbitrary order) c, such that l≦T when the input is x=*x_{1}, . . . , x_{T}). Let also c_{0}(x) be c(x) with the initializing Laplace noise removed. Observe that, since each x_{j }contributes to exactly log W+1 variables c_{lu}:
∀jε[T]L∥c_{0}(x_{1}, . . . ,x_{j}, . . . ,x_{T})−c_{0}(x_{1}, . . . ,1−x_{j}, . . . ,x_{T})∥_{1}≦log W+1. (13)
Differential privacy follows from Equation 13 and Theorem 1.
A proof of the accuracy aspect is presented. It is easy to see that {circumflex over (F)}_{w}(j,W)=F_{w}(j,W).
By Assertion 1, for each k and each u, s(u_{1}, _{k}) is the sum of at most log W+1 random variables, each with variance 2(log W+1)^{2}/ε^{2}.
Therefore, the standard deviation of {circumflex over (F)}_{w}(j,W) is O(log^{1.5}W/ε).
Next we show that there exists a fixed constant C such that for all large enough q, for any j,
Pr[{{circumflex over (F)}_{w}(j,W)−F_{w}(j,W)>Cε]≦1/3q (14)
where ε is equal to log^{1.5 }W log^{0.5 }q if W≧q, or to log W log q otherwise. Taking a union bound over all jεQ for Q=q completes the proof of the theorem. We use Lemma 1 to establish Equation 14.
We consider two cases. If W≧q, we set the following parameters:
In the above C′ is a universal constant set so that the assumption of Lemma 1 holds. Then, from Lemma 1 we get that for a constant C we have
Pr[({circumflex over (F)}_{w}(j,W)−F_{w}(j,W)>C log^{1.5 }W log^{0.5}q]≦exp(−Ω(t^{2})). (15)
Setting C high enough so that the right hand side of Equation 15 is at most 1/3q completes the proof for this case.
In the other case, if W<q, set the following parameters:
In the above, C′ is a constant chosen so that the assumption of Lemma 1 holds. By Lemma 1, we have:
Pr([{circumflex over (F)}_{w}(j,W)−F_{w}(j,W)≧tσ]≦exp(−Ω(t^{2/(2−γ)})). (16)
On one hand we have:
On the other hand, observe that t=C′ ln^{1−γ/2}q, and, therefore, t^{2/(2−γ)}≧C′^{2/(2−γ)}ln q.
Setting C high enough so that the right hand side of Equation 16 is at most 1/3q completes the proof.
The windows sum can be approximated for simultaneously for all window sizes and preserve privacy under continual observation. The approximation guarantee is different for different window sizes W, and for any particular W, it is almost the same as that of Theorem 3. The main observation for this algorithm is that if for window size W, the input is divided into blocks of size W′ε[W,2] instead of exactly Was in WindowSum, then all dyadic tree datastructures can be stored as subtrees of a single dyadic tree. However, storing the whole dyadic tree with the same noise at any level will result in error of size Ω(log^{1.5}T) for all W. Instead, the goal is to make sure that within a subtree of height h, the noise added to any variable is proportional to h. To achieve this, a different privacy parameter ε_{k }at level k of the dyadic tree is used and ensures that the sum of privacy parameters converges to ε.
Let δ>1 be a parameter and ζ(−) be the Riemann zeta function, ζ(δ)=Σ_{1}^{∞}i^{−δ} and set
The algorithm AllWindowSum is shown in Table 2.
The above leads to Theorem 4 which that states that the algorithm AllWindowSum satisfies εdifferentially. Furthermore, for any set Q⊂N of size q and any W constant δ>1, with probability 2/3, we have:
W≧q∀jεQ:{circumflex over (F)}′_{w}(j,W)−F_{w}(j,W)≦O(log^{1.50}W log^{0.5}q) (19)
W<q∀jεQ:{circumflex over (F)}′_{w}(j,W)−F_{w}(j,W)≦O(log W′ log q) (20)
The proof of privacy is analogous to the proof of privacy for Theorem 8, but we treat different levels of T separately and use Theorem 2 to bound the total privacy loss. More precisely, it is shown that level k in the tree satisfies ε_{k}differentially privacy and use the fact that Σ_{k=1}^{∞}ε_{k}=ε.
The utility analysis is also analogous to the proof of Theorem 3, noticing the following facts: (1) W≦W′≦2W; and (2) as an upper bound on the variance of any variable used to compute {circumflex over (F)}′_{w}(j,W), the variance of variables at level log W′+1 can be used, which is O(log^{δ} W). The rest of the proof is unchanged.
Described herein is upper bounds for exponential decay. For the exponential decay sum problem, the goal is to design a differentially private estimator that outputs an estimate at every time step, and for any fixed time step j has error at most ε with constant probability, where ε satisfies:
which is the size of the range for the exponential decay sum; and 2) cis independent of j. These properties are analogous to the properties required for the window sum problem described herein above. The regime of interest is where α→1, as an algorithm is desired whose error bound grows slowly when the range of the exponential decay sum grows.
While for the window sum problem a sequence of dyadic trees is kept, for the exponential decay problem a single dyadic tree that grows over time is kept. The main property of exponentially decaying sums that is used is that if S_{1 }is the exponential decay sum over a time interval [a,b−1] and S_{2 }is the exponential decay sum over a time interval [b,c], then α^{c−b+1}S_{1}+S_{2 }is the exponential decay sum over the time interval [a,c]. Thus at a node in the dyadic tree that is indexed by interval [l,u], the exponential decay sum can be kept for that interval. However, doing this for every interval results in a data structure with unbounded sensitivity. Therefore, only some nodes are updated in the tree. The ExponentialSum algorithm is shown as Table 3.
The following Assertion 2 is made for the exponential decay algorithm. For an arbitrary i, let [l_{1},u_{1}], [l_{2},u_{2}], . . . be the sequence of intervals such that ∀k:inε[l_{k},u_{k}] and [l_{k},u_{k}] is a left node. Assume the intervals are ordered in ascending order of u_{k}−l_{k}. Then u_{k}−i≧2^{k−1}−1.
The proof can be provided by induction. The base case is trivial, as from iε[l_{1},u_{1}] follows u_{1}−i≧0. For the inductive step, it suffices to show that u_{k}−u_{k−1}≧2^{k−2}. By the construction of T all nodes indexed by intervals [l,u] such that iε[l,u] (i.e. all nodes satisfying condition (1) lie on the path from the leaf indexed by i to the root of T. Therefore, all nodes indexed by [l_{k},u_{k}] for some k are ancestors of i, and, by the construction of T we have u_{k}−l_{k}+1≧2^{k−1}. In particular, [l_{k},u_{k}] is an ancestor of [l_{k−1},u_{k−1}] and u_{k−1}−l_{k−1}+1≧2^{k−2}. By condition (2) all nodes indexed by [l_{k},u_{k}] are left nodes; let the right sibling of [l_{k−1},u_{k−1}] be the node indexed by [l′_{k−1},u′_{k−1}]. By construction, u′_{k−1}−l∝_{k−1}=u_{k−1}−l_{k−1 }and the parent of both nodes is indexed by [l_{k−1},u′_{k−1}]. All ancestors of [l_{k−1},u_{k−1}] are indexed by intervals that contain [l_{k−1},u′_{k−1}] as a subinterval, and, therefore:
u_{k}≧u′_{k−1}=u_{k−1}+(u_{k−1}−l_{k−1}+1) (22)
≧u_{k−1}+2^{k−2} (23)
The above leads to Theorem 5 which assumes αε(2/3,1) and that ExponentialSum satisfies εdifferentially privacy. Furthermore, for any set Q⊂N of size q, with probability 2/3, we have:
Similar to the proof of Theorem 3, observe that any variable c_{lu }used to compute F_{e}(j,α) will not be updated after time step j and F_{e}(j,α) will be identically distributed if it is computed at any time step T≧j. T is fixed and argue that ExponentialSum is εdifferentially private for inputs of size T. Because the choice of T was arbitrary, εdifferentially privacy for all sizes T follows.
The noise added to the variables associated with nodes in T is sufficient and can be shown by analyzing the sensitivity of T. Define c_{0}(x) as in the proof of Theorem 3 and [l_{1},u_{1}], [l_{2},u_{2}], . . . as in Assertion 2. Then:
Here E_{1}(x)=−E_{i}(−x) and E_{i }is the exponential integral from functional analysis. The following series expansion for E_{1 }is then obtained, which converges for all real x≦π:
where γ is the EulerMascheroni constant. Since, by assumption, α>e^{−1}, then ln 1/α<1. For x<1, the last term in Equation 31 is bounded by γ+E_{1}(1)γυα1/2. Therefore, we have:
For xε(0, 2), the following series expansion for ln x can be obtained:
Since by assumption 1/α−1<1/2, then ln(1/α)≧(1/α−1)/2. Substituting in Equation 33 results in:
Substituting Equation 36 into Equation 30 gives the following bound on sensitivity:
By Theorem 1 and Equation 37, the ExponentialSum algorithm satisfies edifferentially privacy.
The accuracy can be shown as follows. Clearly, E{circumflex over (F)}_{α}(j,α)=F_{e}(j,α). Next, placing an upper bound σ^{2}, the maximum variance of {circumflex over (F)}(j,α) over all j. By Assertion 2, all intervals [1,u_{1}], [u_{1},u_{2}], . . . , [u_{r}, j] correspond to nodes in distinct levels of T and therefore have sizes which are distinct powers of 2. We have, for some fixed constant C:
The proof can be completed analogously to the proof of Theorem 3.
Described herein is the polynomial decay. Unlike the running sum, window sum, or exponential decay sum problems, there is no easy way to combine a polynomial decay sum over an interval [a,b] and a polynomial decay sum over another interval [b,c] into a polynomial decay sum over [a,c]. Therefore, the techniques for estimating polynomial decay sum are considerably different from the techniques used for window and exponential decay sums. On a high level, an approximation of the polynomial decay function g(i)=(i+1)^{−c }can be obtained by a function g′ that is constant on exponentially growing in size intervals. The decay sum induced by g′ can be approximated by running multiple instances of the window sum algorithm in parallel. This technique results in a bicriteria approximation, i.e. the approximation guarantee has both a multiplicative and an additive approximation factor. As c→1, (i.e. as the range of the polynomial decay sum grows), the additive approximation factor remains bounded and is dominated by β^{−2}, where (1±β) is the multiplicative approximation factor. Thus the approximation guarantees for the algorithm are mostly independent of the exponent of the polynomial decay and are determined by a userchosen tradeoff between additive and multiplicative approximation. The technique is more general than the techniques for window sum and exponential decay sum, and can be applied to many decay sum problems, but, naturally, with differing approximation guarantees.
For a given polynomial decay function g=(i+1)^{−c }and the induced decay sum F, a multiplicative error parameter β can be fixed and a function b can be defined as ∀j≧0:b(j)=max{i:g(i)≧(1−β)^{j}}. Intuitively g(i) is almost constant for iε(b(j−1), b(j)). A function g′ can now be defined that approximates g′.
∀iε[b(j−1),b(j):g′(i)=(1−β)^{i−1} (41)
Let F′ be the decay sum induced by g′. From the definition of g′ it is immediate that:
∀j,∀xε{0,1}^{j}:(1−β)F(j)≦F′(j)≦F(j). (42)
The PolynomialSum algorithm is shown in Table 4.
In this case, start an instance of WindowSum for input x_{1}, . . . with window size W_{1}=b(1)−1 and initialize noise for each variable Lap(λ). Set j*=1. At time step i, if i=b(j*), start a new instance of WindowSum for input
(1−β)^{j−1}x_{b(j*)},(1−β)^{j−1}x_{b(j*)+1}, . . .
with windows size W_{j*}=b(j*)−b(j*−1) and initialize noise for each variable Lap(λ). Set j*=j*+1. The output at time step k is:
Note that the jth instance of WindowSum with input consisting of time updates is called in {0,(1−β)^{j−1}}. It is straightforward to check that the WindowSum algorithm can handle such scaled instances without modification. Note also that the WindowSum algorithm can be modified slightly by adjusting the magnitude of noise added to the variables associated with the dyadic trees kept by WindowSum.
The above results in Theorem 6 which states PolynomialSum satisfies εdifferentially privacy. Furthermore, for any set Q⊂N of size q, with probability 2/3, then:
The privacy analysis is analogous to the analysis in the proof of Theorem 3 but sensitivity is bound over all instances of WindowSum. Due to the scaling of the input, the sensitivity of the jth instance of WindowSum is bounded by (1+β)^{j−1 }(log W_{j}+1). First, bound W_{j}. Observe that b(j)=[g^{−1}((1−β)^{j}]. For g(i)=(i+1)^{−c}, we have b(j)≦(1−β)^{−j/c}+1. The overall sensitivity is bound by:
Theorem 1 and Equation 50 complete the privacy proof.
With respect to accuracy, note that E{circumflex over (F)}(j,c)=F′(j). The variance of F_{w}((1−β)^{j}x_{b(j)}, . . . , (1−β)^{j}x_{k},W_{j}) is at most 2(1−β)^{2j}λ^{2 }log W_{j}. Therefore, the total variance σ^{2 }of {circumflex over (F)}_{p}(j,c) is:
Using Lemma 1 as in Theorem 3, it is shows that, with constant probability,
as appropriate) for all jεQ with probability 2/3. Applying Equation 42 completes the proof.
This algorithm can more generally be used to compute a private (under continual observation) approximation to a decayed sum F induced by a decay function gas long as g^{−1 }grows subexponentially. In this case, sensitivity remains bounded and the additive error guarantee is dominated by a function of P, but the exact function depends on g. The algorithm is not applicable to the window or running sum problem since for them g^{−1 }is not well defined. The guarantee for exponential decay sum is incomparable with the one in Theorem 5.
Described herein are the lower bounds. A general framework for lower bounding the dependence of algorithms private under continual observation on q, which is the number of estimates required to be simultaneously accurate. The framework is also instantiated with a construction that yields concrete lower bounds for the three decay sum problems considered herein. As far as the dependence on q is concerned, the lower bounds for window and exponential decay sums are tight as shown by the analysis of the algorithms. The lower bound for polynomial decay sums is against a purely additive approximation and is not directly comparable to the bounds on the approximation factors of the algorithm.
Suppose we want to prove that no εdifferentially private algorithm can simultaneously and accurately approximate a function F(x_{1}, . . . , x_{j}) for all jεQ with probability 2/3. Assume that for some T we can construct N÷1 instances x^{0}, . . . , x^{N}, each of length T, that satisfy the following properties: 1) (Q,C)independence: for all a,bε{0, . . . , N}, a≠b, there exists some jεQ⊂T such that F(x_{1}^{a}, . . . , x_{j}^{a})−F(x_{1}^{b}, . . . , x_{j}^{b})>2C; and 2) Dcloseness: for all a,bε{0, . . . , N}, we have d_{H}(x^{a},x^{b})≦D, where d_{H }is the standard Hamming distance.
The following Lemma 2 can thus follow. Assume there exists an εdifferentially private algorithm A that at time step j outputs {circumflex over (F)}(x_{1}, . . . , x_{j}). Assume further that for any Q⊂N, Q=q, we have:
Pr[∀jεQ:{circumflex over (F)}(x_{1}, . . . ,x_{j})−F(x_{1}, . . . ,x_{j})≦C]≧2/3. (54)
If for some Q there exists a set (x^{0}, . . . , x^{N}) that satisfies (Q, C)independence and Dcloseness with respect to F then:
Let B(x^{i})={f: f_{j}−F(x_{1}^{i}, . . . , x_{j}^{i})≦C). By assumption, Pr[({circumflex over (F)}(x_{1}^{j}, . . . , x_{j}^{i}))_{i=1}^{T}εB(x^{i})]≧2/3. Then, by the definition of differential privacy and Dcloseness, we have:
∀i:Pr[({circumflex over (F)}(x_{1}^{0}, . . . ,x_{j}^{0}))_{i=1}^{T}εB(x^{i})]≧e^{−gD}2/3. (56)
By (Q, C)independence, B(x^{a})∩B(x^{b})= for all a≠b. Therefore:
However, since B(x_{0})∩U_{i=}^{N}B(x^{i})=, by the assumptions on A we have:
and the lemma follows by taking logarithms.
In order to apply Lemma 2, a method to construct a set of instances satisfying (Q, C)independence and Dcloseness for a given error bound Cis needed, such that D is upper bounded by a function of C and N is lower bounded by a function of Q. A construction is then shown that allows derivation of a lower bound for any decayed sum problem, where, naturally, the form of the lower bound depends on the specific problem, i.e. on the decay function g. As corollaries, specific lower bounds are derived for the problems considered herein.
Consider a set {x^{i}}_{i=0}^{q }defined as follows:
x^{0}=(0^{Dq}) (60)
x^{i}=(0^{(i−1)D},1^{D},0^{q−i)D}). (61)
By definition, this set satisfies Dcloseness. Set Q={j: D divides j}. Consider a general decayed sum function F(x_{1}, . . . , x_{j}) with a decay function g by Equation 1. At j=aD, a≠0, then:
F(x_{1}^{a}, . . . ,x_{i}^{a})=Σ_{i=0}^{D−1}g(i) (62)
∀b≠a:F(x_{1}^{b}, . . . ,x_{j}^{b})=0 (63)
(64)
Also, for all j, F(x_{1}^{0}, . . . , x_{j}^{0})=0. Therefore, to ensure (Q, C) independence, it is enough to set C=1/2Σ_{i=0}^{D−1}g(i)−δ for any δ>0. Then, by Lemma 2:
Since the decay function g is nonnegative:
This result is formulated as the main lower bound theorem, Theorem 7. Assume there exists an εdifferentially private algorithm A that at time step j outputs {circumflex over (F)}(x_{1}, . . . , x_{j}). Assume further that for any Q⊂Q=q, we have:
Pr[∀jεQ:{circumflex over (F)}(x_{1}, . . . ,x_{j})−F(x_{1}, . . . ,x_{j})≦C]≧2/3, (67)
where F is the decayed sum induced by g. Denote G(x)=Σ_{i=0}^{z−1}g(i). Then, for log q/ε=O(α/(1−α)):
For the three problems considered herein, the following corollaries are derived.
The first corollary, Corollary 1 states: assume there exists an εdifferentially private algorithm A that at time step j outputs {circumflex over (F)}_{w}(j,W). Assume further that for any Q⊂, we have:
Note that the lower bound of a known algorithm is a special case of the above corollary for q=W=T.
The second corollary, Corollary 2, states: assume there exists an εdifferentially private algorithm A that at time step j outputs {circumflex over (F)}_{e}(j,α). Assume further that for any Q⊂, we have:
Pr[∀jεQ:{circumflex over (F)}_{e}(j,α)−F_{e}(j,α)≦C]≧2/3. (71)
Proof is established by Theorem 7, where:
then use the inequality e^{−x}≦C′(1−x) for some constant C′. We get:
Since the right hand side of Equation 73 is monotonically increasing in log q, for
we have
The third corollary, Corollary 3, states: assume there exists an εdifferentially private algorithm A that at time step j outputs ij, c). Assume further that for any Q⊂, we have:
Pr[∀jεQ:{circumflex over (F)}_{p}(j,c)−F_{p}(j,c)≦C]≧2/3. (76)
then:
where H_{c}(k) is the kth generalized harmonic number in power c.
In general, the algorithms described herein can be used in methods and systems that provide differential privacy guarantees with an improved privacyaccuracy tradeoff. For example, the sums can be functions that can be used in recommendation systems. The algorithms can be the basis for recommendation systems with differentially private guarantees and better recommendation accuracy.
There have thus been described certain examples and embodiments of methods to provide enhanced privacy protection for continually updated data. While embodiments have been described and disclosed, it will be appreciated that modifications of these embodiments are within the true spirit and scope of the invention. All such modifications are intended to be covered by the invention
As described herein, the methods described herein are not limited to any particular element(s) that perform(s) any particular function(s) and some steps of the methods presented need not necessarily occur in the order shown. For example, in some cases two or more method steps can occur in a different order or simultaneously. In addition, some steps of the described methods can be optional (even if not explicitly stated to be optional) and, therefore, can be omitted. These and other variations of the methods disclosed herein will be readily apparent, especially in view of the description of the method described herein, and are considered to be within the full scope of the invention.
Although features and elements are described above in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features and elements.
In view of the above, the foregoing merely illustrates the principles of the invention and it will thus be appreciated that those skilled in the art will be able to devise numerous alternative arrangements which, although not explicitly described herein, embody the principles of the invention and are within its spirit and scope. For example, although illustrated in the context of separate functional elements, these functional elements can be embodied in one, or more, integrated circuits (ICs). Similarly, although shown as separate elements, any or all of the elements can be implemented in a storedprogramcontrolled processor, e.g., a digital signal processor, which executes associated software, e.g., corresponding to one, or more, of the steps shown in, e.g.,