Differentially private processing and database storage
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.
1. A database system configured to implement differential privacy, comprising:
a processor configured to execute computer program instructions; and
a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform actions comprising:
receiving a database query requesting a differentially private response to the query;
determining a privacy parameter ε associated with the query, wherein ε describes a degree of information to release about a set of data stored by the database system that is responsive to the query;
identifying a privacy budget associated with the query, the privacy budget specified in terms of ε and representing a degree of information available to be released about data by the database system;
decrementing the privacy budget by a first ε spend determined responsive to the query; and
applying the query to the database system by performing a differentially private set of operations on the set of data stored by the database system that is responsive to the query to produce a differentially private result set that releases the degree of information about the set of data described by the privacy parameter ε, wherein the set of operations comprises a count operation on a subset of the set of data, and wherein the set of operations comprises perturbing results of the count operation on the subset by a factor defined by a Gaussian random variable G( ) to produce the differentially private result set.
2. The database system of claim 1 , 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 θ, and wherein the set of operations comprises perturbing the loss function by a factor defined by:
θ
T
v
(
G
(
4
·
K
2
·
R
2
2
·
(
log
1
δ
+
ϵ
)
ϵ
2
)
)
,
to produce the set of parameters θ that minimize the perturbed loss function private set, where K, R 2 are constants, wherein δ is another privacy parameter and ν( ) denotes a vector populated with random variables.
3. The database system of claim 1 , wherein the set of operations comprises a median operation on elements associated with a second subset of the set of data, and wherein the set of operations comprises perturbing results of the median operation on the elements by a factor defined by:
c
1
·
S
M
(
U
;
c
2
·
ϵ
2
)
·
C
(
1
)
ϵ
2
,
to produce the differentially private result set, where c 1 , c 2 are constants, C(1) is a Cauchy random variable, ϵ 2 is a second ϵ spend, and S M (U; c 2 ·ε) is a function that computes a smooth sensitivity of the elements with parameter c 2 ·ε 2 .
4. The database system of claim 1 , wherein the set of operations comprises an interquartile range operation on a second subset of the set of data, and wherein the set of operations comprises perturbing a result of the interquartile range operation by a factor defined by:
(
1
1
+
log
n
)
L
(
c
1
ϵ
2
)
,
to produce the differentially private result set, where L( ) denotes a Laplacian random variable, c 1 and n are constants, and ϵ 2 is a second ϵ spend.
5. The database system of claim 1 , wherein the set of operations comprises 1) identifying a loss function for a second subset of the set of data, the loss function a function of a set of parameters θ describing correlations in the second subset, and 2) for each time step, generating a perturbed estimate for the set of parameters θ that minimize the loss function, and wherein the set of operations comprises for each time step, perturbing an estimate for the set of parameters θ by:
η
t
·
v
(
G
(
c
1
2
·
n
2
·
(
log
n
δ
·
log
1
δ
)
ϵ
4
2
)
)
,
to produce the perturbed estimate for the set of parameters θ as the differentially private result set, where η t , n, and c 1 are constants, and ϵ 2 is a second ϵ spend, wherein ν( ) denotes a vector populated with random variables and δ is another privacy parameter.
6. The database system of claim 1 , wherein each entry in a second subset of the set of data is labeled with a category chosen from a set of two or more categories, and wherein the set of operations comprises:
receiving a trained classifier and generating an output vector by applying the classifier to entries of the second subset, each element of the output vector corresponding to a numerical output of the classifier for a corresponding entry in the second subset;
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 second subset, and
the set of operations comprises:
perturbing the threshold value based on a second ϵ spend ε 2 to generate the perturbed threshold value; and
perturbing the counts relating to the performance of the classifier based once to produce the perturbed counts as the differentially private result set.
7. The database system of claim 1 , wherein the differentially private set of operations is performed responsive to determining that the first ε spend can be accommodated by the privacy budget.
8. The database system of claim 1 , wherein the privacy budget is associated with a user of the database system.
9. A method for implementing differential privacy, comprising:
receiving a database query requesting a differentially private response to the query;
determining a privacy parameter ε associated with the query, wherein describes a degree of information to release about a set of data stored by a database system that is responsive to the query;
identifying a privacy budget associated with the query, the privacy budget specified in terms of ε and representing a degree of information available to be released about data by the database system;
decrementing the privacy budget by a first ε spend determined responsive to the query; and
applying the query to the database system by performing a differentially private set of operations on the set of data stored by the database system that is responsive to the query to produce a differentially private result set that releases the degree of information about the set of data described by the privacy parameter ε, wherein the set of operations comprises a count operation on a subset of the set of data, and wherein the set of operations comprises perturbing results of the count operation on the subset by a factor defined by a Gaussian random variable G( ) to produce the differentially private result set.
10. The method of claim 9 , 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 θ, and wherein the set of operations comprises perturbing the loss function by a factor defined by:
θ
T
v
(
G
(
4
·
K
2
·
R
2
2
·
(
log
1
δ
+
ϵ
)
ϵ
2
)
)
,
to produce the set of parameters θ that minimize the perturbed loss function as the differentially private set, where K, R 2 are constants, wherein δ is another privacy parameter and ν( ) denotes a vector populated with random variables.
11. The method of claim 9 , wherein the set of operations comprises a median operation on elements associated with a second subset the set of data, and wherein the set of operations comprises perturbing results of the median operation on the elements by a factor defined by:
c
1
·
S
M
(
U
;
c
2
·
ϵ
2
)
·
C
(
1
)
ϵ
2
,
to produce the differentially private result set, where c 1 , c 2 are constants, C(1) is a Cauchy random variable, ϵ 2 is a second ϵ spend, and S M (U; c 2 ·ε) is a function that computes a smooth sensitivity of the elements with parameter c 2 ·ε 2 .
12. The method of claim 9 , wherein the set of operations comprises an interquartile range operation on a second subset of the set of data, and wherein the set of operations comprises perturbing a result of the interquartile range operation by a factor defined by:
(
1
1
+
log
n
)
L
(
c
1
ϵ
2
)
,
to produce the differentially private result set, where L( ) denotes a Laplacian random variable, c 1 and n are constants and ϵ 2 is a second ϵ spend.
13. The method of claim 9 , wherein the differentially private set of operations is performed responsive to determining that the first ε spend can be accommodated by the privacy budget.
14. The method of claim 9 , wherein the privacy budget is associated with a user of the database system.
15. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform actions for implementing differential privacy comprising:
receiving a database query requesting a differentially private response to the query;
determining a privacy parameter ε associated with the query, wherein describes a degree of information to release about a set of data stored by a database system that is responsive to the query;
identifying a privacy budget associated with the query, the privacy budget specified in terms of ε and representing a degree of information available to be released about data by the database system;
decrementing the privacy budget by a first ε spend determined responsive to the query; and
applying the query to the database system by performing a differentially private set of operations on the set of data stored by the database system that is responsive to the query to produce a differentially private result set that releases the degree of information about the set of data described by the privacy parameter ε, wherein the set of operations comprises a count operation on a subset of the set of data, and wherein the set of operations comprises perturbing results of the count operation on the subset by a factor defined by a Gaussian random variable G( ) to produce the differentially private result set.
16. The non-transitory computer-readable storage medium of claim 15 , 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 θ, and wherein the set of operations comprises perturbing the loss function by a factor defined by:
θ
T
v
(
G
(
4
·
K
2
·
R
2
2
·
(
log
1
δ
+
ϵ
)
ϵ
2
)
)
,
to produce the set of parameters θ that minimize the perturbed loss function, where K, R 2 are constants, wherein δ is another privacy parameter and ν( ) denotes a vector populated with random variables.
17. The non-transitory computer-readable storage medium of claim 15 , wherein the set of operations comprises a median operation on elements associated with a second subset of the set of data, and wherein the set of operations comprises perturbing results of the median operation on the elements by a factor defined by:
c
1
·
S
M
(
U
;
c
2
·
ϵ
2
)
·
C
(
1
)
ϵ
2
,
to produce the differentially private result set, where c 1 , c 2 are constants, C(1) is a Cauchy random variable, ϵ 2 is a second ϵ spend, and S M (U; c 2 ·ε) is a function that computes a smooth sensitivity of the elements with parameter c 2 ·ε 2 .
18. The non-transitory computer-readable storage medium of claim 15 , wherein the set of operations comprises an interquartile range operation on a second subset of the set of data, and wherein the set of operations comprises perturbing a result of the interquartile range operation by a factor defined by:
(
1
1
+
log
n
)
L
(
c
1
ϵ
2
)
,
to produce the differentially private result set, where L( ) denotes a Laplacian random variable, c 1 and n are constants and ε 2 is a second ε spend.
19. The non-transitory computer-readable storage medium of claim 15 , wherein the differentially private set of operations is performed responsive to determining that the first ε spend can be accommodated by the privacy budget.
20. The non-transitory computer-readable storage medium of claim 15 , wherein the privacy budget is associated with a user of the database system.