DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This office action is in response to Applicant’s communication filed on 03/30/2026. Claims 1-20 have been examined.
Response to Arguments
Applicant’s arguments, see Remarks – Pages 20-22 , filed on 03/30/2026 , with respect to the rejections of claims under 103 have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new grounds of rejection is made in view of Krishnaram.
With regards to 101 rejection, Applicant’s amendments/arguments overcome the rejection. Therefore, the rejection is withdrawn.
With regards to 112 rejection, Applicant’s amendments overcome the rejection. Therefore, the rejection is withdrawn.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-5,7,9-15,17-20 are rejected under 35 U.S.C. 103 as being unpatentable over EIDE et al. Publication No. US 2018/0052894 A1 ( EIDE hereinafter) in view of Krishnaram et al. “PriPeARL: A Framework for Privacy _Preserving Analytics and Reporting at LinkedIn ( Krishnaram hereinafter) further in view of Poh et al. Publication No. US 2025/0061224 A1 ( Poh hereinafter)
Regarding claim 1,
EIDE teaches a computer-implemented method comprising:
receiving an aggregation query of a predetermined query type, wherein the aggregation query targets a particular database table (¶0011 - the present invention provide a system having, and/or a method using, an anonymization module whose input is a query, whose output is a perturbed statistical answer, and which interacts with a data store by requesting tables consisting of rows and columns; ¶ 0033 - A query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others – See Also ¶ 0059).
obtaining a first true output for an execution of the aggregation query against the particular database table (Fig.5,¶ 0011 - Aspects of the present invention provide a system having, and/or a method using, an anonymization module whose input is a query, whose output is a perturbed statistical answer, and which interacts with a data store by requesting tables consisting of rows and columns – ¶ 0029 - Additionally, an analyst may learn exact answer values using a series of query pairs whereby one query includes a condition, and the other query the inverse of that condition. Each pair when summed produces a noisy count. When the sequence of pairs is averaged, the noise may be eliminated and an exact count produced - ¶ 0041 - Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property).
determining a first deterministic pseudorandom noise value based on the aggregation query and first state data reflecting a state of data stored in the particular database table used to generate the first true output for the execution of the aggregation query against the particular database table [..] (¶ 0037 - As will be appreciated, certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution - ¶ 0038 – ¶ 0041 -Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise - the cloak controls the value of a fixed-random number by controlling the value used to seed a Pseudo-Random Number Generator (PRNG). the cloak uses information derived from the query itself, in full or in part, to control the fixed-random number – ¶ 0096 - the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries).
determining a first noisy output based on the first true output and the first deterministic pseudorandom noise value (Fig.3, ¶ 0049 - In an embodiment, fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560 – ¶ 0091 - As will be appreciated that the use of noise elements for generating fixed noise and fixed thresholds as described in this patent may be combined with alternate query exploration. In an embodiment, if alternate query exploration for a given attack component determines that the resulting queries are distant queries, then the noise element associated with the attack component may be excluded from the set of noise elements. In this way, it is possible to reduce the amount of noise in an answer);
receiving an additional aggregation query of the predetermined query type, wherein the additional aggregation query targets the particular database table (¶ 0090 - As will be appreciated, embodiments of the present invention may determine the difference in the number of distinct UIDs in the answers between a given query and alternate queries that could be formed by either removing individual attack components – ¶ 0011- The module therefore defends against attacks that use the difference between queries to infer information about individual users - ¶ 0033 - A query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others – See Also ¶ 0059);
subsequent to receiving the additional aggregation query, obtaining a second true output for an execution of the additional aggregation query against the particular database table (¶ 0029 - the answers to two queries that differ by a single or only a few users may be made identical – ¶ 0041 - Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property. Non-Gaussian distributions may also be used. Other means could also in principle be used – See Also - ¶ 0043 – ¶ 0045).
determining second state data reflecting a state of data stored in the particular database table used to generate the second true output for the execution of the additional aggregation query against the particular database table; determining a second deterministic pseudorandom noise value based on the additional aggregation query and the second state data [..] ( (¶ 0037 - As will be appreciated, certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution - ¶ 0038 – ¶ 0041 -Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise - the cloak controls the value of a fixed-random number by controlling the value used to seed a Pseudo-Random Number Generator (PRNG). the cloak uses information derived from the query itself, in full or in part, to control the fixed-random number – ¶ 0096 - the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries);
determining a second noisy output based on the second deterministic pseudorandom noise value (Fig.3, ¶ 0049 - In an embodiment, fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560 – ¶ 0091 - As will be appreciated that the use of noise elements for generating fixed noise and fixed thresholds as described in this patent may be combined with alternate query exploration. In an embodiment, if alternate query exploration for a given attack component determines that the resulting queries are distant queries, then the noise element associated with the attack component may be excluded from the set of noise elements. In this way, it is possible to reduce the amount of noise in an answer);
However, EIDE does not explicitly teach
determining a first deterministic pseudorandom noise value based on a predetermined secret value, and a privacy parameter controlling a scale of generated noise , determining a second deterministic pseudorandom noise value based on the predetermined secret value, and the privacy parameter, causing the second noisy output to be displayed to a graphical user interface of a device.
Krishnaram teaches
determining a first deterministic pseudorandom noise value based on a predetermined secret value, and a privacy parameter controlling a scale of generated noise , determining a second deterministic pseudorandom noise value based on the predetermined secret value, and the privacy parameter (Section 3.1 Due to this reason and also for ensuring consistency of that answer when the same query is repeated, we chose to use a deterministic, pseudorandom noise generation algorithm. The idea is that the noise value chosen for a query is fixed to that query, or the same noise is assigned when the same query is repeated. Given the statistical query, the desired privacy parameter, and the fixed secret, we generate a (fixed) pseudorandom rounded noise from the appropriate Laplace distribution using Algorithm 1. First, the secret and the query parameters are given as input to the deterministic function, Generate Pseudorand Frac, which returns a pseudorandom fraction between 0 and 1. Treating this obtained fraction as sampled from the uniform distribution on (0,1), we apply the inverse cumulative distribution function (cdf) for the appropriate Laplace distribution to get the pseudorandom noise. Finally, we round the noise to the nearest integer since it is desirable for the reported noisy counts to be integers. – Sections 3 . Theorem 3.3. [11] Given a query function f : the randomized mechanism K that adds noise drawn independently from the Laplace distribution with parameter Delta (f)/ ϵ to each of the d dimensions of f(D) satisfies ϵ differential privacy - an algorithm for generating pseudorandom rounded noise from Laplace distribution for a given query (Algorithm 1), followed by an algorithm for computing noisy count for certain canonical queries (Algorithm 2), and finally the main algorithm for privacy-preserving analytics computation (Algorithm 3), which builds on the first two algorithms. - Section 4 – Formally, this guarantee is achieved by adding appropriate noise (e.g., from Laplace distribution) to the true answer of a statistical query function (e.g., the number of members that clicked on an article, or the histogram of titles of members that clicked on an article), and releasing the noisy answer. The magnitude of the noise to be added depends on the L1 sensitivity of the query (namely, the upper bound on the extent to which the query output can change, e.g., when a member is added to or removed from the dataset), and the desired level of privacy guarantee (ϵ) – See Also Section 3.2, Note: generating pseudorandfrac that takes a fixed predetermined secret (s) and privacy parameter to yield a fraction . This fraction is fed into the inverse cdf of LaPlace distribution ,where the privacy parameter(ϵ) controls the variance/scale of the resulting pseudorandom noise (ar = -1/ ϵ…)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Krishnaram. The motivation for doing so is to allow the system to incorporate techniques such as deterministic pseudorandom noise generation to address certain limitations of standard differential privacy and performs post-processing to achieve data consistency (Krishnaram – Section 1).
Poh teaches
causing the second noisy output to be displayed to a graphical user interface of a device (Fig.2 -6 shows displaying noisy output to a GUI – ¶ 0068 - FIGS. 4-7 illustrate various examples of the relationship between noise level and model performance according to embodiments of the present disclosure. Referring to
FIG. 4, a graph 400 is illustrated, which represents the relationship between model performance versus noise level for data corresponding to a sensitive attribute of "customer intent". The graph 400 includes an X-axis and a Y-axis. The X-axis corresponds to a noise level, for example, an amount of noise added by the noise-addition sub-module 240 to generate the noise-added data 250 (see FIG. 1). The Y-axis corresponds to a model performance, for example, a prediction of a binary classification model to predict a user's Net Promoter Score (NPS), where 1 =detractor, and 0=[promoter, passive]. In some embodiments, the binary classification model may be trained using a machine learning model based on a sufficiently large amount of noise-added data similar to the noise-added data 250 of FIG. 1. ).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Poh. The motivation for doing so is to allow the system to analyze a trend associated with the sensitive data based on using the outputted noise-added sensitive data (¶ 0023 -¶ 0024, Claim 16 – Poh) .
Regarding claim 2,
EIDE further teaches
wherein: the additional aggregation query is different from the aggregation query, the additional aggregation query having at least one of: different query parameters, a different aggregation function, or different filtering conditions than the aggregation query; and the second deterministic pseudorandom noise value is different from the first deterministic pseudorandom noise value due to at least one of: the difference between the additional aggregation query and the aggregation query, or a change in the state of data stored in the particular database table between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0004 – the analyst may make the following two queries: 1) "what is the sum of the salaries of all males?", and 2) "what is the sum of the salaries of all males not born on Dec. 14, 1957 and not having zip code 67663" The first query includes all males, whereas the second query includes all males except the victim – ¶ 0028 - the answers to two queries that differ by a single or only a few users may be made identical. Such an approach, however, may require significant computation (processing power) and memory resources to determine by what amount an original analyst query and the modified query differ. When a query condition such as "WHERE salary=1000 is removed from the query, then the resulting answer may contain many times more rows than the original query that contained the condition – ¶ 0029 - an analyst may learn exact answer values using a series of query pairs whereby one query includes a condition, and the other query the inverse of that condition. Each pair when summed produces a noisy count. When the sequence of pairs is averaged – ¶0013 - The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements).
Regarding claim 3,
EIDE further teaches
wherein: the additional aggregation query is identical to the aggregation query; and the second deterministic pseudorandom noise value is identical to the first deterministic pseudorandom noise value, the method further comprises: determining that the second true output is identical to the first true output; and determining that the second noisy output is identical to the first noisy output (¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 - Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. In one embodiment, the noise element is taken from a zero-mean Gaussian distribution – ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak – ¶ 0077- This embodiment illustrates the three principles of answer perturbation. First, it is a fixed operation: the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer);
the second state data is identical to the first state data, indicating that the state of data stored in the particular database table was unchanged between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0096 - In an embodiment, the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries =See Also ¶ 109- ¶ 0110);
Regarding claim 4,
EIDE further teaches
wherein: the second state data is different from the first state data, indicating that the state of data stored in the particular database table has changed between the execution of the aggregation query and the execution of the additional aggregation query; the second deterministic pseudorandom noise value is different from the first deterministic pseudorandom noise value due to the difference between the second state data and the first state data (¶ 0013 - In an embodiment, the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise);
the method further comprises: detecting the change in the state of data stored in the particular database table by comparing the second state data to the first state data; determining that the second true output is different from the first true output based on the detected change in the state of data; and generating the second deterministic pseudorandom noise value using a noise generation function that takes the second state data as an input, (¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0077- the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer. If the selected users in step 365 all have the same value, then
the answer is shared by an adequate number of users (2T +1). If the selected users in step 365 do not all have the same value, then the answer is a composite from the number of users. Either way, the answer is based on a fixed threshold number of users – ¶ 0094 – ¶0096 - Suppose that at time T, the analyst makes a query. At time Tl, after time T, the data for a single user is modified, for instance through addition, deletion, or change of an existing value. At time T2, after time Tl, the same query is repeated. If the answer to the second query differs from that of the first query, then it is because the modified data matched the conditions of the query- ¶ 0104 – when the cloak first receives a standing query, it provides an answer. Subsequently, every time a change occurs to the database, the cloak may determine if the change would result in a modification to the answer. If the answer is yes, then the cloak records the identity of the user to which the change applies. When the number of distinct users exceeds a threshold, the cloak provides a new answer that includes all of the changes since the last provided answer).
Regarding claim 5,
EIDE further teaches
wherein: the second state data is identical to the first state data, indicating that the state of data stored in the particular database table has not changed between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0009 - repeated identical queries may be useful and important in cases for instance where the contents of a database are constantly changing, so that identical queries may produce different results at different times. – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise – ¶0092 - if a given query and an alternate query are found to be nearby queries, then the cloak may adjust the rows of the given query so that the output of the given query is identical to the alternate query. This operation is called "row adjustment" . As will be appreciated, row adjustment defends against a difference attack by forcing the two queries of the difference attack to be identical whether or not there is a difference between the two queries); ¶ 0096 the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries – ¶ 0103 – ¶ 0104 - will be appreciated, the analyst could repeat the same query at each epoch to obtain up-to-date answers. Further, the cloak could, on its own accord, provide the answer to a given query at each epoch. A query whereby the cloak provides periodic answers is called a standing query );
the second deterministic pseudorandom noise value is identical to the first deterministic pseudorandom noise value due to: the identity between the second state data and the first state data, and the use of a deterministic noise generation function that produces the same output for identical inputs; the method further comprises: determining that the state of data stored in the particular database table was unchanged by comparing the second state data to the first state data; and reusing the first deterministic pseudorandom noise value as the second deterministic pseudorandom noise value without regenerating the first deterministic pseudorandom noise value (¶ 0013 - In an embodiment, the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements - ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 -Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. Two attack components are considered the same if they have the same semantics. So for instance, the attack components are considered the same, and the corresponding noise elements would be derived from the same seed – See ¶ 0072, ¶ 0077 - principles of answer perturbation. First, it is a fixed operation: the same fixed threshold produces the same answer – ¶ 0096 -the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries).
Regarding claim 7,
EIDE further teaches
wherein the predetermined query type comprises at least one of: a COUNT query that returns a number of rows meeting specified criteria, a SUM query that calculates a total of values in a specified column, an AVERAGE query that computes a mean value of a specified column, a MIN query that returns a minimum value in a specified column, a MAX query that returns a maximum value in a specified column, a DISTINCT COUNT query that counts unique values in a specified column, a PERCENTILE query that returns a value at a specified percentile of a dataset, a GROUP BY query with aggregation that performs aggregations on grouped data, a HAVING query that filters results of a GROUP BY query based on aggregate values, a window function query that performs calculations across a set of table rows related to the current row, or a time-based aggregation query that aggregates data over specified time periods (Fig.3,¶ 0033 - query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others. -See ¶ 0057-¶ 0058 - For example, suppose that the cloak receives the query [SELECT count(*) FROM table WHERE salary= 100000] – ¶ 0071 - for each statistical operation (count, sum, avg, etc.), there may be a variety of possible methods for answer perturbation).
Regarding claim 9,
EIDE further teaches
wherein each of the first state data and the second state data comprises at least one of: a hash value of data stored in the particular database table, a hash value of a subset of data used to generate a respective true output, a last update timestamp of the particular database table, a row count of the particular database table, a size in bytes of the particular database table, a checksum of column values relevant to a respective aggregation query, a Bloom filter representation of contents of the particular database table, a version number or incrementing counter associated with the particular database table, a set of summary statistics of data in the particular database table, including at least one of a minimum value, maximum value, mean, median, or standard deviation of one or more columns; metadata of a log-structured merge-tree associated with the particular database table, a range of timestamps present in data of the particular database table, a count of distinct values in one or more columns of the particular database table, a sketching data structure summarizing contents of the particular database table, or a combination of two or more of the above data types (¶ 0060-the cloak uses all of the distinct values from the requested column to derive the seed component. In an embodiment, each distinct value is hashed, and the resulting hashed values are combined with XOR operations to produce the seed component. Other embodiments for deriving the seed component from the values reported by the database for the column used in the attack component . the cloak generates a seed component from one or more constants that appear in the attack component. For instance, in the attack component salary=l000OO], 100000 is a constant. In an embodiment, each of the one or more constants are hashed and combined with an XOR function - ¶ 0096 – ¶ 0098 -the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries - time epochs are organized hierarchically, with higher-level epochs encompassing lower-level epochs. For instance, the lowest-level time epoch 600 may be a day. The next higher level time epoch 605 may be two days, and so on. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last lowest-level epoch).
Regarding claim 10,
EIDE does not explicitly teach
wherein causing the second noisy output to be displayed to a graphical user interface of a device comprises at least one of: presenting the second noisy output as a numerical value with a specified number of significant figures or decimal places; displaying the second noisy output in a chart or graph, wherein the chart or graph is at least one of a bar chart, line graph, pie chart, histogram, scatter plot, or heatmap; presenting the second noisy output in a table or grid format, optionally alongside other related data or query results; providing an interactive visualization that allows a user to explore the second noisy output through zooming, filtering, or drill-down operations; displaying the second noisy output with accompanying confidence intervals or error bounds that reflect added noise; presenting the second noisy output alongside the first noisy output to show trends or changes over time; color-coding or otherwise visually emphasizing the second noisy output based on its value or relationship to predefined thresholds; displaying the second noisy output with annotations or tooltips that provide context or explanations about a privacy-preserving nature of a result; providing options for the user to switch between different visual representations of the second noisy output; or displaying the second noisy output as part of a dashboard that includes multiple privacy-preserved query results
However, Poh teaches
wherein causing the second noisy output to be displayed to a graphical user interface of a device comprises at least one of: presenting the second noisy output as a numerical value with a specified number of significant figures or decimal places; displaying the second noisy output in a chart or graph, wherein the chart or graph is at least one of a bar chart, line graph, pie chart, histogram, scatter plot, or heatmap; presenting the second noisy output in a table or grid format, optionally alongside other related data or query results; providing an interactive visualization that allows a user to explore the second noisy output through zooming, filtering, or drill-down operations; displaying the second noisy output with accompanying confidence intervals or error bounds that reflect added noise; presenting the second noisy output alongside the first noisy output to show trends or changes over time; color-coding or otherwise visually emphasizing the second noisy output based on its value or relationship to predefined thresholds; displaying the second noisy output with annotations or tooltips that provide context or explanations about a privacy-preserving nature of a result; providing options for the user to switch between different visual representations of the second noisy output; or displaying the second noisy output as part of a dashboard that includes multiple privacy-preserved query results(Fig.2 -6 shows displaying noisy output to a GUI – ¶ 0068 - FIGS. 4-7 illustrate various examples of the relationship between noise level and model performance according to embodiments of the present disclosure. Referring to FIG. 4, a graph 400 is illustrated, which represents the relationship between model performance versus noise level for data corresponding to a sensitive attribute of "customer intent". The graph 400 includes an X-axis and a Y-axis. The X-axis corresponds to a noise level, for example, an amount of noise added by the noise-addition sub-module 240 to generate the noise-added data 250 (see FIG. 1). The Y-axis corresponds to a model performance, for example, a prediction of a binary classification model to predict a user's Net Promoter Score (NPS), where 1 =detractor, and 0=[promoter, passive]. In some embodiments, the binary classification model may be trained using a machine learning model based on a sufficiently large amount of noise-added data similar to the noise-added data 250 of FIG. 1. ).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Poh. The motivation for doing so is to allow the system to analyze a trend associated with the sensitive data based on using the outputted noise-added sensitive data (¶ 0023 -¶ 0024, Claim 16 – Poh) .
Regarding claim 11,
EIDE teaches a system comprising:
a set of one or more hardware processors; and a set of instructions stored on a set of one or more non-transitory computer-readable media that , when processed by the set of one or more hardware processors, cause the set of one or more hardware processors to perform operations, the operations comprising: receiving an aggregation query of a predetermined query type, wherein the aggregation query targets a particular database table; (¶ 0011 - the present invention provide a system having, and/or a method using, an anonymization module whose input is a query, whose output is a perturbed statistical answer, and which interacts with a data store by requesting tables consisting of rows and columns; ¶ 0033 - A query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others – See Also ¶ 0059);
obtaining a first true output for an execution of the aggregation query against the particular database table (Fig.5,¶ 0011 - Aspects of the present invention provide a system having, and/or a method using, an anonymization module whose input is a query, whose output is a perturbed statistical answer, and which interacts with a data store by requesting tables consisting of rows and columns – ¶ 0029 - Additionally, an analyst may learn exact answer values using a series of query pairs whereby one query includes a condition, and the other query the inverse of that condition. Each pair when summed produces a noisy count. When the sequence of pairs is averaged, the noise may be eliminated and an exact count produced - ¶ 0041 - Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property);
determining a first deterministic pseudorandom noise value based on the aggregation query and first state data reflecting a state of data stored in the particular database table used to generate the first true output for the execution of the aggregation query against the particular database table [..] (¶ 0037 - As will be appreciated, certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated ¶meters, for instance a Gaussian distribution with parameters mean and standard distribution - ¶ 0038 – ¶ 0041 -Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise - the cloak controls the value of a fixed-random number by controlling the value used to seed a Pseudo-Random Number Generator (PRNG). the cloak uses information derived from the query itself, in full or in part, to control the fixed-random number – ¶ 0096 - the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries);
determining a first noisy output based on the first true output and the first deterministic pseudorandom noise value (Fig.3, ¶ 0049 - In an embodiment, fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560 – ¶ 0091 - As will be appreciated that the use of noise elements for generating fixed noise and fixed thresholds as described in this patent may be combined with alternate query exploration. In an embodiment, if alternate query exploration for a given attack component determines that the resulting queries are distant queries, then the noise element associated with the attack component may be excluded from the set of noise elements. In this way, it is possible to reduce the amount of noise in an answer);
receiving an additional aggregation query of the predetermined query type, wherein the additional aggregation query targets the particular database table (¶ 0090 - As will be appreciated, embodiments of the present invention may determine the difference in the number of distinct UIDs in the answers between a given query and alternate queries that could be formed by either removing individual attack components – ¶ 0011- The module therefore defends against attacks that use the difference between queries to infer information about individual users - ¶ 0033 - A query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others – See Also ¶ 0059);
subsequent to receiving the additional aggregation query, obtaining a second true output for an execution of the additional aggregation query against the particular database table, (¶ 0029 - the answers to two queries that differ by a single or only a few users may be made identical – ¶ 0041 - Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property. Non-Gaussian distributions may also be used. Other means could also in principle be used – ¶ 0043 – ¶ 0045);
determining second state data reflecting a state of data stored in the particular database table used to generate the second true output for the execution of the additional aggregation query against the particular database table; determining a second deterministic pseudorandom noise value based on the additional aggregation query and the second state data [..] (¶ 0037 - As will be appreciated, certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution - ¶ 0038 – ¶ 0041 -Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise - the cloak controls the value of a fixed-random number by controlling the value used to seed a Pseudo-Random Number Generator (PRNG). the cloak uses information derived from the query itself, in full or in part, to control the fixed-random number – ¶ 0096 - the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries);
determining a second noisy output based on the second deterministic pseudorandom noise value (Fig.3, ¶ 0049 - In an embodiment, fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560 – ¶ 0091 - As will be appreciated that the use of noise elements for generating fixed noise and fixed thresholds as described in this patent may be combined with alternate query exploration. In an embodiment, if alternate query exploration for a given attack component determines that the resulting queries are distant queries, then the noise element associated with the attack component may be excluded from the set of noise elements. In this way, it is possible to reduce the amount of noise in an answer).
However, EIDE does not explicitly teach
determining a first deterministic pseudorandom noise value based on a predetermined secret value, and a privacy parameter controlling a scale of generated noise , determining a second deterministic pseudorandom noise value based on the predetermined secret value, and the privacy parameter; causing the second noisy output to be stored in a database.
Krishnaram teaches
determining a first deterministic pseudorandom noise value based on a predetermined secret value, and a privacy parameter controlling a scale of generated noise , determining a second deterministic pseudorandom noise value based on the predetermined secret value, and the privacy parameter (Section 3.1 Due to this reason and also for ensuring consistency of that answer when the same query is repeated, we chose to use a deterministic, pseudorandom noise generation algorithm. The idea is that the noise value chosen for a query is fixed to that query, or the same noise is assigned when the same query is repeated. Given the statistical query, the desired privacy parameter, and the fixed secret, we generate a (fixed) pseudorandom rounded noise from the appropriate Laplace distribution using Algorithm 1. First, the secret and the query parameters are given as input to the deterministic function, Generate Pseudorand Frac, which returns a pseudorandom fraction between 0 and 1. Treating this obtained fraction as sampled from the uniform distribution on (0,1), we apply the inverse cumulative distribution function (cdf) for the appropriate Laplace distribution to get the pseudorandom noise. Finally, we round the noise to the nearest integer since it is desirable for the reported noisy counts to be integers. – Sections 3 . Theorem 3.3. [11] Given a query function f : the randomized mechanism K that adds noise drawn independently from the Laplace distribution with parameter Delta (f)/ ϵ to each of the d dimensions of f(D) satisfies ϵ differential privacy - an algorithm for generating pseudorandom rounded noise from Laplace distribution for a given query (Algorithm 1), followed by an algorithm for computing noisy count for certain canonical queries (Algorithm 2), and finally the main algorithm for privacy-preserving analytics computation (Algorithm 3), which builds on the first two algorithms. - Section 4 – Formally, this guarantee is achieved by adding appropriate noise (e.g., from Laplace distribution) to the true answer of a statistical query function (e.g., the number of members that clicked on an article, or the histogram of titles of members that clicked on an article), and releasing the noisy answer. The magnitude of the noise to be added depends on the L1 sensitivity of the query (namely, the upper bound on the extent to which the query output can change, e.g., when a member is added to or removed from the dataset), and the desired level of privacy guarantee (ϵ) – See Also Section 3.2, Note: generating pseudorandfrac that takes a fixed predetermined secret (s) and privacy parameter to yield a fraction . This fraction is fed into the inverse cdf of LaPlace distribution ,where the privacy parameter(ϵ) controls the variance/scale of the resulting pseudorandom noise (ar = -1/ ϵ…)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Krishnaram. The motivation for doing so is to allow the system to incorporate techniques such as deterministic pseudorandom noise generation to address certain limitations of standard differential privacy and performs post-processing to achieve data consistency (Krishnaram – Section 1).
Poh teaches
causing the second noisy output to be stored in a database (¶ 0099 - the embedding of the obfuscated data, the implementation flow 920 may apply noise to the embedded data in response to database queries for the embedded data. The embedded data, after being applied with the noise, may still be stored in their respective partitions A-C. – ¶ 0097 - The noisy data output generated by the step 935 is available to the user or operator of the electronic database on which the obfuscated data is stored. As such, the noisy data output generated by the step 935 may still be used in data analytics, for example via machine learning models – ¶ 0057 - In some other embodiments, noise may also be added to the embedded data 230 before the embedded data 230 is stored in the electronic database.).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Poh. The motivation for doing so is to allow the system to analyze a trend associated with the sensitive data based on using the outputted noise-added sensitive data (¶ 0023 -¶ 0024, Claim 16 – Poh) .
Regarding claim 12,
EIDE further teaches
wherein: the additional aggregation query is different from the aggregation query, the additional aggregation query having at least one of: different query parameters, a different aggregation function, or different filtering conditions than the aggregation query; and the second deterministic pseudorandom noise value is different from the first deterministic pseudorandom noise value due to at least one of: the difference between the additional aggregation query and the aggregation query, or a change in the state of data stored in the particular database table between the execution of the aggregation query and the execution of the additional aggregation query. (¶ 0004 – the analyst may make the following two queries: 1) "what is the sum of the salaries of all males?", and 2) "what is the sum of the salaries of all males not born on Dec. 14, 1957 and not having zip code 67663" The first query includes all males, whereas the second query includes all males except the victim – ¶ 0028 - the answers to two queries that differ by a single or only a few users may be made identical. Such an approach, however, may require significant computation (processing power) and memory recourses to determine by what amount an original analyst query and the modified query differ. When a query condition such as "WHERE salary=1000 is removed from the query, then the resulting answer may contain many times more rows than the original query that contained the condition – ¶ 0029 - an analyst may learn exact answer values using a series of query pairs whereby one query includes a condition, and the other query the inverse of that condition. Each pair when summed produces a noisy count. When the sequence of pairs is averaged - ¶0013 - The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements).
Regarding claim 13,
EIDE further teaches
wherein: the additional aggregation query is identical to the aggregation query; and the second deterministic pseudorandom noise value is identical to the first deterministic pseudorandom noise value and the system further comprises a set of instructions stored on a set of one or more non-transitory computer-readable media and configured to perform: determining that the second true output is identical to the first true output; and determining that the second noisy output is identical to the first noisy output. (¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 - Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. In one embodiment, the noise element is taken from a zero-mean Gaussian distribution – ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak – ¶ 0077- This embodiment illustrates the three principles of answer perturbation. First, it is a fixed operation: the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer);
the second state data is identical to the first state data, indicating that the state of data stored in the particular database table was unchanged between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0096 - In an embodiment, the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries =See ¶ 109- ¶ 0110).
Regarding claim 14,
EIDE further teaches
wherein: the second state data is different from the first state data, indicating that the state of data stored in the particular database table has changed between the execution of the aggregation query and the execution of the additional aggregation query; the second deterministic pseudorandom noise value is different from the first deterministic pseudorandom noise value due to the difference between the second state data and the first state data (¶ 0013 - In an embodiment, the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise);
the method further comprises: detecting the change in the state of data stored in the particular database table by comparing the second state data to the first state data; determining that the second true output is different from the first true output based on the detected change in the state of data; and generating the second deterministic pseudorandom noise value using a noise generation function that takes the second state data as an input, (¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0077- the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer. If the selected users in step 365 all have the same value, then
the answer is shared by an adequate number of users (2T +1). If the selected users in step 365 do not all have the same value, then the answer is a composite from the number of users. Either way, the answer is based on a fixed threshold number of users – ¶ 0094 – Par a0096 - Suppose that at time T, the analyst makes a query. At time Tl, after time T, the data for a single user is modified, for instance through addition, deletion, or change of an existing value. At time T2, after time Tl, the same query is repeated. If the answer to the second query differs from that of the first query, then it is because the modified data matched the conditions of the query- ¶ 0104 – when the cloak first receives a standing query, it provides an answer. Subsequently, every time a change occurs to the database, the cloak may determine if the change would result in a modification to the answer. If the answer is yes, then the cloak records the identity of the user to which the change applies. When the number of distinct users exceeds a threshold, the cloak provides a new answer that includes all of the changes since the last provided answer).
Regarding claim 15,
EIDE further teaches
wherein: the second state data is identical to the first state data, indicating that the state of data stored in the particular database table has not changed between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0009 - repeated identical queries may be useful and important in cases for instance where the contents of a database are constantly changing, so that identical queries may produce different results at different times. – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise – ¶0092 - if a given query and an alternate query are found to be nearby queries, then the cloak may adjust the rows of the given query so that the output of the given query is identical to the alternate query. This operation is called "row adjustment" . As will be appreciated, row adjustment defends against a difference attack by forcing the two queries of the difference attack to be identical whether or not there is a difference between the two queries); ¶ 0096 the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries – ¶ 0103 – ¶ 0104 - will be appreciated, the analyst could repeat the same query at each epoch to obtain up-to-date answers. Further, the cloak could, on its own accord, provide the answer to a given query at each epoch. A query whereby the cloak provides periodic answers is called a standing query );
the second deterministic pseudorandom noise value is identical to the first deterministic pseudorandom noise value due to: the identity between the second state data and the first state data, and the use of a deterministic noise generation function that produces the same output for identical inputs; the method further comprises: determining that the state of data stored in the particular database table was unchanged by comparing the second state data to the first state data; and reusing the first deterministic pseudorandom noise value as the second deterministic pseudorandom noise value without regenerating the first deterministic pseudorandom noise value (¶ 0013 - the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements - ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0077- the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer. If the selected users in step 365 all have the same value, then the answer is shared by an adequate number of users – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 -Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. Two attack components are considered the same if they have the same semantics. So for instance, the attack components [ salary= 100000] and [ salary=2 * 50000] are considered the same, and the corresponding noise elements would be derived from the same seed – ¶ 0096 -the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries).
Regarding claim 17,
EIDE teaches a set of one or more non-transitory computer-readable media storing instructions which, when processed by a set of one or more processors, cause the set of one or more processors to perform operations comprising:
receiving an aggregation query of a predetermined query type, wherein the aggregation query targets a particular database table (¶ 0011 - the present invention provide a system having, and/or a method using, an anonymization module whose input is a query, whose output is a perturbed statistical answer, and which interacts with a data store by requesting tables consisting of rows and columns; ¶ 0033 - A query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others – See Also ¶ 0059);
obtaining a first true output for an execution of the aggregation query against the particular database table (Fig.5,¶ 0011 - Aspects of the present invention provide a system having, and/or a method using, an anonymization module whose input is a query, whose output is a perturbed statistical answer, and which interacts with a data store by requesting tables consisting of rows and columns – ¶ 0029 - Additionally, an analyst may learn exact answer values using a series of query pairs whereby one query includes a condition, and the other query the inverse of that condition. Each pair when summed produces a noisy count. When the sequence of pairs is averaged, the noise may be eliminated and an exact count produced - ¶ 0041 - Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property);
determining a first deterministic pseudorandom noise value based on the aggregation query and first state data reflecting a state of data stored in the particular database table used to generate the first true output for the execution of the aggregation query against the particular database table [..] (¶ 0037 - As will be appreciated, certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution - ¶ 0038 – ¶ 0041 -Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise - the cloak controls the value of a fixed-random number by controlling the value used to seed a Pseudo-Random Number Generator (PRNG). the cloak uses information derived from the query itself, in full or in part, to control the fixed-random number – ¶ 0096 - the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries);
determining a first noisy output based on the first true output and the first deterministic pseudorandom noise value (Fig.3, ¶ 0049 - In an embodiment, fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560 – ¶ 0091 - As will be appreciated that the use of noise elements for generating fixed noise and fixed thresholds as described in this patent may be combined with alternate query exploration. In an embodiment, if alternate query exploration for a given attack component determines that the resulting queries are distant queries, then the noise element associated with the attack component may be excluded from the set of noise elements. In this way, it is possible to reduce the amount of noise in an answer);
receiving an additional aggregation query of the predetermined query type, wherein the additional aggregation query targets the particular database table (¶ 0090 - As will be appreciated, embodiments of the present invention may determine the difference in the number of distinct UIDs in the answers between a given query and alternate queries that could be formed by either removing individual attack components – ¶ 0011- The module therefore defends against attacks that use the difference between queries to infer information about individual users - ¶ 0033 - A query to a data store/database for statistical analysis may be characterized as consisting of two steps. Step 1 selects from among all rows and columns a subset of rows and columns. Step 2 computes a statistical operation over the cells from one or more columns of the selected rows. Typical statistical operations include count (count the number of rows), count distinct ( count the number of distinct cell values), avg (compute the average of cell values), std-dev (compute the standard deviation of cell values), sum, max (select the maximum cell value), min, median, and others – See Also ¶ 0059);
subsequent to receiving the additional aggregation query, obtaining a second true output for an execution of the additional aggregation query against the particular database table (¶ 0029 - the answers to two queries that differ by a single or only a few users may be made identical – ¶ 0041 - Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property. Non-Gaussian distributions may also be used. Other means could also in principle be used – ¶ 0043 – ¶ 0045);
determining second state data reflecting a state of data stored in the particular database table used to generate the second true output for the execution of the additional aggregation query against the particular database table; determining a second deterministic pseudorandom noise value based on the additional aggregation query and the second state data [..] ( (¶ 0037 - As will be appreciated, certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution - ¶ 0038 – ¶ 0041 -Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise - the cloak controls the value of a fixed-random number by controlling the value used to seed a Pseudo-Random Number Generator (PRNG). the cloak uses information derived from the query itself, in full or in part, to control the fixed-random number – ¶ 0096 - the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries).
determining a second noisy output based on the second deterministic pseudorandom noise value (Fig.3, ¶ 0049 - In an embodiment, fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560 – ¶ 0091 - As will be appreciated that the use of noise elements for generating fixed noise and fixed thresholds as described in this patent may be combined with alternate query exploration. In an embodiment, if alternate query exploration for a given attack component determines that the resulting queries are distant queries, then the noise element associated with the attack component may be excluded from the set of noise elements. In this way, it is possible to reduce the amount of noise in an answer).
However, EIDE does not explicitly teach
determining a first deterministic pseudorandom noise value based on a predetermined secret value, and a privacy parameter controlling a scale of generated noise , determining a second deterministic pseudorandom noise value based on the predetermined secret value, and the privacy parameter; causing the second noisy output to be displayed to a graphical user interface of a device.
Krishnaram teaches
determining a first deterministic pseudorandom noise value based on a predetermined secret value, and a privacy parameter controlling a scale of generated noise , determining a second deterministic pseudorandom noise value based on the predetermined secret value, and the privacy parameter (Section 3.1 Due to this reason and also for ensuring consistency of that answer when the same query is repeated, we chose to use a deterministic, pseudorandom noise generation algorithm. The idea is that the noise value chosen for a query is fixed to that query, or the same noise is assigned when the same query is repeated. Given the statistical query, the desired privacy parameter, and the fixed secret, we generate a (fixed) pseudorandom rounded noise from the appropriate Laplace distribution using Algorithm 1. First, the secret and the query parameters are given as input to the deterministic function, Generate Pseudorand Frac, which returns a pseudorandom fraction between 0 and 1. Treating this obtained fraction as sampled from the uniform distribution on (0,1), we apply the inverse cumulative distribution function (cdf) for the appropriate Laplace distribution to get the pseudorandom noise. Finally, we round the noise to the nearest integer since it is desirable for the reported noisy counts to be integers. – Sections 3 . Theorem 3.3. [11] Given a query function f : the randomized mechanism K that adds noise drawn independently from the Laplace distribution with parameter Delta (f)/ ϵ to each of the d dimensions of f(D) satisfies ϵ differential privacy - an algorithm for generating pseudorandom rounded noise from Laplace distribution for a given query (Algorithm 1), followed by an algorithm for computing noisy count for certain canonical queries (Algorithm 2), and finally the main algorithm for privacy-preserving analytics computation (Algorithm 3), which builds on the first two algorithms. - Section 4 – Formally, this guarantee is achieved by adding appropriate noise (e.g., from Laplace distribution) to the true answer of a statistical query function (e.g., the number of members that clicked on an article, or the histogram of titles of members that clicked on an article), and releasing the noisy answer. The magnitude of the noise to be added depends on the L1 sensitivity of the query (namely, the upper bound on the extent to which the query output can change, e.g., when a member is added to or removed from the dataset), and the desired level of privacy guarantee (ϵ) – See Also Section 3.2, Note: generating pseudorandfrac that takes a fixed predetermined secret (s) and privacy parameter to yield a fraction . This fraction is fed into the inverse cdf of LaPlace distribution ,where the privacy parameter(ϵ) controls the variance/scale of the resulting pseudorandom noise (ar = -1/ ϵ…)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Krishnaram. The motivation for doing so is to allow the system to incorporate techniques such as deterministic pseudorandom noise generation to address certain limitations of standard differential privacy and performs post-processing to achieve data consistency (Krishnaram – Section 1).
Poh teaches
causing the second noisy output to be displayed to a graphical user interface of a device (Fig.2 -6 shows displaying noisy output to a GUI – ¶ 0068 - FIGS. 4-7 illustrate various examples of the relationship between noise level and model performance according to embodiments of the present disclosure. Referring to
FIG. 4, a graph 400 is illustrated, which represents the relationship between model performance versus noise level for data corresponding to a sensitive attribute of "customer intent". The graph 400 includes an X-axis and a Y-axis. The X-axis corresponds to a noise level, for example, an amount of noise added by the noise-addition sub-module 240 to generate the noise-added data 250 (see FIG. 1). The Y-axis corresponds to a model performance, for example, a prediction of a binary classification model to predict a user's Net Promoter Score (NPS), where 1 =detractor, and 0=[promoter, passive]. In some embodiments, the binary classification model may be trained using a machine learning model based on a sufficiently large amount of noise-added data similar to the noise-added data 250 of FIG. 1. ).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Poh. The motivation for doing so is to allow the system to analyze a trend associated with the sensitive data based on using the outputted noise-added sensitive data (¶ 0023 -¶ 0024, Claim 16 – Poh) .
Regarding claim 18,
EIDE further teaches
wherein: the additional aggregation query is different from the aggregation query, the additional aggregation query having at least one of: different query parameters, a different aggregation function, or different filtering conditions than the aggregation query; and the second deterministic pseudorandom noise value is different from the first deterministic pseudorandom noise value due to at least one of: the difference between the additional aggregation query and the aggregation query, or a change in the state of data stored in the particular database table between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0004 – the analyst may make the following two queries: 1) "what is the sum of the salaries of all males?", and 2) "what is the sum of the salaries of all males not born on Dec. 14, 1957 and not having zip code 67663" The first query includes all males, whereas the second query includes all males except the victim – ¶ 0028 - the answers to two queries that differ by a single or only a few users may be made identical. Such an approach, however, may require significant computation (processing power) and memory recourses to determine by what amount an original analyst query and the modified query differ. When a query condition such as "WHERE salary=1000 is removed from the query, then the resulting answer may contain many times more rows than the original query that contained the condition – ¶ 0029 - an analyst may learn exact answer values using a series of query pairs whereby one query includes a condition, and the other query the inverse of that condition. Each pair when summed produces a noisy count. When the sequence of pairs is averaged ¶0013 - The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements).
Regarding claim 19,
EIDE further teaches
wherein: the additional aggregation query is identical to the aggregation query; and the set of one or more non-transitory computer-readable media further stores instructions which, when processed by a set of one or more processors, cause: determining that the second true count is identical to the first true count; and determining that the second noisy count is identical to the first noisy count. (¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 - Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. In one embodiment, the noise element is taken from a zero-mean Gaussian distribution – ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak – ¶ 0077- This embodiment illustrates the three principles of answer perturbation. First, it is a fixed operation: the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer);
the second state data is identical to the first state data, indicating that the state of data stored in the particular database table was unchanged between the execution of the aggregation query and the execution of the additional aggregation query (¶ 0096 - In an embodiment, the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries =See ¶ 109- ¶ 0110);
Regarding claim 20,
EIDE further teaches
wherein: the second state data is different from the first state data, indicating that the state of data stored in the particular database table has changed between the execution of the aggregation query and the execution of the additional aggregation query; the second deterministic pseudorandom noise value is different from the first deterministic pseudorandom noise value due to the difference between the second state data and the first state data (¶ 0013 - In an embodiment, the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise, or that two different queries that nevertheless return the same answer have different noise);
the set of one or more non-transitory computer-readable media further stores instructions which, when processed by the set of one or more hardware processors, cause the set of one or more hardware processors:: detecting the change in the state of data stored in the particular database table by comparing the second state data to the first state data; determining that the second true output is different from the first true count based on the detected change in the state of data; and generating the second deterministic pseudorandom noise value using a noise generation function that takes the second state data as an input (¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0077- the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer. If the selected users in step 365 all have the same value, then the answer is shared by an adequate number of users (2T +1). If the selected users in step 365 do not all have the same value, then the answer is a composite from the number of users. Either way, the answer is based on a fixed threshold number of users – ¶ 0094 – Par a0096 - Suppose that at time T, the analyst makes a query. At time Tl, after time T, the data for a single user is modified, for instance through addition, deletion, or change of an existing value. At time T2, after time Tl, the same query is repeated. If the answer to the second query differs from that of the first query, then it is because the modified data matched the conditions of the query- ¶ 0104 – when the cloak first receives a standing query, it provides an answer. Subsequently, every time a change occurs to the database, the cloak ma determine if the change would result in a modification to the answer. If the answer is yes, then the cloak records the identity of the user to which the change applies. When the number of distinct users exceeds a threshold, the cloak provides a new answer that includes all of the changes since the last provided answer).
Claims 6,8,16 are rejected under 35 U.S.C. 103 as being unpatentable over EIDE in view of Krishnaram further in view of Poh further in view of Kostopoulou et al. “Turbo: Effective Caching in Differentially -Private Databases” – 10/23/2023.
Regarding claim 6,
EIDE further teaches
determining that the additional aggregation query is identical to the aggregation query; comparing the second state data to the first state data and determining that they are identical, indicating that the state of data stored in the particular database table is unchanged between the execution of the aggregation query and the execution of the additional aggregation query; in response to determining that the additional aggregation query is identical to the aggregation query and that the second state data is identical to the first state data: reusing the first deterministic pseudorandom noise value as the second deterministic pseudorandom noise value; setting the second noisy output to be identical to the first noisy output(¶ 0013 - In an embodiment, the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements - ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0077- the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer. If the selected users in step 365 all have the same value, then the answer is shared by an adequate number of users– ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 -Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. Two attack components are considered the same if they have the same semantics. So for instance, the attack components [ salary= 100000] and [ salary=2 * 50000] are considered the same, and the corresponding noise elements would be derived from the same seed – ¶ 0096 -the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries).
However, EIDE does not explicitly teach
maintaining a privacy budget associated with at least one of the aggregation query, the particular database table, or a user of the device; forgoing any reduction of the privacy budget that would otherwise occur for executing a new query
Kostopoulou teaches
maintaining a privacy budget associated with at least one of the aggregation query, the particular database table, or a user of the device; forgoing any reduction of the privacy budget that would otherwise occur for executing a new query (Abstract -Turbo builds upon private multiplicative weights (PMW), a DP mechanism that is powerful in theory but ineffective in practice, and transforms it into a highly-effective caching mechanism, PMW-Bypass, that uses prior query results obtained through an external DP mechanism to train a PMW to answer arbitrary future linear queries accurately and “for free” from a privacy perspective – Page 3 -When a query arrives, PMW estimates an answer using the histogram and computes the error of this estimate against the real data in a DP way, using a DP mechanism called sparse vector (SV) [26] (described shortly). If the estimate’s error is low, it is returned to the analyst, consuming no privacy budget (i.e., the query is answered “for free”). If the estimate’s error is large, then PMW executes the DP query on the data with the Laplace/Gaussian mechanism, consuming privacy budget as needed – Page 4 - Given a query, PMW-Bypass uses an effective heuristic to judge whether the histogram is sufficiently trained to answer the query accurately; if so, it uses it, thereby spending no budget ;
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Kostopoulou. The motivation for doing so is to allow the system to store previous queries and their DP results, allowing for direct retrieval of the result without consuming any privacy budget when the same query is seen again on the same database version (Section 3.3 – Caching – Kostopoulou) .
Regarding claim 8,
EIDE further teaches
selecting a probability distribution from a set of predefined distributions, the set comprising at least [..]: a Laplace distribution, a Gaussian distribution, a geometric distribution, a discrete Laplace distribution, a uniform distribution, a truncated Laplace distribution, a truncated Gaussian distribution, an exponential distribution, a Cauchy distribution, or a student's t-distribution (¶ 0037 - certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution – See also ¶ 0041 -Fixed noise refers to the mechanism of adding noise to numerical answers so as to obscure the exact answer. In one embodiment, fixed noise is a fixed-random number with a mean of zero. By using a zero mean, the expected value of the answer is equal to the true answer, which is an important statistical property. Non-Gaussian distributions may also be used. Other means could also in principle be used. ).
wherein determining the first and second deterministic pseudorandom noise values is based on the selecting the probability distribution ( ¶ 0037 - certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution – See Also ¶ 0049)
and wherein a parameter of the selected probability distribution is determined based on the first state data for the first deterministic pseudorandom noise value and the second state data for the second deterministic pseudorandom noise value, respectively( ¶ 0037 - certain operations in answer perturbation require a pseudo-random number. Randomness is generally required to prevent an analyst from establishing concrete facts about the data with high confidence. This pseudo-random number may come from some distribution and its associated parameters, for instance a Gaussian distribution with parameters mean and standard distribution – ¶ 0049 - fixed noise and fixed thresholds may be based on multiple fixed random values. If the fixed noise and fixed threshold use a Gaussian distribution, then the multiple fixed random values are summed to produce the fixed noise or fixed threshold. The individual noise values that includes fixed noise or the fixed threshold are called "noise elements". As will be appreciated, distributions other than Gaussian may be used for noise elements, and operations other than summing may be used to combine the noise
elements – ¶ 0053 - Seed components 515 are generally combined to produce a seed 320, although there are cases where more than one seed can be generated from a given attack component, as illustrated in step 520 of FIG. 4. Each seed is used to generate a noise element 555 (i.e. a pseudo-random Gaussian value), and noise elements are combined to generate the noise 560. ¶ 0072 -In other words, repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these properties may still provide valuable anonymization benefit).
EIDE teaches selecting a probability distribution from a set of predefined distributions, the set comprising at least two of: Gaussian distribution and non gaussian distribution (¶ 0037, ¶ 0041).
However, EIDE does not explicitly teach that the non gaussian distribution is selected from a Laplace distribution, a geometric distribution, a discrete Laplace distribution, a uniform distribution, a truncated Laplace distribution, a truncated Gaussian distribution, an exponential distribution, a Cauchy distribution, or a student's -distribution;
wherein the selection of the probability distribution is based on at least one of: the predetermined query type, a sensitivity of the aggregation query or the additional aggregation query, characteristics of data stored in the particular database table, or a computational efficiency consideration;
Kostopoulou teaches
selecting a probability distribution from a set of predefined distributions, the set comprising at least two of: a Laplace distribution, a Gaussian distribution, a geometric distribution, a discrete Laplace distribution, a uniform distribution, a truncated Laplace distribution, a truncated Gaussian distribution, an exponential distribution, a Cauchy distribution, or a student's t-distribution (Page 3 - Two common mechanisms to enforce DP are the Laplace and Gaussian mechanisms. They add noise from an appropriately scaled Laplace/Gaussian distribution to the true query result, and return the noisy result for counting queries and a database of size 𝑛, adding noise from Laplace(0, 1/𝑛𝜖), ensures (𝜖, 0)-DP (a.k.a. pure DP); adding noise from Gaussian(0, √︁ 2 ln(1.25/𝛿)/𝑛𝜖) ensures (𝜖, 𝛿)-DP. The accuracy for such queries can be controlled probabilistically by converting it into the (𝜖, 𝛿) parameters.
wherein the selection of the probability distribution is based on at least one of: the predetermined query type, a sensitivity of the aggregation query or the additional aggregation query, a desired level of privacy as specified by a privacy parameter, characteristics of data stored in the particular database table, or a computational efficiency consideration (Page 3 - DP and is called parallel composition. Using composition, one can enforce a global (𝜖𝐺, 𝛿𝐺)-DP guarantee over a workload, with each DP query “consuming” part of a global privacy budget that is defined upfront as a system parameter - Two common mechanisms to enforce DP are the Laplace and Gaussian mechanisms. They add noise from an appropriately scaled Laplace/Gaussian distribution to the true query result, and return the noisy result. As an example, for counting queries and a database of size 𝑛, adding noise from Laplace(0, 1/𝑛𝜖), ensures (𝜖, 0)-DP (a.k.a. pure DP); adding noise from Gaussian(0, √︁2 ln(1.25/𝛿)/𝑛𝜖) ensures (𝜖, 𝛿)-DP. The accuracy for such queries can be controlled probabilistically by converting it into the (𝜖, 𝛿) parameters – Page 2 - We propose Turbo, the first general and effective caching layer for DP SQL databases that boosts the number of linear queries (such as sums, averages, counts) that can be answered accurately under a fixed, global DP guarantee).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Kostopoulou. The motivation for doing so is to allow the system to store previous queries and their DP results, allowing for direct retrieval of the result without consuming any privacy budget when the same query is seen again on the same database version (Section 3.3 – Caching – Kostopoulou) .
Regarding claim 16,
EIDE further teaches
determining that the additional aggregation query is identical to the aggregation query; comparing the second state data to the first state data and determining that they are identical, indicating that the state of data stored in the particular database table is unchanged between the execution of the aggregation query and the execution of the additional aggregation query; in response to determining that the additional aggregation query is identical to the aggregation query and that the second state data is identical to the first state data: reusing the first deterministic pseudorandom noise value as the second deterministic pseudorandom noise value; setting the second noisy output to be identical to the first noisy output(¶ 0013 -the module uses a set of fixed random number elements summed together for adding noise and for setting noisy thresholds. The fixed-random numbers are taken from a pseudo-random distribution in such a way that on one hand the same answer produces the same pseudo-random number element, but on the other hand different query conditions will produce a different pseudorandom number elements - ¶ 0072 - repeated executions of queries with the same semantics produce the same noise element, and execution of a semantically different query has a significant probability of producing a different noise element. Third, any answer produced by the operation must be based on the cell values of some fixed threshold number of users. Any statistical operation with these three properties may be used in an embodiment of answer perturbation in the cloak. As will be appreciated, answer perturbation methods that have some but not all three of these pr properties may still provide valuable anonymization benefits –¶ 0077- the same fixed threshold produces the same answer, and a different fixed threshold could very well produce a different answer. If the selected users in step 365 all have the same value, then the answer is shared by an adequate number of users. – ¶ 0038 - Anonymization in embodiments of the cloak uses a special kind of pseudo-random number generation called fixed-random. A fixed-random number is a pseudo-random number whose value may be controlled by the cloak. This control allows the cloak to ensure that the same query generates the same noise – ¶ 0050 -Noise elements are fixed in that the same noise value is produced for the same attack component. As a result, if the same query is repeated, the noise will be the same, and so the noise value cannot be averaged away, as would be the case if, for instance, the noise value was a pure pseudo-random value. Two attack components are considered the same if they have the same semantics. So for instance, the attack components [ salary= 100000] and [ salary=2 * 50000] are considered the same, and the corresponding noise elements would be derived from the same seed – ¶ 0096 -the cloak partitions time into periods of time called time epochs. Exemplary time epochs include an hour or a day. In an embodiment, when answering queries, the cloak ignores changes to the database with a timestamp later than the end of the last epoch. As a result, it may be rare that, in the context of any given repeated query, one and only one user's data changed between the two queries).
However, EIDE does not explicitly teach
maintaining a privacy budget associated with at least one of the aggregation query, the particular database table, or a user of the device; forgoing any reduction of the privacy budget that would otherwise occur for executing a new query; whereby the method allows for repeated execution of the same query on unchanged data without consuming additional privacy budget, thus preserving the privacy budget for future queries while maintaining consistent results for unchanged data.
Kostopoulou teaches
maintaining a privacy budget associated with at least one of the aggregation query, the particular database table, or a user of the device; forgoing any reduction of the privacy budget that would otherwise occur for executing a new query (Abstract -Turbo builds upon private multiplicative weights (PMW), a DP mechanism that is powerful in theory but ineffective in practice, and transforms it into a highly-effective caching mechanism, PMW-Bypass, that uses prior query results obtained through an external DP mechanism to train a PMW to answer arbitrary future linear queries accurately and “for free” from a privacy perspective – Page 3 -When a query arrives, PMW estimates an answer using the histogram and computes the error of this estimate against the real data in a DP way, using a DP mechanism called sparse vector (SV) [26] (described shortly). If the estimate’s error is low, it is returned to the analyst, consuming no privacy budget (i.e., the query is answered “for free”). If the estimate’s error is large, then PMW executes the DP query on the data with the Laplace/Gaussian mechanism, consuming privacy budget as needed – Page 4 - Given a query, PMW-Bypass uses an effective heuristic to judge whether the histogram is sufficiently trained to answer the query accurately; if so, it uses it, thereby spending no budget);
whereby the method allows for repeated execution of the same query on unchanged data without consuming additional privacy budget, thus preserving the privacy budget for future queries while maintaining consistent results for unchanged data (Page 4 - Caching objects. Turbo maintains several types of caching objects. First, the Exact-Cache stores previous queries and their DP results, allowing for direct retrieval of the result without consuming any privacy budget when the same query is seen again on the same database version. Second, the PMW Bypass is an improved version of PMW that reduces privacy budget consumption during the training phase of its histogram – Section 3.2 Use Cases - Non-partitioned databases are the most common use case in DP. A group of untrusted analysts issue queries over time against a static database, and the database owner wishes to enforce a global DP guarantee).
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the teachings of EIDE to include the teachings of Kostopoulou. The motivation for doing so is to allow the system to store previous queries and their DP results, allowing for direct retrieval of the result without consuming any privacy budget when the same query is seen again on the same database version (Section 3.3 – Caching – Kostopoulou) .
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to YOUNES NAJI whose telephone number is (571)272-2659. The examiner can normally be reached on Monday - Friday 8:30 AM -5:30 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Oscar A Louie can be reached on (571) 270-1684. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/YOUNES NAJI/Primary Examiner, Art Unit 2445
Prosecution Insights