Differentially private budget tracking using Renyi divergence

• US 10,642,847 B1
• Filed: 05/09/2019
• Issued: 05/05/2020
• Est. Priority Date: 05/09/2019
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: LeapYear Technologies, Inc. (Snowflake Inc)
• Inventors: Nerurkar, Ishaan, Hockenbrocht, Christopher, Rozenshteyn, Alexander, Damewood, Liam, Maruseac, Mihai
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US16/408,390
• Time in Patent Office: 362 Days
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

A differentially private security system communicatively coupled to a database storing restricted data receives a database query from a client. The database query includes a relation indicative of data to perform the query upon and at least one privacy parameter indicative of a level of differential privacy with which to perform the query. The differentially private security system determines a noise type for the query. The differentially private security system determines a representation of probabilistic privacy loss for the query based on the determined noise type. The differentially private security system determines a privacy spend for the query using the generated representation of probabilistic privacy loss. The differentially private security system determines whether the determined privacy spend exceeds a privacy budget associated with the client.

Claims

1. A method for bounding a privacy spend for a query to a database storing restricted data, the query received by a differentially private system, the method comprising:

receiving a database query from the client, the database query comprising a relation indicative of data to perform the query upon and at least one privacy parameter indicative of a level of differential privacy with which to perform the query;

determining a noise type for the query based on a preset configuration of the differentially private system;

generating a representation of probabilistic privacy loss for the query based on the determined noise type;

determining a privacy spend for the query using the generated representation of probabilistic privacy loss;

determining whether the determined privacy spend exceeds a privacy budget associated with the client; and

responsive to determining the determined privacy spend exceeds the privacy budget associated with the client, blocking the query.

2. The method of claim 1, wherein determining a privacy spend for the query using the generated representation of probabilistic privacy loss comprises:

determining a set of upper bounds in terms of the at least one privacy parameter for the query based on the generated representation of probabilistic privacy loss;

recording the determined set of upper bounds at a log including sets of upper bounds associated with historic queries;

evaluating the recorded sets of upper bounds in the log.

3. The method of claim 1, wherein generating the representation of probabilistic privacy loss for the query based on the determined noise type comprises generating a Renyi differential privacy curve, wherein determining the privacy spend for the query comprises:

evaluating the Renyi differential privacy curve at a plurality of alphas to produce a set of tau values;

for each alpha of the plurality of alphas, combining the corresponding tau value from the set of tau values with one or more historic tau values also associated with the alpha; and

determining the privacy spend for the query based on the combinations.

4. The method of claim 1, further comprising:

determining a sensitivity of the query based on the relation; and

adjusting the generated representation of probabilistic privacy loss based on the determined sensitivity.

5. The method of claim 1, wherein the at least one privacy parameter comprises at least one of an epsilon value indicative of a degree of information released about the database due to performance of the database query and a delta value indicative of an improbability of the database query satisfying epsilon-differential privacy.

6. The method of claim 5, wherein determining whether the determined privacy spend exceeds the privacy budget associated with the client further comprises comparing a maximum epsilon the determined privacy spend.

7. The method of claim 1, further comprising:

receiving a second database query;

determining a second noise type for the second database query based on a preset configuration of the differentially private system;

generating a second representation of probabilistic privacy loss for the second database query based on the second determined noise type;

determining a second privacy spend for the second database query using the second generated representation of probabilistic privacy loss;

determining the second privacy spend does not exceed the privacy budget;

responsive to determining the second privacy spend does not exceed the privacy budget, performing the second database query upon the database using the second determined privacy spend to produce query results; and

reporting the produced query results to the client.

19. The method of claim 1, wherein the preset configuration is set by an administrator of the differentially private system.

20. The method of claim 1, wherein the preset configuration of the differentially private system includes a correspondence between query attributes and noise types such that a particular noise type corresponding to a particular query attribute is used when generating the representation of probabilistic privacy loss for a query including the particular query attribute.

8. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations for bounding a privacy spend for a query to a database storing restricted data, the query received by a differentially private system, the operations comprising:

receiving a database query from the client, the database query comprising a relation indicative of data to perform the query upon and at least one privacy parameter indicative of a level of differential privacy with which to perform the query;

determining a noise type for the query based on a preset configuration of the differentially private system;

generating a representation of probabilistic privacy loss for the query based on the determined noise type;

determining a privacy spend for the query using the generated representation of probabilistic privacy loss;

determining whether the determined privacy spend exceeds a privacy budget associated with the client; and

responsive to determining the determined privacy spend exceeds the privacy budget associated with the client, blocking the query.

9. The non-transitory computer-readable storage medium of claim 8, wherein determining a privacy spend for the query using the generated representation of probabilistic privacy loss comprises:

determining a set of upper bounds in terms of the at least one privacy parameter for the query based on the generated representation of probabilistic privacy loss;

recording the determined set of upper bounds at a log including sets of upper bounds associated with historic queries;

evaluating the recorded sets of upper bounds in the log.

10. The non-transitory computer-readable storage medium of claim 8, wherein generating the representation of probabilistic privacy loss for the query based on the determined noise type comprises generating a Renyi differential privacy curve, wherein determining the privacy spend for the query comprises:

evaluating the Renyi differential privacy curve at a plurality of alphas to produce a set of tau values;

for each alpha of the plurality of alphas, combining the corresponding tau value from the set of tau values with one or more historic tau values also associated with the alpha; and

determining the privacy spend for the query based on the combinations.

11. The non-transitory computer-readable storage medium of claim 8, the operations further comprising:

determining a sensitivity of the query based on the relation; and

adjusting the generated representation of probabilistic privacy loss based on the determined sensitivity.

12. The non-transitory computer-readable storage medium of claim 8, wherein the at least one privacy parameter comprises at least one of an epsilon value indicative of a degree of information released about the database due to performance of the database query and a delta value indicative of an improbability of the database query satisfying epsilon-differential privacy.

13. The non-transitory computer-readable storage medium of claim 12, wherein determining whether the determined privacy spend exceeds the privacy budget associated with the client further comprises comparing a maximum epsilon the determined privacy spend.

14. The non-transitory computer-readable storage medium of claim 8, the operations further comprising:

receiving a second database query;

determining a second noise type for the second database query based on a preset configuration of the differentially private system;

generating a second representation of probabilistic privacy loss for the second database query based on the second determined noise type;

determining a second privacy spend for the second database query using the second generated representation of probabilistic privacy loss;

determining the second privacy spend does not exceed the privacy budget;

responsive to determining the second privacy spend does not exceed the privacy budget, performing the second database query upon the database using the second determined privacy spend to produce query results; and

reporting the produced query results to the client.

15. A system, comprising:

a processor; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations for bounding privacy spend for a query to a database storing restricted data, the query received by a differentially private system, the operations comprising;

receiving a database query from the client, the database query comprising a relation indicative of data to perform the query upon and at least one privacy parameter indicative of a level of differential privacy with which to perform the query;

determining a noise type for the query based on a preset configuration of the differentially private system;

generating a representation of probabilistic privacy loss for the query based on the determined noise type;

determining a privacy spend for the query using the generated representation of probabilistic privacy loss;

determining whether the determined privacy spend exceeds a privacy budget associated with the client; and

responsive to determining the determined privacy spend exceeds the privacy budget associated with the client, blocking the query.

16. The system of claim 15, wherein determining a privacy spend for the query using the generated representation of probabilistic privacy loss comprises:

determining a set of upper bounds in terms of the at least one privacy parameter for the query based on the generated representation of probabilistic privacy loss;

recording the determined set of upper bounds at a log including sets of upper bounds associated with historic queries;

evaluating the recorded sets of upper bounds in the log.

17. The system of claim 15, wherein generating the representation of probabilistic privacy loss for the query based on the determined noise type comprises generating a Renyi differential privacy curve, wherein determining the privacy spend for the query comprises:

evaluating the Renyi differential privacy curve at a plurality of alphas to produce a set of tau values;

for each alpha of the plurality of alphas, combining the corresponding tau value from the set of tau values with one or more historic tau values also associated with the alpha; and

determining the privacy spend for the query based on the combinations.

18. The system of claim 15, the operations further comprising:

determining a sensitivity of the query based on the relation; and

adjusting the generated representation of probabilistic privacy loss based on the determined sensitivity.