Differentially private database queries involving rank statistics
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.
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:
α
∑
b
≥
B
n
b
d
(
b
,
B
)
+
(
1
-
α
)
∑
b
≤
B
n
b
d
(
b
,
B
)
wherein B is a bin number of the bin for which the weight is being determined, b is a bin number other than B, n b is a number of values of the set of values placed in b and d(b,B) is a difference between the bin number of b and the bin number of B.
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:
N
b
-
1
N
b
*
I
x
*
max
(
α
,
1
-
α
)
wherein N b is a number of bins in the plurality of bins, |I x | is a width of an interval bounding the set of values, and max(α, 1−α) is a maximum of a and 1−α; and
applying an exponential mechanism to the selection scores assigned to the bins of the plurality of bins; and
selecting the bin responsive to the application of the exponential mechanism to the selection scores.
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:
α
∑
b
≥
B
n
b
d
(
b
,
B
)
+
(
1
-
α
)
∑
b
≤
B
n
b
d
(
b
,
B
)
wherein B is a bin number of the bin for which the weight is being determined, b is a bin number other than B, n b is a number of values of the set of values placed in b and d(b,B) is a difference between the bin number of b and the bin number of B.
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:
N
b
-
1
N
b
*
I
x
*
max
(
α
,
1
-
α
)
wherein N b is a number of bins in the plurality of bins, |I x | is a width of an interval bounding the set of values, and max(α, 1−α) is a maximum of a and 1−α; and
applying an exponential mechanism to the selection scores assigned to the bins of the plurality of bins; and
selecting the bin responsive to the application of the exponential mechanism to the selection scores.
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.