Differentially Private Processing and Database Storage

• US 20180048653A1
• Filed: 10/25/2017
• Published: 02/15/2018
• Est. Priority Date: 11/02/2015
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: LeapYear Technologies, Inc. (Snowflake Inc)
• Inventors: Nerurkar, Ishaan, Hockenbrocht, Christopher, Shaughnessy, Michael, Chatav, Eitan
• Granted Patent: US 10,242,224 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: H04L 63/105 Multiple levels of security

Abstract

A hardware database privacy device is communicatively coupled to a private database system. The hardware database privacy device receives a request from a client device to perform a query of the private database system and identifies a level of differential privacy corresponding to the request. The identified level of differential privacy includes privacy parameters (∈,δ) indicating the degree of information released about the private database system. The hardware database privacy device identifies a set of operations to be performed on the set of data that corresponds to the requested query. After the set of data is accessed, the set of operations is modified based on the identified level of differential privacy such that a performance of the modified set of operations produces a result set that is (∈,δ)-differentially private.

Claims

1. A hardware database privacy device, the hardware database privacy device communicatively coupled to a private database system, and configured to:

receive a request from a client device to perform a query of the private database system and identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ∈ and

δ

;

identify a set of data stored in the private database system and a set of operations to be performed on the set of data corresponding to the requested query, wherein the set of operations comprises

     1) identifying a loss function for the set of data, the loss function comprising a function of a set of parameters θ

describing correlations in the set of data, and

     2) minimizing a perturbed loss function over the set of parameters θ

;

access the set of data from the private database system;

modify the set of operations based on the identified level of differential privacy such that a performance of the modified set of operations produces a result set that is (∈

,δ

)-differentially private, wherein modifying the set of operations comprises perturbing the loss function by a factor defined by;

2. The device of claim 1, wherein the set of operations further comprises a count operation on one or more subsets of the set of data, and wherein modifying the set of operations further comprises perturbing results of the count operation on the one or more subsets by a factor defined by a Laplacian random variable with parameter c₁·

∈

;

3. The device of claim 1, wherein the set of operations further comprises a median operation on elements associated with one or more subsets of the set of data, and wherein modifying the set of operations further comprises perturbing results of the median operation on the elements by a factor defined by:

4. The device of claim 3, wherein the set of operations further comprises a mean operation on the one or more subsets of the set of data, and wherein the elements associated with the one or more subsets of the set of data are results of the mean operation on the one or more subsets of the set of data.

5. The device of claim 3, wherein the set of operations further comprises a variance operation on the one or more subsets of the set of data, and wherein the elements associated with the one or more subsets of the set of data are results of the variance operation on the one or more subsets of the set of data.

6. The device of claim 1, wherein the set of operations further comprises an interquartile range operation on the set of data, and wherein modifying the set of operations further comprises perturbing a result of the interquartile range operation by a factor defined by:

7. The device of claim 1, wherein each entry in the set of data is labeled with a category chosen from a set of two or more categories, wherein the set of operations further comprises training a random forest classifier, the random forest classifier comprising a plurality of binary decision trees, a binary decision tree having one or more leaf nodes each associated with a corresponding subset of entries in the set of data, and modifying the set of operations further comprises for each leaf node in the plurality of binary decision trees, perturbing relative proportions of entries labeled with each category by:

8. The device of claim 1, wherein each entry in the set of data is labeled with a category chosen from a set of two or more categories, and wherein:

the set of operations further comprises;

receiving a trained classifier and generating an output vector by applying the classifier to the entries of the set of data, each element of the output vector corresponding to a numerical output of the classifier for a corresponding entry in the set of data;

identifying a threshold value and assigning categories for each of the elements of the output vector based on a perturbed threshold value; and

recording counts related to a performance of the classifier, the counts generated by comparing the assigned categories of the elements of the output vector to the corresponding label in the set of data, and

modifying the set of operations further comprises;

perturbing the threshold value based on the privacy parameter c to generate the perturbed threshold value; and

perturbing the counts relating to the performance of the classifier based on the privacy parameter c to produce the perturbed counts as the differentially private result set.

9. A method for implementing differential privacy in a private database system, comprising:

receiving, by a hardware database privacy device communicatively coupled to the privacy database system, a request from a client device to perform a query of the private database system and identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ∈ and

δ

;

identifying, by the hardware database privacy device, a set of data stored in the private database system and a set of operations to be performed on the set of data corresponding to the requested query, wherein the set of operations comprises

     1) identifying a loss function for the set of data, the loss function comprising a function of a set of parameters θ

describing correlations in the set of data, and

     2) minimizing a perturbed loss function over the set of parameters θ

;

accessing, by the hardware database privacy device, the set of data from the private database system;

modifying, by the hardware database privacy device, the set of operations based on the identified level of differential privacy such that a performance of the modified set of operations produces a result set that is (∈

,δ

)-differentially private, wherein modifying the set of operations comprises perturbing the loss function by a factor defined by;

10. The method of claim 9, wherein the set of operations further comprises a count operation on one or more subsets of the set of data, and wherein modifying the set of operations further comprises perturbing results of the count operation on the one or more subsets by a factor defined by a Laplacian random variable with parameter c₁·

∈

;

11. The method of claim 9, wherein the set of operations further comprises a median operation on elements associated with one or more subsets of the set of data, and wherein modifying the set of operations further comprises perturbing results of the median operation on the elements by a factor defined by:

12. The method of claim 11, wherein the set of operations further comprises a mean operation on the one or more subsets of the set of data, and wherein the elements associated with the one or more subsets of the set of data are results of the mean operation on the one or more subsets of the set of data.

13. The method of claim 11, wherein the set of operations further comprises a variance operation on the one or more subsets of the set of data, and wherein the elements associated with the one or more subsets of the set of data are results of the variance operation on the one or more subsets of the set of data.

14. The method of claim 9, wherein the set of operations further comprises an interquartile range operation on the set of data, and wherein modifying the set of operations further comprises perturbing a result of the interquartile range operation by a factor defined by:

15. The method of claim 9, wherein each entry in the set of data is labeled with a category chosen from a set of two or more categories, wherein the set of operations further comprises training a random forest classifier, the random forest classifier comprising a plurality of binary decision trees, a binary decision tree having one or more leaf nodes each associated with a corresponding subset of entries in the set of data, and modifying the set of operations further comprises for each leaf node in the plurality of binary decision trees, perturbing relative proportions of entries labeled with each category by:

16. The method of claim 9, wherein each entry in the set of data is labeled with a category chosen from a set of two or more categories, and wherein:

the set of operations further comprises;

receiving a trained classifier and generating an output vector by applying the classifier to the entries of the set of data, each element of the output vector corresponding to a numerical output of the classifier for a corresponding entry in the set of data;

identifying a threshold value and assigning categories for each of the elements of the output vector based on a perturbed threshold value; and

recording counts related to a performance of the classifier, the counts generated by comparing the assigned categories of the elements of the output vector to the corresponding label in the set of data, and

modifying the set of operations further comprises;

perturbing the threshold value based on the privacy parameter c to generate the perturbed threshold value; and

perturbing the counts relating to the performance of the classifier based on the privacy parameter c to produce the perturbed counts as the differentially private result set.