KR102054450B1 - Differential privacy-based query processing system and privacy budget saving method using the same - Google Patents

Abstract

A method for saving a privacy budget by a query processing system, comprising: calculating a maximum update count for each of a plurality of received queries, and allocating a budget for each of the plurality of queries based on the calculated maximum update count and a preset total privacy budget. do. At least one query among the plurality of budget-allocated queries is included in one batch, the at least one query included in one batch is rearranged, and the rearranged at least one query is processed.

Description

Differential privacy-based query processing system and privacy budget saving method using the same}

The present invention relates to a differential privacy based query processing system and a privacy budget saving method using the same.

When publishing data in an interactive environment or providing query results for a query made by any user, a technique for protecting personal information is essential to prevent personal identification. To this end, structural protection techniques such as k-anonymization have been studied. However, with the advent of various attack techniques including differential attack, differential privacy that can protect the privacy above a certain level irrespective of the attacker's prior knowledge is being studied.

In order to satisfy the differential privacy for the query results, a certain level of noise must be inserted into the raw data and provided as a query result. At this time, in the process of deriving the noise value inserted into the raw data, the queryer spends a part of the privacy budget allocated to the query.

The more the budget is spent, the less noise is inserted, and the more accurate the query results. However, since the budget of the query is limited, the budget to be applied to each query should be appropriately divided and applied when processing a large number of queries. In addition, when the budget is too small, a large amount of noise is inserted, which greatly reduces the accuracy of query results.

Accordingly, the present invention provides a query processing system for processing linear queries by applying differential privacy in an interactive environment, and a method of saving a privacy budget using the same.

As a method of processing a differential privacy query, a query processing system which is one feature of the present invention for achieving the technical problem of the present invention,

Calculating a maximum number of updates for each of the plurality of received queries, allocating a budget for each of the plurality of queries based on the calculated maximum number of updates and a preset total privacy budget, a plurality of allocated budgets Including at least one of the queries in one batch, and relocating at least one query included in the one batch, and processing the relocated at least one query.

The calculating of the maximum update number may include generating a second histogram, which is a virtual histogram having a uniform distribution that is different from a first histogram, which is an original histogram, from a database in which the plurality of queries are stored. Calculating a first result value that is a query result value and a second result value that is a query result value derived from the first histogram, and checking whether a difference between the first result value and the second result value deviates from a preset threshold value And distributing a result of inserting noise into the second result value and updating the virtual histogram when the difference is out of the threshold value.

The calculating of the maximum number of updates may include an upper limit value of a relative entropy between the first histogram and the initialized second histogram, a histogram parameter, the number of the plurality of queries, and a Laplace distribution region that is out of the threshold. The maximum update count may be determined based on the calculated value.

Including in one batch may include including at least one query in the batch until a probability that a query enters according to a Poisson distribution is higher than a uniform distribution value that is a probability that the query randomly enters. have.

The step of including in the batch may include setting a maximum threshold value of the batch size based on the maximum number of updates, the number of queries, and the total privacy budget.

The processing of the one query may include: calculating a distance value if the difference between the first result value and the second result value is greater than the threshold value, and having the largest distance value based on the calculated distance value. And relocating in order of query, wherein the distance value is calculated as a difference between the original histogram and the virtual histogram for each of at least one query included in the batch.

As a query processing system for processing a differential privacy query that is another feature of the present invention for achieving the technical problem of the present invention,

A budget allocator configured to calculate a maximum update count for each of the plurality of received queries, and allocate a budget for each of the plurality of queries based on the calculated maximum update count and a preset total privacy budget; A batch size setting unit including at least one query among the queries in one batch, and a query processing unit processing at least one query included in the one batch.

The budget allocator is based on an upper limit value of a relative entropy between a first histogram and an initialized second histogram, a histogram parameter, the number of the plurality of queries, and a value of a Laplace distribution region that is out of the threshold value. The maximum update count may be calculated.

The batch size setting unit may include at least one query in the batch until a probability that the query enters according to the Poisson distribution becomes higher than a uniform distribution value that is a probability that the query randomly enters.

The batch size setting unit may set the size of the batch to a maximum threshold value based on the maximum number of updates, the number of queries, and the total privacy budget.

According to the present invention, a batch process may be performed in consideration of a limited privacy budget, so that a query may be processed at a smaller budget when processing the same number of queries.

1 is a structural diagram of a query processing system according to an embodiment of the present invention.
2 is a flowchart illustrating a privacy budget saving method according to an embodiment of the present invention.
3 is an exemplary view comparing actual update times and inferred update times according to an embodiment of the present invention.
4 is an exemplary view comparing update times according to a method and a general method according to an exemplary embodiment of the present invention.
5 is an exemplary diagram of a region outside the threshold in various histogram and Laplace distributions according to an embodiment of the present invention.

DETAILED DESCRIPTION Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art may easily implement the present invention. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present invention. In the drawings, parts irrelevant to the description are omitted in order to clearly describe the present invention, and like reference numerals designate like parts throughout the specification.

Hereinafter, a differential privacy based query processing system and a privacy budget saving method using the same according to an embodiment of the present invention will be described in detail with reference to the accompanying drawings.

1 is a structural diagram of a query processing system according to an embodiment of the present invention.

As shown in FIG. 1, the query processing system 100 is operated by at least one processor and includes a budget allocator 110, a batch size setting unit 120, and a query processing unit 130.

The budget allocator 110 receives a plurality of queries from a user terminal (not shown) or the outside. In this case, the plurality of queries received by the budget allocator 110 will be described using a linear query as an example.

The budget allocator 110 calculates a maximum update count based on the number of received queries and the total budget information previously allowed. The budget is divided by the calculated maximum update times to determine the budget to be allocated to one query.

That is, in the related art, as much as the budget divided by the total budget is allocated to one query. In this case, since the budget allocated to one query becomes very small as the number of queries increases, there is a disadvantage in that noise is excessively inserted to reduce the accuracy of the query.

Accordingly, the budget allocator 110 first calculates the maximum update number instead of dividing the entire budget by the number of queries. The budget is divided based on the calculated maximum update count.

The batch size setting unit 120 determines the batch size based on the budget allocated by the budget allocating unit 110. The larger the batch size, the more the budget consumption for the query can be optimized. However, if the batch size is too large, the response time of each query increases.

Therefore, the batch size setting unit 120 calculates a probability that the query enters according to the parameter of the query and the Poisson distribution. The batch size setting unit 120 sets the maximum threshold value of the batch size based on the calculated probability. The batch size setting unit 120 determines the batch size for the query using the set maximum threshold value of the batch size. This will be described later in detail.

The batch size setting unit 120 compares the query result from the virtual histogram with the noise inserted into the query result from the original histogram when there is a query. If the comparison value is larger than the preset threshold value, the relative entropy is determined to be large, and the query is rearranged based on a query criterion having a large distance value to update the virtual histogram. Based on this, a small number of updates makes the virtual histogram similar to the original histogram, saving privacy budget. This will be described later in detail.

When the budget allocator 110 divides the budget, and the batch size setting unit 120 sets the batch size for the query and rearranges the query, the query processor 130 queries the query based on the divided budget and the set batch size. Process the to generate the query response information. Since the query processing unit 130 processes the query in various ways, the embodiment of the present invention is not limited to any one method.

In addition, in the embodiment of the present invention, although not shown separately for convenience of description, a memory for storing and managing programs necessary for driving the query processing system 100 may be further included. Since the form of the program and the form of the question and answer information are various, the embodiment of the present invention is not limited to any one form.

A method of saving a privacy budget with the query processing system 100 described above will be described with reference to FIG. 2.

2 is a flowchart illustrating a privacy budget saving method according to an embodiment of the present invention.

As illustrated in FIG. 2, when receiving a plurality of queries from the outside (S100), the query processing system 100 checks the number of queries. In addition, the query processing system 100 calculates a maximum update count in the plurality of received queries (S101).

Here, since the query processing system 100 checks the number of queries in various ways, the embodiment of the present invention is not limited to any one method.

In addition, when the query processing system processes a linear query in an interactive environment, the query processing system 100 utilizes a virtual histogram to reduce the consumption of the budget. It utilizes virtual histograms and parameters to reduce budget consumption by providing query results through virtual histograms rather than original histograms under certain conditions.

Through this, the query processing system 100 generates a virtual histogram of a uniform distribution form separately from the original histogram derived from the actual database where the query is stored. After that, the noise result is compared to the query result derived from the virtual histogram and the value derived from the original histogram. If the difference is less than or equal to the threshold T, the results from the virtual histogram are distributed to avoid spending budget.

On the other hand, if the difference is greater than or equal to the threshold, the result of inserting noise into the value derived from the original histogram is distributed. The virtual histogram is then updated to make it similar to the original histogram. The budget is only spent distributing noise into the original histogram, and the above process is repeated for queries that continue to flow in the interactive environment.

This establishes the threshold value T and histogram update mechanism, demonstrating that the query processing method according to the embodiment of the present invention satisfies (ε, δ) -differential privacy. Since the differential privacy satisfaction proof method can be proved by various methods, detailed description is omitted in the embodiment of the present invention.

However, even if this method is executed for the same set of queries, the number of update of the virtual histogram varies differently according to the order of entry of the entering queries, which greatly increases the performance deviation of the technique. This will be described first with reference to FIG. 5.

5 is an exemplary diagram of a region outside the threshold in various histogram and Laplace distributions according to an embodiment of the present invention.

Assume that there is an original histogram for the query as shown in FIG. Then, as shown in (c-1) of FIG. 5, the virtual histogram normalized to the initial value is updated by a query that continuously enters. Suppose that the first query Q1 is a query for bin 2, and the second query Q2 and the third query Q3 are queries for bin 7, bin 10, respectively.

The three histograms of the three queries are updated as shown in (c-2), (c-3), and (c-4) of FIG. 5. However, if the seventh query Q7 is a query for bin 7 and bin 10, a virtual histogram similar to the result of three updates of Q1, Q2, and Q3 is generated with only one update through Q7 as shown in (b-2) of FIG. You can get it.

Using batch to rearrange queries in batch in an efficient order does not affect the proof of (ε, δ) -differential privacy. In addition, a certain level of performance can be maintained, and similar virtual histograms can be obtained with fewer updates than conventional methods, thereby reducing budget consumption.

Referring to FIG. 2, in order to calculate the maximum number of updates in a plurality of received queries, the query processing system 100 updates the upper limit of relative entropy between the initial virtual histogram and the original histogram and one histogram update for the query. Use the relative entropy number that decreases when this occurs.

That is, relative entropy reduction by η ² occurs when one histogram is updated for a query. Thus, the upper limit of the relative entropy between the initial virtual histogram y and the original histogram x becomes logH. Through this, the query processing system 100 may calculate that the maximum logH / η ² update is attempted until the initial virtual histogram is similar to the original histogram.

However, the maximum number of update attempts is the result of not considering the noise insertion calculated from the Laplace distribution. Accordingly, the query processing system 100 recognizes that an additional update occurs by comparing the result of inserting noise into the result of the query resulting from the virtual histogram and the value derived from the original histogram. Here, since the distribution of the noise follows the Laplace distribution, p can be obtained as shown in Equation 1 when p is a region deviating from the threshold.

만큼의 갱신이 발생한다. Therefore, if additional updates of N * p occur,

As many updates occur.

The query processing system 100 determines a budget to allocate to one query based on the maximum number of update occurrences obtained in Equation 1 (S102). That is, the privacy budget UE that can be allocated to one update process is shown in Equation 2 below. The query processing system 100 allocates each time the privacy budget is updated.

If the budget is determined through the step S102, the query processing system 100 sets the batch size (S103). As the batch size increases, the budget consumption of the query can be optimized. However, when the batch size becomes too large, the response time of each query increases. Therefore, batch size should be maintained at an appropriate level.

In order for the query processing system 100 to set a batch size, in the embodiment of the present invention, it is assumed that a query enters according to a Poisson distribution whose parameter is λ. When the previous batch processes the mth query by the distribution, the probability that the query enters from the next query to the nth query is expressed by Equation 3 below.

Where f (x) is the probability that the x-th event will occur when the parameter is λ.

According to the Poisson distribution of Equation 3, the query processing system 100 includes the queries in one batch until the probability that the query enters becomes higher than the uniform distribution value that is the probability that the query enters arbitrarily. At this time, in the case of the Poisson distribution, P (X ≦ N) = α, which is a probability that all the queries are entered according to the parameter, may be smaller than 1. Therefore, the Poisson distribution value is compared with the uniform distribution value, and the queries are included in the batch until the condition of Equation 4 is satisfied.

only. Due to the nature of the Poisson distribution, the larger the difference from the parameter, the smaller the probability value, so the size of the batch can be very large. Therefore, in order to maintain a certain level of query response time, the maximum threshold value of the batch size is set as in Equation 5 below.

When ε becomes large, the maximum update count decreases, and even when the number of queries increases, the maximum update count increases. Therefore, the maximum threshold provides a batch size that can maintain a certain level of query response time even with e or N changes. The algorithm considering the budget determined in step S102 and the batch size set in step S103 is shown in Table 1 below.

: 질의 집합, N: 질의 개수
H: 원본 히스토그램 bin 수, B: 배치 크기
E: 전체 프라이버시 예산, n: 데이터베이스 레코드 수

Predefine: η, σ, T

: 히스토그램 갱신 변수

: 라플라스 분포 분산

: 결과값 차이 임계값Require: x, ε, Q, H, E, N
x: text histogram, ε: privacy level required per quality
y: virtual histogram, T: result difference threshold

: Query set, N: number of queries
H: number of original histogram bins, B: batch size
E: total privacy budget, n: number of database records

Predefine: η, σ, T

: Histogram update variables

: Laplace Distribution Variance

: Result Difference Threshold

As shown in Table 1, the original histogram (x), the required privacy level per query (ε), the virtual histogram (y), the resulting difference threshold (T), in order to implement the algorithm considering budget allocation and placement, The query set (Q), the number of queries (N), the original histogram bin number, the batch size (B), the total privacy budget (E), and the number of database records (n) are input information. Predefine values also include a histogram update parameter η, a Laplace distribution variance σ, and a resultant difference threshold T.

Running the algorithm shown in Table 1, query processing system 100 rearranges at least one query contained in one batch. That is, the query processing system 100 makes the virtual histogram similar to the original histogram through the continuous updating of the virtual histogram. This is because when the difference between the virtual histogram and the original histogram is expressed in terms of relative entropy, the amount of change in relative entropy that can be changed for each query is different.

Therefore, the virtual histogram update is performed by rearranging the query based on the query that changes the relative entropy most significantly among the queries in one batch. Here, for query relocation, the query processing system 100 calculates a query distance value, where the distance value d _i is a _i- <q _i which is the difference between the original histogram and the virtual histogram for the i th query. , y> and a _i = <q _i , x> + A _i , where A _i is the result of noise insertion. Based on this, a small number of virtual histogram updates can make a virtual histogram similar to the original histogram, which saves privacy budget.

On the other hand, if the batch size is set in step S103 of FIG. 2, the query processing system 100 processes the query received in step S100 and provides the query to the user's terminal (not shown) (S104).

Next, an example in which the actual number of updates according to an embodiment of the present invention is compared with the inferred number of updates will be described with reference to FIG. 3, and the comparison between the number of updates according to the method and the general method according to the embodiment of the present invention is described below. This will be described with reference to FIG. 4.

3 is an exemplary view comparing actual update times and inferred update times according to an embodiment of the present invention. 4 is an exemplary view comparing update times according to a method and a general method according to an exemplary embodiment of the present invention.

The data used in the embodiment of the present invention is data from The National Long-Term Case Study (NLTCS) of StatLib, which consists of 16 binary attributes and 21674 records. This is an example of measuring the accuracy of the inferred update frequency for the change in the privacy protection level ε, and experimenting on the consumption of the privacy budget, with δ fixed at 0.001.

In addition, the update frequency according to the embodiment of the present invention means budget consumption. The parameters of the Poisson distribution are set by the number of queries, and the description will be given by using 10,000 arbitrary linear queries as an example.

First, as shown in FIG. 3, even if ε changes, it can be confirmed that a value almost similar to the actual update frequency is inferred. Therefore, based on the update count calculated by the method according to the embodiment of the present invention, it can be confirmed that the budget allocated to each update step is appropriate. This allows you to set a budget that can be allocated to each renewal stage for the level of privacy ε you want to achieve, which is very useful when the budget is limited.

And, as shown in Figure 4, looking at the example of comparing the budget consumption of the proposed method and the budget consumption of the existing technique for the same privacy performance, rearrangement of the query through the batch for the privacy protection level of all intervals You can see that this is actually effective in reducing the number of updates. Instead of unconditionally increasing the size of the batch, setting the appropriate thresholds does not excessively increase the response time of the query. Through this, it can be seen that the method according to the embodiment of the present invention consumes less budget for the same privacy performance than the existing method.

Although the embodiments of the present invention have been described in detail above, the scope of the present invention is not limited thereto, and various modifications and improvements of those skilled in the art using the basic concepts of the present invention defined in the following claims are also provided. It belongs to the scope of rights.

Claims (12)

As a query processing system saves privacy budgets,
Calculating a maximum update count for each of a plurality of received queries based on an original histogram and a virtual histogram generated from the original histogram;
Allocating a budget for each of the plurality of queries based on the calculated maximum update count and a predetermined overall privacy budget;
Including at least one query of the plurality of budgeted queries in one batch, and
Relocating at least one query included in the one batch and processing the relocated at least one query
Privacy budget saving method that includes. The method of claim 1,
The calculating of the maximum update number may include:
Generating a second histogram, the virtual histogram, having a uniform distribution form different from the first histogram, the original histogram, from a database in which the plurality of queries are received;
Calculating a first result value that is a query result value derived from the second histogram and a second result value that is a query result value derived from the first histogram;
Checking whether a difference between the first result value and the second result value deviates from a preset threshold value, and
If the difference deviates from the threshold, distributing a result of inserting noise into the second result value and updating the virtual histogram
Privacy budget saving method that includes. The method of claim 2,
The calculating of the maximum update number may include:
The maximum update count is based on an upper limit value of a relative entropy between the first histogram and the initialized second histogram, a histogram parameter, the number of the plurality of queries, and a Laplace distribution region that is out of the threshold. How privacy budgets are determined. The method of claim 1,
Including in one batch,
Including at least one query in the batch until the probability that the query enters according to the Poisson distribution is higher than the uniform distribution value that is the probability that the query enters arbitrarily;
Privacy budget saving method that includes. The method of claim 4, wherein
Including in the batch,
Setting a maximum threshold value of a batch size based on the maximum number of updates, the number of queries and the overall privacy budget
Privacy budget saving method that includes more. The method of claim 2,
The step of processing the one query,
Calculating a distance value if the difference between the first result value and the second result value is greater than the threshold value, and
Relocating the query with the largest distance value based on the calculated distance value
Including,
And the distance value is calculated as a difference between the original histogram and the virtual histogram for each of at least one query included in the batch. A query processing system for processing differential privacy queries,
For each of the plurality of received queries, a maximum update count is calculated based on the original histogram and the virtual histogram generated from the original histogram, and for each of the plurality of queries based on the calculated maximum update count and a predetermined overall privacy budget. A budget allocator that allocates a budget,
A batch size setting unit including at least one query among a plurality of budget-allocated queries in one batch, and
Query processing unit for processing at least one query included in the one batch
Query processing system comprising a. The method of claim 7, wherein
The budget allocation unit,
The upper limit value of the relative entropy between the first histogram, the original histogram, and the second histogram, from which the virtual histogram is initialized, a histogram parameter, the number of the plurality of queries, and a Laplace distribution region that is out of a threshold value. Query processing system for calculating the maximum number of updates based on. The method of claim 8,
The first histogram is an original histogram from a database in which the received plurality of queries are stored.
And the second histogram is a virtual histogram of a uniform distribution form different from the first histogram. The method of claim 9,
The batch size setting unit,
And at least one query is included in the batch until a probability that the query enters according to the Poisson distribution is higher than a uniform distribution value that is a probability that the query enters arbitrarily. The method of claim 10,
The batch size setting unit,
And the size of the batch is set to a maximum threshold value based on the maximum number of updates, the number of queries, and the total privacy budget. The method of claim 11,
The batch size setting unit,
Calculating a distance value between an original histogram and a virtual histogram for each of at least one query included in the batch, and relocating the query in the order of the query having the largest distance value based on the distance value.

Images