CN108537055A - A kind of privacy budget allocation of data query secret protection and data dissemination method and its system - Google Patents

Abstract

The invention discloses a kind of privacy budget allocation of data query secret protection and data dissemination methods, include the following steps：Step 1：Privacy budget parameters are set：Data administrator is denoted as ε according to the significance levels of data, the privacy budget of data-oriented；And setting is denoted as k to the basic inquiry times of data；Step 2：Calculate inquiry privacy budget every time；Step 3：The inquiry f, the susceptibility Δ f inquired submitted according to user；In conjunction with the privacy budget ε for distributing to inquiry, to query result application difference Privacy preserving algorithms, calculating needs noise to be added, obtains noise-containing query result；Step 4：According to the inquiry that user submits, noise-containing query result is returned, the privacy of data is made to be protected.This invention provides both the secret protection in data issuing process, anti-confederate's attack, the precision of k inquiry, will not cause availability of data too low because of the infinite sub-distribution of privacy budget before in turn ensuring.

Description

A privacy budget allocation and data release method for data query privacy protection and its system

technical field

The invention relates to a privacy budget allocation and data publishing method and system for data query privacy protection, and belongs to the technical field of information security.

Background technique

The deepening and popularization of information technology makes the collection, storage, release and analysis of data fast and convenient. Data mining technology can obtain valuable information from various published data, but at the same time it will also cause the leakage of personal information. As an effective privacy protection technology, differential privacy can ensure that personal information is not leaked while publishing valid data. .

Differential privacy protection data publishing can be divided into two types according to different implementation scenarios, namely interactive data publishing and non-interactive data publishing. In a non-interactive scenario, the system applies a differential privacy algorithm to the original data set, releases the noisy data set at one time, and then the user directly queries the noisy data set; in an interactive scenario, the user submits a query to the system, and the system Operate the original data set according to the query request and return the result to the user after applying the differential privacy algorithm. The user cannot see the whole picture of the data. According to the sequence composition nature of differential privacy, in non-interactive scenarios, as long as the differential privacy algorithm is applied to the original data set once, all the privacy budget ε is directly allocated to the algorithm. In an interactive scenario, every time a user submits a query, a differential privacy algorithm needs to be used, and the sum of the privacy budgets consumed by all algorithms is ε. The privacy budget ε represents the level of privacy protection. The smaller ε is, the higher the level of privacy protection is, but at the same time, more noise will be introduced, resulting in reduced data availability. Therefore, how to effectively allocate the privacy budget is a major challenge in differential privacy interactive scenarios. .

The existing data publishing algorithms in interactive scenarios mainly study how to answer more queries with a given privacy budget under the condition of certain accuracy. Although these algorithms guarantee the availability of data to a certain extent, However, the number of queries for users is limited, and infinite queries to the data set cannot be realized.

Contents of the invention

The technical problem to be solved by the present invention is to provide a privacy budget allocation and data release method and system for data query privacy protection in view of the defects of the background technology. While ensuring data privacy, users can query the database infinitely, and Data availability for the first k queries can be guaranteed.

In order to solve the above technical problems, the present invention adopts the following technical solutions:

A privacy budget allocation and data release method for data query privacy protection of the present invention, comprising the following steps:

Step 1: Set privacy budget parameters:

For the database stored in the computer system, the data administrator, according to the importance of the data, gives the privacy budget of the data, denoted as ε, where 0<ε≤1; and sets the number of basic queries on the data, denoted as k, where k<200;

Step 2: Calculate the privacy budget per query:

According to the privacy budget ε and the number of basic queries k, the Poisson probability mechanism is used to realize the infinite distribution of the privacy budget ε; each time a user submits a data query, the result is recorded as f _i , and the allocated privacy budget is calculated , denoted as ε _i , the specific value is:

Step 3: Calculate the noise added to the data:

For each data query result f _i of the user, calculate the sensitivity Δf _i ; combined with the privacy budget ε _i allocated to the query, the query result (data query is given by a computer application, such as: for a hospital system, a certain The user said, give me the number of cold patients today, and the hospital system will query this value. But this is real data, and hackers can finally derive a lot of sensitive information through other query results. Therefore, the present invention is to The method of privacy protection for sensitive information is to add a little noise to the real data. Of course, there must be a theoretical basis, that is, to meet the conditions of differential privacy protection. Differential privacy protection is a published theoretical result) Applying the differential privacy protection algorithm to calculate what needs to be added Noise, get query results containing noise;

Step 4: Return the result of user query:

According to the query submitted by the user, the query result containing noise is returned, so that the privacy of the data is protected.

In step 1, the privacy budget ε represents the level of privacy protection. The smaller ε, the higher the level of privacy protection. On the contrary, the lower the level of privacy protection. At the same time, ε also affects the size of the noise. The smaller ε will introduce more loud noise;

The basic query times k represents the user's ideal query times, and accurate query results are returned after k times of queries; in order to ensure data privacy, when the query times exceed k, the system returns noisy query results.

In step 2, the sequence combination property of differential privacy is applied:

Differential privacy protection algorithms M ₁ , M ₂ ,..., M _∞ satisfy ε _i -differential privacy respectively, where, 1≤i≤∞, for the same data set D, the algorithm {M ₁ , M ₂ ,...,M _∞ }'s sequence combination provides

In step 2, the Poisson probability mechanism is specifically as follows:

The Poisson distribution satisfies Expected value E(X)=λ, which represents the average occurrence rate of random time per unit time;

In order to realize infinite queries of users in interactive scenarios, each time a user submits a query, the system will allocate a privacy budget ε _i for the query and apply the differential privacy protection algorithm M _i , M _i satisfies ε _i - differential privacy, 1≤i≤ ∞, the privacy budget and should satisfy

Let the expected value of the Poisson distribution be equal to the number of basic user queries, that is, E(X)=k, then we have Multiplying both sides by ε, That is, it satisfies the above infinite allocation of privacy budget;

The privacy budget allocation calculation method under the Poisson mechanism is as follows:

In step three, the calculation method of the sensitivity Δf _i is:

For any function f:D→R ^d , the sensitivity of function f is

Among them, datasets D and D' are adjacent datasets with the same attribute structure, and there is at most one record difference between them.

In step 3, noise is generated through Laplacian distribution to achieve differential privacy protection, and the output result is: in It is the Laplacian noise variable, and the magnitude of the noise is proportional to the query sensitivity Δf _i and inversely proportional to the allocated privacy budget ε _i .

A privacy budget allocation and data release system for data query privacy protection according to the present invention, comprising:

The differential privacy budget total amount setting module is used to set the differential privacy budget total amount according to the degree of privacy protection demand;

The differential privacy budget sequence generation module is used to calculate the differential privacy budget in each data query and generate a differential privacy budget sequence;

The random noise calculation module is used to calculate the random noise by using the differential privacy budget sequence according to the query submitted by the user and the sensitivity of the query;

The query result returning module is used to calculate the query result containing noise and return the query result to the user.

In the data query scenario, the invention not only ensures that the published data does not leak the personal privacy of the user, but also improves the usability of the data. After determining the size of the privacy budget ε and the number of basic queries k, the method uses the Poisson mechanism to allocate the privacy budget infinitely, obtains a privacy budget sequence {ε _i }, and then distributes it to each query f _i of the user A privacy budget ε _i can provide unlimited queries and ensure that the first k queries provide more accurate query results. The present invention not only provides privacy protection in the data release process, resists collusion attacks, but also ensures the accuracy of the first k queries, and will not cause too low data availability due to infinite allocation of privacy budgets.

Description of drawings

Figure 1 is a flowchart of the release mechanism;

Figure 2 is a flow chart of Poisson mechanism allocation privacy budget;

Figure 3 is a partial tabular diagram of the Waitakere dataset statistics.

Detailed ways

The implementation of the technical solution of the present invention will be described in further detail below in conjunction with the accompanying drawings:

Aiming at the problem of privacy budget allocation in the data publishing process in the differential privacy interactive scenario, the present invention proposes a Poisson mechanism that can realize infinite allocation of privacy budget. Users can set the number of basic queries k according to query requirements, and the first k queries More accurate query results can be obtained, which ensures the data availability of the query results. At the same time, when the number of queries exceeds k, the allocated privacy budget will become smaller and smaller, achieving the purpose of privacy protection.

As shown in Figure 1 and Figure 2, the present invention comprises the following steps:

Step 1: The system sets a privacy budget ε

The privacy budget ε represents the level of privacy protection. The smaller the ε, the higher the level of privacy protection. On the contrary, the lower the level of privacy protection. At the same time, ε also affects the size of the noise. The smaller the ε, the greater the noise will be introduced.

Step 2: The user enters the number of basic queries k

The number of basic queries k represents the user's ideal query times, and the system returns more accurate query results for these k queries. At the same time, in order to ensure the privacy of data, when the number of queries exceeds k, the system will return query results with relatively high noise.

Step 3: The Poisson mechanism allocates the privacy budget infinitely

The Poisson distribution satisfies Expected value E(X)=λ, which represents the average occurrence rate of random time per unit time.

In order to realize infinite queries of users in interactive scenarios, each time a user submits a query, the system will allocate a privacy budget ε _i for the query and apply the differential privacy protection algorithm M _i , M _i satisfies ε _i - differential privacy (1≤i ≤∞), privacy budget and should satisfy

Let the expected value of the Poisson distribution be equal to the number of basic user queries, that is, E(X)=k, then we have Multiplying both sides by ε, Infinite allocations to satisfy privacy budgets.

Because of the Poisson distribution, when the value of X is near the mean, the value of P(X) is larger, so when 1≤i≤k, that is, for the first k queries, the privacy budget It can be guaranteed that the first k queries can share a larger privacy budget and obtain more accurate query results. When i>k, the number of user queries exceeds the number of basic queries, in order to prevent data privacy information from being mined due to multiple queries, start to limit the accuracy of query results and allocate a relatively small privacy budget Therefore, the privacy budget allocation method under the Poisson mechanism is as follows:

Step 4: Laplace mechanism adds random noise to query results

The real output result of the noise perturbation generated by the Laplacian distribution is used to realize differential privacy protection, and the output result is: in It is the Laplacian noise variable, and the magnitude of the noise is proportional to the query sensitivity Δf _i and inversely proportional to the allocated privacy budget ε _i .

Step 5: Return noisy results to the user

Referring to Fig. 3, the following takes the statistical information of the Waitakere data set as an example to specifically introduce the implementation of the present invention:

Waitakere is a semi-synthetic dataset generated from the New Zealand 2006 census grid dataset, with a total population of 186,471 distributed across 1,340 grid areas. We randomly placed residents into each grid block, and then the entire area Divide it into 7,725 non-overlapping rectangles (154×113m2 in size), and count the population in each rectangle.

Step 1. Take the privacy budget ε=1, and take the number of basic queries k=10;

Step 2. Calculate the privacy budget based on the Poisson mechanism:

Step 3. According to the query submitted by the user, Laplace adds random noise to the query results. In order to simplify the operation, we set the query set F={f|f to find the total number of people in the interval [456,459]}, that is, f ₁ =f ₂ =… =f _n =...=f, Δf ₁ =Δf ₂ =...=Δf _n =...=Δf=1, f ₁ (D)=f ₂ (D)=...=f _n (D)=...=f(D )=131.

When the user submits the first query f ₁ , add a random noise to the query result f ₁ (D) Therefore, the query result with noise may be M ₁ (D)=131+3.762=134.762.

When the user submits the second query f ₂ , add a random noise to the query result f ₂ (D) Therefore, the noisy query result may be M ₂ (D)=131-5.698=125.20.

The following queries can be deduced by analogy. When the user submits 10 queries, a total of 0.996 privacy budget is consumed. It can be seen that most of the privacy budget is used in the first 10 queries, providing more accurate query results for the first 10 queries .

When the user submits the 11th query f ₁₁ , the random noise added to the query result f ₁₁ (D) Generally, the random numbers subject to this distribution are relatively large, so the query result with noise may be M ₂ (D)=131+122.368=253.368. It disturbs the real query results to a great extent and achieves the purpose of privacy protection.

Subsequent queries can be deduced by analogy, the more the number of queries, the smaller the allocated privacy budget.

In summary, the present invention proposes a privacy budget allocation and data release method for data query privacy protection. According to the sequence combination property of differential privacy, the Poisson mechanism is used to realize the infinite allocation of privacy budget, while ensuring the first k times The query accuracy not only ensures the privacy of the data, but also ensures the data availability of the first k queries.

The above descriptions are only part of the embodiments of the present invention. It should be pointed out that those skilled in the art can make some improvements and modifications without departing from the principles of the present invention. It should be regarded as the protection scope of the present invention.

Claims (7)

1. A privacy budget allocation and data release method for data query privacy protection, characterized in that, comprising the following steps: Step 1: Set privacy budget parameters: For the database stored in the computer system, the data administrator, according to the importance of the data, gives the privacy budget of the data, denoted as ε, where 0<ε≤1; and sets the number of basic queries on the data, denoted as k, where k<200; Step 2: Calculate the privacy budget per query: According to the privacy budget ε and the number of basic queries k, the Poisson probability mechanism is used to realize the infinite distribution of the privacy budget ε; each time a user submits a data query, the result is recorded as f _i , and the allocated privacy budget is calculated , denoted as ε _i , the specific value is: Step 3: Calculate the noise added to the data: For each data query result f _i of the user, calculate the sensitivity Δf _i ; combined with the privacy budget ε _i allocated to the query, apply the differential privacy protection algorithm to the query result, calculate the noise that needs to be added, and get the query result containing noise; Step 4: Return the result of user query: According to the query submitted by the user, the query result containing noise is returned, so that the privacy of the data is protected. 2. The privacy budget allocation and data release method of data query privacy protection according to claim 1, wherein in step 1, the privacy budget ε represents the level of privacy protection, the smaller ε, the higher the level of privacy protection, Conversely, the lower the level of privacy protection, and ε also affects the size of the noise, the smaller ε will introduce greater noise; The basic query times k represents the user's ideal query times, and accurate query results are returned after k times of queries; in order to ensure data privacy, when the query times exceed k, the system returns noisy query results. 3. The privacy budget allocation and data release method of data query privacy protection according to claim 1, characterized in that, in step 2, the sequence combination property of applying differential privacy: Differential privacy protection algorithms M ₁ , M ₂ ,..., M _∞ satisfy ε _i -differential privacy respectively, where, 1≤i≤∞, for the same data set D, the algorithm {M ₁ , M ₂ ,...,M _∞ }'s sequence combination provides 4. The privacy budget allocation and data publishing method of data query privacy protection according to claim 3, characterized in that, in step 2, the Poisson probability mechanism is specifically as follows: The Poisson distribution satisfies Expected value E(X)=λ, which represents the average occurrence rate of random time per unit time; In order to realize infinite queries of users in interactive scenarios, each time a user submits a query, the system will allocate a privacy budget ε _i for the query and apply the differential privacy protection algorithm M _i , M _i satisfies ε _i - differential privacy, 1≤i≤ ∞, the privacy budget and should satisfy Let the expected value of the Poisson distribution be equal to the number of basic user queries, that is, E(X)=k, then we have Multiplying both sides by ε, That is, it satisfies the above infinite allocation of privacy budget; The privacy budget allocation calculation method under the Poisson mechanism is as follows: 5. The privacy budget allocation and data release method of data query privacy protection according to claim 1, wherein in step 3, the calculation method of the sensitivity Δf _i is: For any function f:D→R ^d , the sensitivity of function f is Among them, datasets D and D' are adjacent datasets with the same attribute structure, and there is at most one record difference between them. 6. The privacy budget allocation and data release method of data query privacy protection according to claim 5, characterized in that, in step 3, noise is generated through Laplace distribution, thereby realizing differential privacy protection, and the output result is: in It is the Laplacian noise variable, and the magnitude of the noise is proportional to the query sensitivity Δf _i and inversely proportional to the allocated privacy budget ε _i . 7. A privacy budget allocation and data release system for data query privacy protection, characterized in that it includes: The differential privacy budget total amount setting module is used to set the differential privacy budget total amount according to the degree of privacy protection demand; The differential privacy budget sequence generation module is used to calculate the differential privacy budget in each data query and generate a differential privacy budget sequence; The random noise calculation module is used to calculate the random noise by using the differential privacy budget sequence according to the query submitted by the user and the sensitivity of the query; The query result returning module is used to calculate the query result containing noise and return the query result to the user.