Differentially private database queries involving rank statistics

• US 10,467,234 B2
• Filed: 07/19/2018
• Issued: 11/05/2019
• 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, Damewood, Liam, Maruseac, Mihai, Rozenshteyn, Alexander
• Primary Examiner(s): Leung, Robert B
• Application Number:
  US16/040,478
• Publication Number:
  US 20180349384A1
• Time in Patent Office: 474 Days
• CPC Class Codes: G06F 16/24578 using ranking
• 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 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• 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

Abstract

A differentially private security system is communicatively coupled to a database. The differentially private security system receives a request from a client device to perform a query of the database 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 database. The differentially private security system performs a differentially private query upon a set of data in the database such that the performance of the query produces a result that is (ε,δ)-differentially private.

Claims

1. A method for returning differentially private results in response to a query to a database storing restricted data, comprising:

receiving a database query from a client device, the database query requesting a value satisfying a rank statistic based on a set of values of a column of a set of records storing restricted data in the database;

performing the query on the set of records in the database to produce a differentially private version of the value satisfying the rank statistic, performing the query comprising;

computing a histogram placing the values in the set of values into a plurality of bins, each bin containing any values in the set of values within a respective interval;

assigning weights to the plurality of bins;

selecting a bin of the plurality of bins responsive to the assigned weights; and

computing a differentially private version of the value satisfying the rank statistic responsive to values within the respective interval for the selected bin; and

returning the computed differentially private version of the value satisfying the rank statistic to the client device.

2. The method of claim 1, wherein the weight assigned to a given bin is based on a distance between the given bin and a true bin including the value satisfying the rank statistic.

3. The method of claim 1, wherein the rank statistic is specified by a quantile α

of a plurality of quantiles, each bin of the plurality of bins has a respective bin number, and assigning weights to the plurality of bins comprises;

determining a weight for each respective bin of the plurality of bins as;

4. The method of claim 3, wherein the database query specifies a privacy parameter ε

describing a degree of information released about the set of values stored in the database due to the query, and selecting the bin responsive to the assigned weights comprises;

assigning selection scores to the plurality of bins, the selection score assigned to the given bin determined responsive to the privacy parameter ε

, the weight assigned to the given bin, and a sensitivity function;

5. The method of claim 1, wherein the rank statistic is specified by a quantile α

of a plurality of quantiles and computing the differentially private version of the value satisfying the rank statistic comprises;

computing the differentially private version of the value satisfying the rank statistic as;

B_inf+α

|B|

wherein B_inf is a lower bound of the selected bin and |B| is a width of the selected bin.

6. The method of claim 1, wherein the received query further identifies a level of accuracy, and further comprising:

computing a number of bins in the plurality of bins responsive to the identified level of accuracy.

7. The method of claim 1, wherein the database query specifies the rank statistic as a quantile α

of a plurality of quantiles and specifies a privacy parameter describing a degree of information released about the set of values stored in the database due to the query, and wherein computing the histogram comprises;

computing bounding intervals for the bins of the plurality of bins such that each bin is bounded by two adjacent values of the set of values and includes one of the two adjacent values.

8. The method of claim 7, wherein each bin of the plurality of bins has a respective bin number i and:

assigning weights to the plurality of bins comprises;

determining a weight for each respective bin of the plurality of bins as;

|I|exp(−

ε

|i−

α

n|)

wherein |I| is a width of the respective bin, i is the bin number of the bin, and n is a number of values in the set of values; and

selecting the bin of the plurality of bins responsive to the assigned weights comprises;

applying an exponential mechanism to the weights assigned to the bins of the plurality of bins; and

selecting the bin responsive to the application of the exponential mechanism to the weights.

9. The method of claim 8, wherein computing a differentially private version of the value satisfying the rank statistic comprises:

selecting a value within the bounding interval of the selected bin.

10. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations for returning differentially private results in response to a query to a database storing restricted data, the operations comprising:

receiving a database query from a client device, the database query requesting a value satisfying a rank statistic based on a set of values of a column of a set of records storing restricted data in the database;

performing the query on the set of records in the database to produce a differentially private version of the value satisfying the rank statistic, performing the query comprising;

computing a histogram placing the values in the set of values into a plurality of bins, each bin containing any values in the set of values within a respective interval;

assigning weights to the plurality of bins;

selecting a bin of the plurality of bins responsive to the assigned weights; and

computing a differentially private version of the value satisfying the rank statistic responsive to values within the respective interval for the selected bin; and

returning the computed differentially private version of the value satisfying the rank statistic to the client device.

11. The non-transitory computer-readable storage medium of claim 10, wherein the weight assigned to a given bin is based on a distance between the given bin and a true bin including the value satisfying the rank statistic.

12. The non-transitory computer-readable storage medium of claim 10, wherein the rank statistic is specified by a quantile α

of a plurality of quantiles, each bin of the plurality of bins has a respective bin number, and assigning weights to the plurality of bins comprises;

determining a weight for each respective bin of the plurality of bins as;

13. The non-transitory computer-readable storage medium of claim 12, wherein the database query specifies a privacy parameter ε

describing a degree of information released about the set of values stored in the database due to the query, and selecting the bin responsive to the assigned weights comprises;

assigning selection scores to the plurality of bins, the selection score assigned to the given bin determined responsive to the privacy parameter ε

, the weight assigned to the given bin, and a sensitivity function;

14. The non-transitory computer-readable storage medium of claim 10, wherein the rank statistic is specified by a quantile α

of a plurality of quantiles and computing the differentially private version of the value satisfying the rank statistic comprises;

computing the differentially private version of the value satisfying the rank statistic as;

B_inf+α

|B|

wherein B_inf is a lower bound of the selected bin and |B| is a width of the selected bin.

15. The non-transitory computer-readable storage medium of claim 10, wherein the received query further identifies a level of accuracy, and the operations further comprise:

computing a number of bins in the plurality of bins responsive to the identified level of accuracy.

16. The non-transitory computer-readable storage medium of claim 10, wherein the database query specifies the rank statistic as a quantile α

of a plurality of quantiles and specifies a privacy parameter ε

describing a degree of information released about the set of values stored in the database due to the query, and wherein computing the histogram comprises;

computing bounding intervals for the bins of the plurality of bins such that each bin is bounded by two adjacent values of the set of values and includes one of the two adjacent values.

17. The non-transitory computer-readable storage medium of claim 16, wherein each bin of the plurality of bins has a respective bin number i and:

assigning weights to the plurality of bins comprises;

determining a weight for each respective bin of the plurality of bins as;

|I|exp(−

ε

|i−

α

n|)

wherein |I| is a width of the respective bin, i is the bin number of the bin, and n is a number of values in the set of values; and

selecting the bin of the plurality of bins responsive to the assigned weights comprises;

applying an exponential mechanism to the weights assigned to the bins of the plurality of bins; and

selecting the bin responsive to the application of the exponential mechanism to the weights.

18. The non-transitory computer-readable storage medium of claim 17, wherein computing a differentially private version of the value satisfying the rank statistic comprises:

selecting a value within the bounding interval of the selected bin.

19. A method for returning differentially private results in response to a query to a database storing restricted data, comprising:

receiving a database query from a client device, the database query requesting a differentially private subset of records from a set of records in the database, the records in the set having a column with values defining a bounded interval, the requested subset of records having values of the column within a specified range of the bounded interval;

performing the query on the set of records in the database to produce a differentially private result set of records based on the requested subset, performing the query comprising;

using a differentially-private rank statistic technique to determine an initial differentially private median value within the bounded interval for the column;

subdividing the bounded interval into sub-intervals bounded by the initial median value;

recursively generating additional differentially private median values based on the sub-intervals; and

identifying a differentially private subset of records responsive to the additional median values; and

returning the identified differentially private subset of the records to the client device.