JP6466812B2 - Name identification system, apparatus, method and program - Google Patents

Description

  The present invention relates to a technique for naming tables owned by a plurality of different subjects.

First, a model assumed by the present technology will be described. n parties P ₀ , ..., P _n-1 have tables τ ₀ , ..., τ _n-1 with each other, each table has the same ID r∈R, but Each table has different attributes, such as age for a party table and annual income for a table at a different party.

  Consider joining such tables without giving unnecessary information to each other as much as possible. By doing so, analysis such as correlation between age and annual income becomes possible.

For the sake of simplicity, the description in this document, a party to obtain a bound table, but the P _0, parties to obtain a bound table may be any party other than P _0.

For example, a table in which P ₀ is joined can be obtained by the following 1. to 3.

1. Using deterministic encryption (if the same value is encrypted, the same ciphertext is used), the ID and table are encrypted so that only P ₀ can be decrypted, and sent to P ₀ .
2.P ₀ sees the encrypted ID and combines records with the same value.
3. P ₀ decodes all values.

However, by matching P ₀ with the original table, it is possible to match the individual I with the original table with the individual I with the combined table. Then, information about an individual that is essentially unnecessary for analysis such as correlation is passed to P ₀ . For example, in order to obtain an analysis result that “when the age is 30 years old, the annual income rises a lot”, P ₀ has obtained information such as “Mr. I does not increase the annual income even at the age of 30” , Privacy issues may arise.

  An object of the present invention is to provide a name identification system, apparatus, method, and program capable of protecting privacy for a subject to be restored.

In the name identification system according to one aspect of the present invention, n is a predetermined integer equal to or greater than 1, and only the random number is changed without changing the contents of the ciphertext so that only the 0th device can decrypt each attribute value of the table of itself. In the name collation system including the 0th device to the (n-1) th device including the encryption unit that encrypts a table of itself by encrypting using a public key encryption capable of re -randomization, the n-1 device Is the name identification table, which is a table obtained by encrypting the tables encrypted by the n-1 apparatus from the 0th apparatus, and the attribute value of each attribute a∈A ₀ of the name identification table as a set A ₀ of the attributes of the table possessed by the 0th apparatus. determining whether to maintain like regular maintenance substituted disturbance in accordance with a predetermined parameter [rho _a relative, for the determined attribute value to maintain be re randomized to only the 0 device can decrypt A disturbance unit that generates a random number for an attribute value determined not to be maintained and replaces the random number with an encrypted value so that only the 0th device can decrypt the random number. And a rearrangement unit that creates a rearranged table by rearranging the records in the name identification table after the disturbance, and the zeroth device further includes a decoding unit that decodes each attribute value of the rearranged table. I have.

In the name identification device according to one aspect of the present invention, the 0th device to the (n-1) th device encrypt each n so that only the 0th device can decrypt each attribute value of the table, with n being a predetermined integer of 1 or more. From the 0th device to the (n-1) -th device, including an encryption unit that encrypts a table that it has by encrypting it using public key cryptography that can be re-randomized to change only the random number without changing the content of the sentence The table identified by the name of the encrypted table is referred to as a name identification table, and the attribute value of each attribute a∈A ₀ of the name identification table is normally set in accordance with _a predetermined parameter ρ _a as the attribute set A ₀ of the table of the 0th device. maintaining determine whether to maintain the same manner as substituted disturbance, for determining attribute values to maintain performs disturbance name identification table by re randomized so that only the zeroth device can decrypt, Wei A random number is generated for the attribute value determined to be not used, and a disturbance unit that replaces the random number with an encrypted value so that only the 0th device can decrypt the random value, and a record of the name identification table after the disturbance are arranged. It is the n-1th apparatus which further contains the rearrangement part which produces the table after rearrangement by changing.

  Privacy can be protected for the subject to restore.

The block diagram for demonstrating the example of a name collation apparatus. The flowchart for demonstrating the example of a name collation method. The figure which shows the example of a name collation protocol.

  First, the matter which becomes the basis of this invention is demonstrated.

[notation]
abs (x) indicates the absolute value of x. For set A, | A | represents the number of elements in the set, and g represents a group. X ← B indicates that if B is a set, an element is selected at random from B and assigned to x, and if B is an algorithm, the output of B is assigned to x.

[Data format and notation]
The data before and after anonymization is a table in which each row represents one person's data (this is called a record), and values such as age and annual income called attributes are entered in each column.

  Gives definitions for formal discussion of anonymization for tables.

・ Τ, τ: Random variable of table before anonymization and its instance ・ Τ ', τ': Random variable of anonymization table and its instance ・ R, R ': Record set of table before / after anonymization ・ A , A ': Set of attributes before / after anonymizationV _a , V _a ': Set of possible attribute values of attribute a∈A before / after anonymizationV, V ': Before / after anonymization A set of attribute value combinations that a record can take. In other words, V = Π _a∈A V _{a when the} direct product is expressed by Π.
V _a : an instance of an attribute value of attribute a∈A of a record.
・ Δ, δ: Random variables for privacy protection and their instances ・ f _X : Probability density function for random variables X ・ Random substitution random variables such as Π, π: R → R ′ and their instances τ, τ ′ , δ are functions such as τ: R → V, τ ′: R ′ → V ′, δ: (R → V) → (R → V ′), and π, δ, τ, τ ′ In the meantime, δ (τ) = τ ′ · π holds. Also, let τ (r) ^(a) be τ ′ (r ′) ^{(a ′)} as the attribute value of attribute a of record r, and attribute value of attribute a ′ of record r ′.

[Pk-anonymity]
Pk-anonymity is a privacy protection index proposed in References 1 and 2. For a certain τ ', r∈R, r'∈R, Δ (Τ) = Τ' ・ Π, Pr [Π (r) = r '| Τ' = τ '] is the probability of successful attack, and Pk-anonymous Sex is defined as:

  [Reference 1] Dai Ikarashi, Ryo Kikuchi, Koji Chida, and Katsumi Takahashi, "k-anonymous microdata release via post randomisation method", In IWSEC 2015 (to appear), 2015.

[Reference 2] University of Igarashi, Koji Senda, Katsumi Takahashi, "Expansion of k-anonymity to probabilistic index and its application examples", In CSS, 2009.
For real k ≧ 1, 'is, an attacker with a background knowledge f _Τ, any table Τ, record r∈R, record r'∈R' some privacy protection process Δ and anonymous table τ for,

Then, (Δ, τ ′) satisfies Pk-anonymity for an attacker with background knowledge f _Τ .

  This definition is extended from the definition in Reference 1 so that an attacker with weak background knowledge can also be assumed.

[Pk-anonymization]
Pk-anonymization is a process for satisfying Pk-anonymity, and here, maintenance substitution disturbance (for example, see references 1 and 3) for a category attribute is handled.

  [Reference 3] Rakesh Agrawal, Ramakrishnan Srikant, and Dilys Thomas, "Privacy preserving OLAP", In SIGMOD Conference, pp. 251-262, 2005.

  As a kind of Pk-anonymization, the method of maintaining attribute values with a certain probability and replacing them with random values is called maintenance replacement disturbance.

The transition probability matrix A, A ^(a) the value of the attribute a representation how changed by anonymous | a matrix | V _a | × | V _'a. Each element of A ^(a)

Is the probability that the attribute value v _a transitions to v ′ _{a due} to anonymization. Maintenance substitution disturbance is any a∈A, v _a ∈V _a , 0 ≦ ρ _a ≦ 1,

It satisfies. The transition probability matrix A is A = Π _a∈A A ^(a) where Π is the Kronecker product. At this time, A _{v, v ′} is

Similarly, when the attribute value of the record is v, there is a probability that the attribute value will change to v ′ by anonymization.

  Maintenance replacement disturbance is

When

By doing so, it is known that Pk-anonymity can be satisfied.

[P (c, L) -diversity]
In addition to personal identification risk, attribute estimation risk is known as another typical privacy risk.

  When considering attribute estimation risk in addition to identification risk, attribute estimation risk can be reduced by using P (c, L) -diversity. See Reference 4 for a detailed explanation.

  [Reference 4] University of Igarashi, Koji Senda, Katsumi Takahashi, "Pl-diversity: Quantifying privacy of reconstruction methods for attribute estimation", In CSS, 2010.

When an attribute that an attacker is trying to estimate is called a target attribute V ^* , the distribution of attribute values other than all target attributes and the target attribute alone is known, and the target attribute value of the individual subject to attack is L-2 For an attacker who has a background knowledge that the probability is less than ε for the attribute value within the number, about the estimated probability of the target attribute value of the individual to be attacked,

It holds that P (c, L) -diversity when In sustain substitution disturbance, when Ω _Σ is the distribution of the target attribute population and Ω _Σ satisfies P (c, L) -diversity,

Then P (c ′, L) -diversity is satisfied.

[Re-randomized public key cryptography]
A public key cipher that can change the random number without changing the contents of the ciphertext is called a public key cipher that can be re-randomized. If it has homomorphism, it can be re-randomized. The parameter params is omitted because it is necessary for all algorithms other than Setup.

Setup (1 ^λ ): Security parameter 1 ^λ is input and parameter params is output.
・ KGen (): params is input, and a public / private key pair (pk, sk) is output.
• Enc (pk, m) pk and message m are input and ciphertext c is output.
-Dec (sk, c) sk and ciphertext c are input and m is output.
ReRand (pk, c) Using pk and c as inputs, re-randomized ciphertext c ′ is output.

As correctness, m = Dec (sk, ReRand (pk, Enc (pk, m))) and m = Dec (for any params ← Setup (1 ^λ ), any (pk, sk) ← KGen (params) sk, Enc (pk, m)) holds.

  Here, it is assumed that public key cryptography that can be re-randomized has IND-CPA security. That is, for Turing machine A that moves in arbitrary polynomial time,

Holds.

  Specifically, ciphers with homomorphism can be mentioned. ElGamal encryption and Paillier encryption.

[Name identification system, apparatus and method]
Hereinafter, an embodiment of a name identification system, apparatus, and method will be described with reference to the drawings. As shown in FIG. 1, the name identification system includes, for example, a 0th device, a first device,. Each of the 0th device, the 1st device,..., The n−1th device is a name identification device. The 0th device includes an encryption unit 2 and a decryption unit 5, for example. The first to n-2th devices include, for example, the maintenance replacement disturbance unit 1 and the encryption unit 2. The n-1th apparatus is provided with the maintenance replacement disturbance part 1, the encryption part 2, the disturbance part 3, and the rearrangement part 4, for example. Each part of the name collation apparatus performs the process of each step in FIG. 2 to realize the name collation method.

n as 1 or more predetermined integer, the 0th unit (n-1) th device each party P _0, · · ·, a P _{n-1. P 0, ···, P n-} 1 , respectively τ _0, ···, have τ _n-1. τ _i has A _i as an attribute such that A = ∪ _{i <n} A _i ,

Τ _i : R → V _i . Here, the fact that R is constant regardless of i means that an attribute with a certain ID exists and the attribute value is the same in any table. Note that it is assumed that P ₀ performs key generation for public key cryptography that can be re-randomized in advance, and the public key has been distributed.
At this time, an example of the name identification protocol is shown in FIG.

<Step S1>
Each of the first device to the (n−1) -th device performs the maintenance replacement disturbance on the attribute value of each attribute “a” of each record of its own table according to a predetermined parameter ρ _a (step S1). This process is performed by the maintenance replacement disturbing unit 1 provided in each of the first to n-1th devices. The attribute value after the maintenance replacement disturbance is output to the encryption unit 2.

  The processing in step S1 corresponds to “1:” to “6:” of the name identification protocol in FIG.

<Step S2>
Each of the 0th device to the (n-1) th device encrypts its own table by encrypting the attribute value after the maintenance replacement disturbance so that only the 0th device can decrypt it (step S2). This process is performed by the encryption unit 2 provided in each of the first device to the (n-1) th device. The encryption is performed using, for example, a public key in a public key cryptosystem that can be re-randomized by the 0th apparatus. The encrypted table is output to the (n-1) th apparatus.

  The processing in step S2 corresponds to “7:” to “9:” of the name identification protocol in FIG.

<Step S3>
The (n-1) th device names the tables encrypted by the n-1th device from the 0th device. This name-matched table is referred to as “name-matching table”.

Disturbance portion 3 of the n-1 device, as a set A ₀ of the attribute tables 0th device has a normal maintenance replacement in accordance with predetermined parameters [rho _a relative attribute values for each attribute A∈A ₀ name identification table Whether or not to maintain is determined in the same manner as the disturbance, and the attribute value determined to be maintained is re-encrypted so that only the 0th device can decrypt it, thereby disturbing the name identification table (step S3). When performing replacement, for example, a random number is generated, such as “14:” “15:” in the name identification protocol in FIG. 3, and the random number is encrypted so that only the 0th device can decrypt it. Perform replacement. The name identification table after the disturbance is output to the rearrangement unit 4.

  The processing in step S3 corresponds to the name identification protocol “10:” to “17:” in FIG.

<Step S4>
The rearrangement unit 4 of the n-1th apparatus creates the rearranged table by rearranging the records in the name identification table after the disturbance (step S4). For example, the rearrangement unit 4 shuffles records randomly. The post-reordering table is transmitted to the 0th device.

  The processing in step S4 corresponds to “18:” to “19:” of the name identification protocol in FIG.

<Step S5>
The decoding unit 5 of the 0th device decodes each attribute value in the post-reordering table (step S5). The decryption is performed using, for example, a secret key in the public key cryptosystem that can be re-randomized by the 0th apparatus.

  The process of step S5 corresponds to “20:” to “21:” of the name identification protocol in FIG.

In this way, by performing Pk-anonymization by maintaining replacement perturbation with encryption, privacy can be protected for the 0th device (P ₀ ) that is the main body to be restored.

Hereinafter, an example of setting the predetermined parameter ρ _a (maintenance probability ρ _a ) in the maintenance replacement disturbance will be described.

To prevent personal identification for P ₀ without background knowledge, for a∈A ₀ , k is a security parameter,

Ρ _a

And set. Also,

Ρ _a = 1.

To prevent personal identification for P ₀ with background knowledge, for a∈A, k is a security parameter,

Ρ _a

And set.

P with respect to an attribute A∈A\A ₀ to prevent attribute identification (c, L) - if that satisfies diversity, population distribution attributes _{a∈A\A 0} Ω Σ is P (c ', L)-When meeting diversity

And set. c and c ′ are predetermined real numbers of 0 or more. m is m = | A \ A ₀ |. That, m is the number of elements in the set A\A _0.

If you want to prevent both personal identification and attribute estimation, and extend to meet both identification risk and attribute estimation risk, keep Pk-anonymity and P (c, L) -diversity The substitution disturbance parameter ρ may be set. That is, ρ _a is calculated for each attribute a∈A, and the lowest ρ _a may be adopted.

[Program and recording medium]
The processes described in the name identification system, apparatus, and method are not only executed in chronological order according to the order of description, but may be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. .

  Further, when each process in the name identification device is realized by a computer, the processing contents of the functions that the name identification device or the model creation device should have are described by a program. Then, by executing this program on a computer, each process is realized on the computer.

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

  Each processing means may be configured by executing a predetermined program on a computer, or at least a part of these processing contents may be realized by hardware.

[Modification]
The process of step S1 by the maintenance replacement disturbing unit 1 in the first device to the (n-1) th device may not be performed. In this case, each of the 0th device to the (n−1) th device encrypts its own table by encrypting each attribute value of its own table so that only the 0th device can decrypt it (step S2). )
Needless to say, other modifications are possible without departing from the spirit of the present invention.

1 maintenance replacement disturbance unit 2 encryption unit 3 disturbance unit 4 rearrangement unit 5 decryption unit

Claims (8)

Public key cryptography that can be re-randomized by changing only the random number without changing the contents of the ciphertext so that only the 0th device can decrypt each attribute value of the table that n is a predetermined integer of 1 or more In the name collation system including the 0th device to the (n-1) th device including the encryption unit that encrypts the table that the device has by encrypting using the device,
The n-1 device uses a table obtained by identifying the tables encrypted by the n-1 device from the 0th device as a name identification table, and sets the attribute of the table of the 0th device as a set A ₀ of the name identification table. Whether or not to maintain the attribute value of each attribute a ∈ A ₀ according to a predetermined parameter ρ _{a in the} same manner as in the normal maintenance replacement disturbance is determined, and for the attribute value determined to be maintained, the 0th device By re- randomizing so that only can be decrypted, the name identification table is disturbed, and a random number is generated for an attribute value determined not to be maintained, and only the 0th device can decrypt the random number. A disturbance unit that performs replacement with the encrypted value, and a rearrangement unit that creates a rearranged table by rearranging the records of the name identification table after the disturbance,
The 0th device further includes a decoding unit that decodes each attribute value of the post-reordering table,
Name identification system. The name identification system of claim 1,
Said the first device (n-1) -th apparatus further comprises a maintenance replacement disturbance unit which performs maintenance substituted disturbance in accordance with a predetermined parameter [rho _a relative attribute values for each attribute a of each record in the table having its own, the encryption The unit encrypts the attribute value after maintaining replacement disturbance so that only the 0th device can decrypt the attribute value,
Name identification system. The name identification system according to claim 1 or 2,
When k is a security parameter, R is a set of records before anonymization, V _a is a set of attribute values that can be taken by the attribute a before anonymization, and the parameter ρ _a is a∈A ₀ Ρ _a defined by the following equation:

The parameter ρ _a is ρ _a = 1 if not a∈A ₀ ,
Name identification system. The name identification system according to claim 1 or 2,
k is a security parameter, R is a set of records before anonymization, Va is _a set of attribute values that can be taken by the attribute a before anonymization, and A is included in the 0th to n-1th devices as a set a of the attributes of table, the parameter [rho _a is a [rho _a is defined by the following formula,

Name identification system. The name identification system according to claim 1 or 2,
c, c ′ is a predetermined real number greater than or equal to 0, A is the attribute set A of the tables of the 0th device to the (n−1) th device, and m is the number of elements of the set A \ A ₀ parameter [rho _a is a [rho _a is defined by the following formula,

Name identification system. From the 0th device to the (n-1) th device, n is a predetermined integer of 1 or more, and only random numbers are used without changing the contents of the ciphertext so that only the 0th device can decrypt each attribute value of its own table. It includes an encryption unit that encrypts the table it has by encrypting it using public key cryptography that can be re-randomized
A table in which the tables encrypted from the 0th device to the n-1 device are identified is referred to as a name identification table, and each attribute a∈A ₀ of the name identification table is set as a set A ₀ of attributes of the table of the 0th device. It is determined whether or not to maintain the attribute value in the same manner as in the normal maintenance replacement disturbance according to a predetermined parameter ρ _a , and the attribute value determined to be maintained is reproduced so that only the 0th device can decode. performed disturbance of the name identification table by randomization, substituted for the non as determined attribute value kept generates a random number for the random number encrypted value to be decoded only the 0th device The name collation apparatus which is said n-1th apparatus further including the disturbance part which performs, and the rearrangement part which produces the table after a rearrangement by rearranging the record of the name collation table after the said disturbance. The ciphers of each of the 0th device to the (n-1) th device set the contents of the ciphertext so that only the 0th device can decrypt each attribute value of its own table, where n is a predetermined integer of 1 or more. A cryptographic step of encrypting the table that the device itself has by encrypting with public key cryptography that can be re-randomized to change only the random number instead of ;
The disturbing unit of the n-1 device defines a table in which the tables encrypted from the 0th device by the n-1 device are named as a name identification table, and sets the attribute A ₀ of the table of the 0th device as the above It is determined whether or not to maintain the attribute value of each attribute a∈A ₀ of the name identification table in the same manner as the normal maintenance replacement disturbance according to the predetermined parameter ρ _a , and the attribute value determined to be maintained is the above The name identification table is disturbed by re- randomizing it so that only the 0th device can decode it, and a random number is generated for the attribute value determined not to be maintained. A perturbation step that replaces with an encrypted value so that it can be decrypted;
A rearrangement step in which the rearrangement unit of the n-1 device creates a rearranged table by rearranging the records of the name identification table after the disturbance,
A decoding step in which the decoding unit of the 0th device decodes each attribute value of the post-reordering table;
Name identification method including. From the 0th device to the (n-1) th device, n is a predetermined integer of 1 or more, and only random numbers are used without changing the contents of the ciphertext so that only the 0th device can decrypt each attribute value of its own table. It includes an encryption unit that encrypts the table it has by encrypting it using public key cryptography that can be re-randomized
A table in which the tables encrypted from the 0th device to the n-1 device are identified is referred to as a name identification table, and each attribute a∈A ₀ of the name identification table is set as a set A ₀ of attributes of the table of the 0th device. It is determined whether or not to maintain the attribute value in the same manner as in the normal maintenance replacement disturbance according to a predetermined parameter ρ _a , and the attribute value determined to be maintained is reproduced so that only the 0th device can decode. performed disturbance of the name identification table by randomization, substituted for the non as determined attribute value kept generates a random number for the random number encrypted value to be decoded only the 0th device The encryption unit, the disturbance unit, and the rearrangement of the name collation device further including a disturbance unit that performs the sorting, and a rearrangement unit that creates the rearranged table by rearranging the records of the name identification table after the disturbance. Program for causing a computer to function as a.

Images