# US 2019/0318121 A1 · Budget Tracking in a Differentially Private Database System

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0318121 A1
- Document ID: US20190318121A1
- Status: Published application
- Kind: A1
- Application number: 15/953,409
- Filed: 2018-04-14
- Published: 2019-10-17
- Earliest claimed: 2018-04-14
- Assignees: LeapYear Technologies, Inc.
- Applicants: LeapYear Technologies, Inc.
- Inventors: Christopher Hockenbrocht; Ishaan Nerurkar; Liam Damewood; Mihai Maruseac; Alexander Rozenshteyn
- Web page: https://patentgrep.com/patent/US20190318121A1

## CPC

- G06F 16/2456: {Join operations}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques are described for budget tracking in a differentially private security system. A request to perform a query of a private database system is received by a privacy device from a client device. The request is associated with a level of differential privacy. A privacy budget corresponding to the received request is accessed by the privacy device. The privacy budget includes a cumulative privacy spend and a maximum privacy spend, the cumulative privacy spend representative of previous queries of the private database system. A privacy spend associated with the received request is determined by the privacy device based at least in part on the level of differential privacy associated with the received request. If a sum of the determined privacy spend and the cumulative privacy spend is less than the maximum privacy spend, the query is performed. Otherwise a security action is performed based on a security policy.

## Claims

### Claim 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, the request associated with a level of differential privacy;
access a privacy budget corresponding to the received request, the privacy budget including a cumulative privacy spend and a maximum privacy spend, the cumulative privacy spend representative of previous queries of the private database system;
determine a privacy spend associated with the received request based at least in part on the level of differential privacy associated with the received request;
in response to the sum of the cumulative privacy spend and the determined privacy spend being less than the maximum privacy spend:
provide a set of results to the client device in response to the performed query; and
update the cumulative privacy spend by incrementing the cumulative privacy spend by an amount equal to the determined privacy spend; and
in response to the sum of the cumulative privacy spend and the determined privacy spend being equal to or greater than the maximum privacy spend:
access a security policy associated with the privacy budget; and
perform a security action based on the accessed security policy and the received request.

### Claim 2 (depends on 1)

The hardware database privacy device of claim 1, wherein the accessed privacy budget comprises a privacy budget for a user or a set of users corresponding to the received request.

### Claim 3 (depends on 1)

The hardware database privacy device of claim 1, wherein the accessed privacy budget comprises a privacy budget for a dataset being queried.

### Claim 4 (depends on 1)

The hardware database privacy device of claim 1, wherein the level of differential privacy comprises privacy parameters ε and δ, and wherein the determined privacy spend is computed based on one or more of: a dataset being queried, a query type, the privacy parameter ε, the privacy parameter δ, and a sensitivity factor associated with the query.

### Claim 5 (depends on 4)

The hardware database privacy device of claim 4, wherein the determined privacy spend comprises the product of the sensitivity factor and ε.

### Claim 6 (depends on 4)

The hardware database privacy device of claim 4, wherein the determined privacy spend comprises ε.

### Claim 7 (depends on 4)

The hardware database privacy device of claim 4, wherein the query comprises one of a ‘select’ relational operator and a ‘where’ relational operator, and wherein the determined privacy spend comprises ε.

### Claim 8 (depends on 7)

The hardware database privacy device of claim 7, wherein the relational operator modifies a bound of the dataset, and wherein ε is modified in response to modifying the bound of the dataset.

### Claim 9 (depends on 4)

The hardware database privacy device of claim 4, wherein the query comprises a ‘join’ relational operator for a plurality of datasets, and wherein the sensitivity factor is based on a number of times a most frequently-occurring entry occurs within a dataset of the plurality of datasets.

### Claim 10 (depends on 9)

The hardware database privacy device of claim 9, wherein the plurality of datasets comprises a first dataset and a second dataset, wherein the first dataset is associated with a first sensitivity factor, wherein the second dataset is associated with a second sensitivity factor, and wherein determining a privacy spend associated with the received request comprises determining a first privacy spend associated with the first dataset and determining a second privacy spend associated with the second dataset.

### Claim 11 (depends on 4)

The hardware database privacy device of claim 4, wherein the query comprises a ‘union’ relational operator for a first dataset and a second dataset, and wherein the sensitivity factor is based on an amount of overlap between the first dataset and the second dataset.

### Claim 12 (depends on 11)

The hardware database privacy device of claim 11, wherein the sensitivity factor is 1 if the first dataset and the second dataset have no overlap.

### Claim 13 (depends on 11)

The hardware database privacy device of claim 11, wherein the sensitivity factor is 2 if the first dataset and the second dataset are identical.

### Claim 14 (depends on 11)

The hardware database privacy device of claim 11, wherein c is modified based on a union of a bounds of the first dataset and a bounds of the second dataset.

### Claim 15 (depends on 1)

The hardware database privacy device of claim 1, wherein updating the cumulative privacy spend comprises updating a cumulative privacy spend for each dataset associated with the query.

### Claim 16 (depends on 1)

The hardware database privacy device of claim 1, wherein the query is associated with a plurality of datasets, and wherein each dataset is associated with a corresponding maximum privacy spend such that at least one dataset is associated with a different corresponding maximum privacy spend than another dataset.

### Claim 17 (depends on 1)

The hardware database privacy device of claim 1, wherein performing the security action comprises rejecting the query.

### Claim 18 (depends on 1)

The hardware database privacy device of claim 1, wherein performing the security action comprises providing the set of results to the client device and notifying a database manager that the query exceeded the maximum privacy spend.

### Claim 19

A non-transitory computer-readable storage medium storing executable instructions that, when executed by a processor, cause the processor to perform steps comprises:
receiving a request from a client device to perform a query of a private database system, the request associated with a level of differential privacy;
accessing a privacy budget corresponding to the received request, the privacy budget including a cumulative privacy spend and a maximum privacy spend, the cumulative privacy spend representative of previous queries of the private database system;
determining a privacy spend associated with the received request based at least in part on the level of differential privacy associated with the received request;
in response to the sum of the cumulative privacy spend and the determined privacy spend being less than the maximum privacy spend:
providing a set of results to the client device in response to the performed query; and
updating the cumulative privacy spend by incrementing the cumulative privacy spend by an amount equal to the determined privacy spend; and
in response to the sum of the cumulative privacy spend and the determined privacy spend being equal to or greater than the maximum privacy spend:
accessing a security policy associated with the privacy budget; and
performing a security action based on the accessed security policy and the received request.

### Claim 20

A method comprising:
receiving, by a privacy device, a request from a client device to perform a query of a private database system, the request associated with a level of differential privacy;
accessing, by the privacy device, a privacy budget corresponding to the received request, the privacy budget including a cumulative privacy spend and a maximum privacy spend, the cumulative privacy spend representative of previous queries of the private database system;
determining, by the privacy device, a privacy spend associated with the received request based at least in part on the level of differential privacy associated with the received request;
in response to the sum of the cumulative privacy spend and the determined privacy spend being less than the maximum privacy spend:
providing, by the privacy device, a set of results to the client device in response to the performed query; and
updating, by the privacy device, the cumulative privacy spend by incrementing the cumulative privacy spend by an amount equal to the determined privacy spend; and
in response to the sum of the cumulative privacy spend and the determined privacy spend being equal to or greater than the maximum privacy spend:
accessing, by the privacy device, a security policy associated with the privacy budget; and
performing, by the privacy device, a security action based on the accessed security policy and the received request.