JP2013152670A - Database disturbance parameter setting device, database disturbance system and method, and database disturbance device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a technique capable of achieving Pk-anonymity even if an attacker can view arbitrary M attributes among A attributes.SOLUTION: A database disturbance parameter setting device uses a database disturbance parameter determination part 11 for determining a parameter pused for a database disturbance part 21 which performs disturbance of a table by performing disturbance based on a function A(p)determined by a prescribed parameter pto make an attribute v' after disturbance, assuming that |N| is the number of records, M is a prescribed natural number not more than A-1, α=((k-1)/(N-1)), ess inf * is essential lower limit of *, the attribute value of each attribute a is v for each of the attributes included in a table, the domain of attribute values u, v before disturbance is V, and attribute values v', u' after disturbance is V'.

Description

  The present invention relates to a technique for performing data mining while protecting privacy.

  A database disturbance technique that satisfies so-called Pk-anonymity and a parameter determination technique used in the database disturbance technique have been proposed in Non-Patent Document 1 (for example, see Non-Patent Document 1). Specifically, Non-Patent Document 1 describes a database disturbance technique and a parameter determination technique for realizing Pk-anonymity when an attacker can see all of the A attributes. Yes.

  Pk-anonymity is a property that each record in the database and an individual corresponding to each record cannot be associated with a probability of 1 / k or more.

University of Igarashi, 2 others, “Randomization method that satisfies k-anonymity in numerical attributes”, CSS 2011, 2011

  However, a technique for realizing Pk-anonymity when M is an integer equal to or less than A-1 and an attacker can view any M attributes among the A attributes is not patented. It is not described in Document 1.

  The present invention relates to a database disturbance parameter setting device, a database disturbance system and method, and a database for realizing Pk-anonymity when an attacker can view any M attributes of A attributes. An object is to provide a disturbance device.

In the database disturbance parameter setting device according to one aspect of the present invention, the table includes a plurality of records, A is a predetermined integer of 2 or more, each record includes a record identifier and A attribute values, and k is a security parameter. , | N | is the number of records, M is a predetermined natural number less than or equal to A-1, α = ((k−1) / (N−1)) ^{1 / M} , and ess inf is essentially the lower limit for each attribute included in the table, then the attribute values of the respective attributes a and v, disturbance before an attribute value v, the domain of u and V _a, the attribute values v after disturbance ', u' Database disturbance in which a domain is defined as V ′ _a , disturbance is performed based on _a function A _a (pa) _{v, v ′} determined by _a predetermined parameter pa, and the attribute value v ′ after the disturbance is used to disturb the table Used in equipment In Database disturbance parameter determining device for determining a that parameter p _a, parameter determination unit determining a parameter p _a satisfying the following formula

including.

  The database disturbance system by one aspect | mode of this invention contains the said database disturbance parameter determination apparatus and the said database disturbance apparatus.

In the database disturbance device according to an aspect of the present invention, the table includes a plurality of records, A is a predetermined integer equal to or greater than 2, each record includes a record identifier and at least one attribute value, k is a security parameter, N | is the number of records, M is a predetermined natural number equal to or less than A-1, α = ((k−1) / (N−1)) ^{1 / M} , and ess inf · is an essential lower limit of for each attribute of the following number M included in the table, then the attribute values of the respective attributes a and v, disturbance before an attribute value v, the domain of u and V _a, the attribute values v after disturbance ' , U ′ is defined as V ′ _a , disturbance based on the function A _a (p _a ) _{v, v ′} determined by _a predetermined parameter pa is performed, and the attribute value v ′ after the disturbance is set, thereby disturbing the table. Including the disturbance section to perform Over data p _a satisfy the relationship of the following formula.

  Pk-anonymity can also be realized when an attacker can view any M attributes of A attributes.

The block diagram for demonstrating the database disturbance system of 1st embodiment. The flowchart for demonstrating the database disturbance system of 1st embodiment. The figure for demonstrating the example of the database used as the object of disturbance. The figure for demonstrating the example of the database used as the object of disturbance.

  Embodiments of the present invention will be described below with reference to the drawings.

[First embodiment]
The database disturbance system of 1st embodiment is provided with the data provider apparatus 2, the anonymous data server 1, and the analysis user apparatus 3, as illustrated in FIG.

  The anonymous data server 1 is a server that stores anonymized data. The anonymous data server 1 includes, for example, a parameter determination unit 11 and a storage unit 12. The parameter determination unit 11 corresponds to the database disturbance parameter determination device in the claims.

  The data provider device 2 is a subject that intends to deposit data in the anonymous data server 1. The data provider device 2 is, for example, a computer such as a PC or a portable information terminal device possessed by a user who wants to deposit data in the anonymous data server 1. Two or more data provider devices 2 may exist. The data provider device 2 includes a disturbing unit 21, for example. The disturbing unit 21 corresponds to the database disturbing device recited in the claims.

  The analysis user device 3 is a device that performs aggregation processing based on anonymized data. Two or more analysis user devices 3 may exist.

  First, a database to be disturbed will be described. The database to be disturbed is composed of a plurality of records as illustrated in FIGS. 3 and 2.

  Each record is composed of a record identifier and at least one attribute value. The record identifier is an identifier for identifying an individual and is a so-called record ID. The record identifier is, for example, a name or an ID number corresponding to the name. In this embodiment, the record identifier is an identifier for identifying the data provider or the data provider device 2.

  Each attribute value is a vector included in the subset V of the n-dimensional real vector, and is a so-called numerical attribute value. n is an integer of 1 or more. When n = 1 and the attribute is, for example, “intermediate test score” or “term test score”, the attribute value is any integer from 0 to 100.

  Each attribute value may be a so-called category attribute value. The category attribute value is, for example, an attribute value such as gender, and is an attribute value that is limited to several values that the attribute value can take, unlike the numerical attribute value.

  FIG. 3 illustrates a database when each attribute is a numerical attribute. On the other hand, FIG. 4 illustrates a database including both numerical attribute attributes and category attribute attributes.

<Step S1>
First, the parameter determination unit 11 of the anonymous data server 1 determines parameters p _a satisfying the following equation (step S1). Determined parameter p _a is transmitted to the data provider device 2. Let A be the number of attribute types. A is a predetermined integer of 2 or more. Parameter determination unit 11, the attribute a (a = 1,2, ..., A) for each, to determine the parameters _{p a.} Parameter p _a is calculated by for example the so-called bisection method.

Here, α = ((k−1) / (N−1)) ^{1 / M} , where k is a security parameter, | N | is the number of records, and M is a predetermined natural number equal to or less than A-1. . In addition, ess inf · is an essential lower limit of ·.

  When the domain of the function f (x) is χ, the essential lower limit ess inf f (x) of the function f (x) can be specifically written as follows. Let μ ({f <b}) be a measure (eg, area or volume) of the region where the function f (x) <b. R in the following formula means a real number.

V _a is a definition area of the attribute values v and u before the disturbance of the attribute a, and V ′ _a is a definition area of the attribute values v ′ and u ′ of the attribute a after the disturbance. A _a (p _a ) _{v, v ′} is _a function determined by _a predetermined parameter pa, and represents the probability that the attribute value v before disturbance becomes the attribute value v ′ after disturbance. _{A a (p a) u,} v ', A a (p a) v, u' and _{A a (p a) u,} ' for _{even, A a (p a) v} , v' u is the same as.

Attribute a is a numeric attribute, if the function _{A a (p a) v,} v ' is the probability density function is a Laplacian distribution of the dispersed 2p _a ² defined by the following equation,

Parameter determining unit 11 is specifically determine the parameters p _a satisfying the following equation. μ is, for example, 0. In the following equation, || · || ₁ is the L1 norm of •, and the bottom of log is the Napier number e.

The attribute a is category attribute, the function _{A a (p a) v,} v ' is an attribute value v, a predetermined probability and maintained at _{(p a + (1-p} a) / | | V a) In the case of a function that replaces the attribute value v ′ other than the attribute value v of the attribute a with _a predetermined probability (1−p _a ) / | V _a | _a is determined. | V _a | is the number of elements in the set V _a .

<Step S2>
Disturbance portion 21 of each of the data provider device 2, the attribute value of each attribute to be disturbance, disrupting performed disturbance based on determined by the parameter p _a function _{A a (p a) v,} v '( step S2 ). In this embodiment, disturbance portion 21 of each data provider apparatus 2, the attribute value v for each attribute a having itself performs disturbance based on the parameter p _a the determined function A _{a (p} a) _v, v _' The attribute value v ′ after the disturbance is assumed. Each attribute value v ′ after the disturbance is transmitted to the anonymous data server 1.

If attribute a subject to disturbance is numeric attribute, the function _{A a (p a) v,} v ' is the probability density function. For example, the function A _a (p _a ) _{v, v ′} is a probability density function that is a Laplace distribution with _a variance ² p _a ² defined by the following equation. || · || ₁ is the L1 norm of. For example, μ = 0.

When the attribute a to be disturbed is a numerical attribute, the disturbance based on the function A _a (p) _{v, v ′} is the probability density function A _a (p ) It means that the value according to _{v and v ′} is added to obtain the attribute value v ′ after disturbance. That is, the attribute value v ′ after disturbance is equal to the attribute value v before disturbance + the probability density function A _a (p) _{v, v ′} .

Hereinafter, the “value according to the probability density function f” and the “value according to the Laplace distribution” will be described. Here, in order to simplify the notation, the probability density function f is written. The probability density function f may be considered to be the same as the probability density function A _a (p) _{v, v ′} .

1. Regarding “value according to probability density function f” (1) When domain and attribute value of probability density function f are one-dimensional (i) Cumulative distribution function F (x) = ∫− _∞ ^x f (x ′) dx ′ Ask.
(Ii) An inverse function F ⁻¹ of the cumulative distribution function F (x) is obtained.
(Iii) Generate a uniform random number r on the interval [0, 1].
(Iv) F ⁻¹ (r) is output as “a value according to the probability density function f”.

When the cumulative distribution function F (x) or the inverse function F ⁻¹ is obtained by a mathematical formula, F ⁻¹ (r) may be calculated based on the mathematical formula. Otherwise, F ⁻ is calculated by numerical calculation. ¹ (r) may be calculated.

(2) When the domain and the attribute value of the probability density function f are n-dimensional The following (i) and (ii) are performed for each of i = 0,.

(I) x ₀ to x _i−1 are fixed, x _{i + 1} to x _n−1 are integrated, and a probability density function f _{i in} which only x _i is left as a variable is obtained.

(Ii) Since the domain of the probability density function f _i is one-dimensional, the “probability density” is determined by a method similar to the method described above in “(1) When the domain and attribute value of the probability density function f are one-dimensional”. The value according to the function f _i is calculated.

By calculating “value according to probability density function f _i ” for each of i = 0,..., n−1, n “values according to probability density function f _i ” are obtained.

  In the case where the probability density function is a Laplace distribution, it is as follows.

2. About “value according to Laplace distribution” (1) When the domain and attribute value of Laplace distribution are one-dimensional (i) Uniform random number r on interval [0, 1], Uniform random number on interval (0, 1) b is generated.
(Ii) (-1) ^b σlogr + μ is output as “value according to Laplace distribution”.

(2) When the domain and attribute value of the Laplace distribution are n-dimensional (i) n in the same manner as the method described in “(1) When the domain and attribute value of the Laplace distribution is one-dimensional” above X ₀ , x ₁ ,..., X _n−1 which are “values according to the Laplace distribution”.
(Ii) These x ₀ , x ₁ ,..., X _n−1 are output as “values according to Laplace distribution”.

If attribute a subject to disturbance is category attribute, the function _{A a (p a) v,} v ' is an attribute value v, a predetermined probability _{(p a + (1-p} a) / | V _a |), and a function that replaces an attribute value v ′ other than the attribute value v of the attribute a with a predetermined probability (1−p _a ) / | V _a |. The attribute value v is replaced with an attribute value v ′ other than the attribute value v of the attribute a. For example, when the attribute a is gender and the attribute value v is “male”, the attribute value “m” is attributed. It means replacing with the value “female”. See Reference 1 for details of maintenance-replacement perturbation of maintenance probability ρ.
[References] JP 2011-100116 A

  In this way, by disturbing the attribute value, Pk-anonymity can be realized when an attacker can view any M attributes among the A attributes. Here, the proof is omitted.

<Step S3>
The anonymous data server 1 stores each attribute value v ′ after disturbance received from each data provider device 2 in the storage unit 12 in association with each data provider device 2 (step S3). That is, a plurality of pairs of the record identifier of the data provider device 2 and each attribute value v ′ after the disturbance received from the data provider device are stored in the storage unit 12 as an anonymized database.

<Step S4>
The analysis user device 3 transmits designation information that is information about M attributes designated in advance to the anonymous data server 1 (step S4). The M attributes may be specified in advance by the analysis user who operates the analysis user device 3, or may be specified in advance by the analysis user itself.

<Step S5>
The anonymous data server 1 extracts a column of attribute values of M attributes specified by the received designation information from the database stored in the storage unit 12, and transmits it to the analysis user device 3 (step S5). . For example, when the database is the database illustrated in FIG. 3, M = 2, and two attributes “intermediate test score” and “term test score” are designated, the attribute “intermediate test” The attribute value column a1 composed of the attribute value of “number of points” and the attribute value column a2 composed of the attribute value of the attribute “score for the term test” are transmitted to the analysis user device 3.

<Step S6>
The aggregation unit 31 of the analysis user device 3 performs an aggregation process using the received M attribute value sequence (step S6). The tabulation unit 31 estimates a tabulation result such as cross tabulation using, for example, an iterative Bayesian method described in Reference Document 2.

[Reference 2]
University of Igarashi, 2 others, “Efficient privacy protection cross-tabulation applicable to multi-valued attributes”, Computer Security Symposium 2008

[Modifications, etc.]
The disturbing unit 21 may be provided in the anonymous data server 1. That is, in this case, the disturbing unit 21 provided in the anonymous data server 1 disturbs the attribute value received from each data provider device 2 in the same manner as described above and stores it in the storage unit 12.

  Moreover, the parameter determination part 11 may be provided in each data provider apparatus 2. FIG.

  Further, the data provider device 2 and the anonymous data server 1 may be provided in the same device.

  In addition, the present invention is not limited to the above-described embodiment. For example, the various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes.

  Further, when the above-described configuration is realized by a computer, the processing content of each unit that each device should have is described by a program. Each part is realized on the computer by executing this program on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

  Needless to say, other modifications are possible without departing from the spirit of the present invention.

DESCRIPTION OF SYMBOLS 1 Anonymous data server 11 Parameter determination part 12 Storage part 2 Data provider apparatus 21 Disturbance part 3 Analysis user apparatus 31 Total part

Claims (5)

The table includes a plurality of records, A is a predetermined integer of 2 or more, each record includes a record identifier and A attribute values, k is a security parameter, | N | is the number of records, and M is A With respect to each of the attributes included in the table, a predetermined natural number of −1 or less, α = ((k−1) / (N−1)) ^{1 / M} , ess inf · the attribute value of the respective attribute a and v, disturbance before an attribute value v, the domain of u and V _a, the attribute values v after disturbance ', u' the domain of the V _'a, predetermined parameters determining the parameter p _a used in database disruptor for performing disturbance of the table by a p _a the determined function _{a a (p a) v,} v ' attribute value after disturbance performed disturbance based on v' Database disturbance parameter In over data determining device,
Parameter determination unit determining a parameter p _a satisfying the following formula

A database disturbance parameter determination device including: In the database disturbance parameter determination apparatus of Claim 1,
When the attribute a is a numerical attribute and the function A _a (p _a ) _{v, v ′} is a probability density function that is a Laplace distribution with _a variance 2pa ² defined by the following equation: | ₁ as the L1 norm of

The parameter determination unit determines _a parameter pa satisfying the following formula,

| _{V a} | as the number of the set _{V a} elements, the attribute a is category attribute, the function _A a _{(p a) v, v 'is} given the attribute values v probability _(p a + (1 −p _a ) / | V _a |), and a function that replaces an attribute value other than the attribute value v of the attribute a with a predetermined probability (1-p _a ) / | V _a | parameter determination unit determines parameters p _a satisfying the following equation,

Database disturbance parameter determination device. The database disturbance parameter determination device according to claim 1 or 2,
The database disruptor;
Including database disturbance system. The table includes a plurality of records, A is a predetermined integer of 2 or more, each record includes a record identifier and at least one attribute value, k is a security parameter, | N | is the number of records, and M is A −1 or less, α = ((k−1) / (N−1)) ^{1 / M} , ess inf · for each attribute, the attribute values of the respective attributes a and v, disturbance before an attribute value v, the domain of u and V _a, the attribute values v after disturbance ', u' V the domain of _'a as includes a disturbance unit which performs disturbance of the table by a predetermined parameter p _a the determined function _{a a (p a) v,} v ' performs disturbance based on disturbance after the attribute values v',
The parameter p _a satisfies the relation of the following formula,

Database disturbance device. The table includes a plurality of records, A is a predetermined integer of 2 or more, each record includes a record identifier and at least one attribute value, k is a security parameter, | N | is the number of records, and M is A −1 or less, α = ((k−1) / (N−1)) ^{1 / M} , ess inf · for each attribute, the attribute values of the respective attributes a and v, disturbance before an attribute value v, the domain of u and V _a, the attribute values v after disturbance ', u' V the domain of _'a In the database disturbance method in which disturbance is performed based on _a function A _a (pa) _{v, v ′} determined by _a predetermined parameter pa and the attribute value v ′ after the disturbance is set to disturb the table.
Parameter determination unit, a parameter determining step of determining a parameter p _a satisfying the following equation,

Disturbance portion, the attribute value v for each attribute a of M following number contained in the table, the function A _{a (p} a) determined by the predetermined parameters p _{a v,} v attributes after disturbance performed disturbance based on _' The disturbance step with value v ′;
Database disruption method including.

Images