Secure computation system, secure computation device, secure computation method, and program

Abstract

Fisher's exact test is efficiently computed through secure computation. It is assumed that a, b, c and d are frequencies of a 2×2 contingency table, [a], [b], [c] and [d] are secure texts of the respective frequencies a, b, c and d, and N is an upper bound satisfying a+b+c+dN. A reference frequency computation part computes a secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of a combination of reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0) which are integers satisfying a.sub.0+b.sub.0=a+b, c.sub.0+d.sub.0=c+d, a.sub.0+c.sub.0=a+c, and b.sub.0+d.sub.0=b+d. A number-of-patterns determination part determines integers h.sub.0 and h.sub.1 satisfying h.sub.0≤h.sub.1. A pattern computation part computes [ai]=[a.sub.0]+i, [b.sub.i]=[b.sub.0]−i, [c.sub.i]=[c.sub.0]−i and [d.sub.i]=[d.sub.0]+i for i=h.sub.0, . . . , h.sub.1, and obtains a set S={([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i])}.sub.i of secure texts of combinations of frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i).

Claims

1. A secure computation system comprising three or more secure computation devices, wherein it is assumed that a, b, c and d are non-negative integers, a is a frequency on a first row and a first column of a 2×2 contingency table, b is a frequency on the first row and a second column of the contingency table, c is a frequency on a second row and the first column of the contingency table, d is a frequency on the second row and the second column of the contingency table, [a], [b], [c] and [d] are secure texts of the respective frequencies a, b, c and d, and N is an upper bound satisfying a+b+c+d≤N, each secure computation device comprises circuitry configured to: receive, over a network, an input of the secure texts ([a], [b], [c], [d]), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices; compute a secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of a combination of reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0) which are integers satisfying a.sub.0+b.sub.0=a+b, c.sub.0+d.sub.0=c+d, a.sub.0+c.sub.0=a+c, and b.sub.0+d.sub.0=b+d; determine integers h.sub.0 and h.sub.1 satisfying h.sub.0≤h.sub.1; and compute [a.sub.i]=[a.sub.0]+i, [b.sub.i]=[b.sub.0]−i, [c.sub.i]=[c.sub.0]−i and [d.sub.i]=[d.sub.0]+i for i=h.sub.0, . . . , h.sub.1, and obtain a set S={([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i])}.sub.i of secure texts of combinations of frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i).

2. The secure computation system according to claim 1, wherein the circuitry computes [a.sub.0]=0, [b.sub.0]=[b]+[a], [c.sub.0]=[c]+[a] and [d.sub.0]=[d]−[a], obtains the secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]), and determines h.sub.0=0, and h.sub.1=N.

3. The secure computation system according to claim 1, wherein min(•) represents a minimum value among arguments •, and floor(•) represents a maximum integer equal to or less than a value •, the circuitry computes [e]=min([a], [d]), computes [a.sub.0]=[a]−[e], [b.sub.0]=[b]+[e], [c.sub.0]=[c]+[e] and [d.sub.0]=[d]−[e], obtains the secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]), and determines that h.sub.0=0, h.sub.1=floor(N/2).

4. The secure computation system according to any one of claims 1 to 3, wherein the contingency table is genome information obtained by classifying and counting according to presence or absence of mutation and presence or absence of an onset of a disease.

5. A secure computation device configured to be implemented in a secure computation system comprising three or more secure computation devices, wherein it is assumed that a, b, c and d are non-negative integers, a is a frequency on a first row and a first column of a 2×2 contingency table, b is a frequency on the first row and a second column of the contingency table, c is a frequency on a second row and the first column of the contingency table, d is a frequency on the second row and the second column of the contingency table, [a], [b], [c] and [d] are secure texts of the respective frequencies a, b, c and d, and N is an upper bound satisfying a+b+c+d≤N, the secure computation device comprises circuitry configured to: receive, over a network, an input of the secure texts ([a], [b], [c], [d]), wherein the original respective frequencies a, b, c and d are concealed from the secret computation devices in the secure computation system; compute a secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of a combination of reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0) which are integers satisfying a.sub.0, b.sub.0=a+b, c.sub.0+d.sub.0=c+d, a.sub.0+c.sub.0=a+c, and b.sub.0+d.sub.0=b+d; determine integers h.sub.0 and h.sub.1 satisfying h.sub.0≤h.sub.1; and compute [a.sub.i]=[a.sub.0]+i, [b.sub.i]=[b.sub.0]−i, [c.sub.i]=[c.sub.0]−i and [d.sub.i]=[d.sub.0]+i for i=h.sub.0, . . . , h.sub.1, and obtain a set S={([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i])}.sub.i of secure texts of combinations of frequencies (a.sub.i, b.sub.1, c.sub.i, d.sub.i).

6. A secure computation method implemented in a secure computation system comprising three or more secure computation devices, wherein it is assumed that a, b, c and d are non-negative integers, a is a frequency on a first row and a first column of a 2×2 contingency table, b is a frequency on the first row and a second column of the contingency table, c is a frequency on a second row and the first column of the contingency table, d is a frequency on the second row and the second column of the contingency table, [a], [b], [c] and [d] are secure texts of the respective frequencies a, b, c and d, and N is an upper bound satisfying a+b+c+d≤N, the secure computation method comprising by circuitry of each secure computation device: receiving, over a network, an input of the secure texts ([a], [b], [c], [d]), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices; computing a secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of a combination of reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0) which are integers satisfying a.sub.0+b.sub.0=a+b, c.sub.0+d.sub.0=c+d, a.sub.0+c.sub.0=a+c, and b.sub.0+d.sub.0=b+d, determining integers h.sub.0 and h.sub.1 satisfying h.sub.0≤h.sub.1 by the circuitry of the secure computation device, and computing [a.sub.i]=[a.sub.0]+i, [b.sub.i]=[b.sub.0]−i, [c.sub.0]=[c.sub.0]−i and [d.sub.i]=[d.sub.0]+i for i=h.sub.0, . . . , h.sub.1, and obtaining a set S={([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i])}.sub.i of secure texts of combinations of frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i) by the circuitry of the secure computation device.

7. A non-transitory computer readable medium including computer executable instructions that make a secure computation device perform a method, the secure computation device being configured to be implemented in a secure computation system comprising three or more secure computation devices, wherein it is assumed that a, b, c and d are non-negative integers, a is a frequency on a first row and a first column of a 2×2 contingency table, b is a frequency on the first row and a second column of the contingency table, c is a frequency on a second row and the first column of the contingency table, d is a frequency on the second row and the second column of the contingency table, [a], [b], [c] and [d] are secure texts of the respective frequencies a, b, c and d, and N is an upper bound satisfying a+b+c+d<N, the method comprising: receiving, over a network, an input of the secure texts ([a], [b], [c], [d]), wherein the original respective frequencies a, b, c and d are concealed from the secret computation devices in the secure computation system; computing a secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of a combination of reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0) which are integers satisfying a.sub.0+b.sub.0=a+b, c.sub.0+d.sub.0=c+d, a.sub.0+c.sub.0=a+c, and b.sub.0+d.sub.0=b+d, determining integers h.sub.0 and h.sub.1 satisfying h.sub.0≤h.sub.1; and computing [a.sub.i]=[a.sub.0]+i, [b.sub.i]=[b.sub.0]−i, [c.sub.i]=[c.sub.0]−i and [d.sub.i]=[d.sub.0]+i for i=h.sub.0, . . . , h.sub.1, and obtaining a set S={([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i])}.sub.i of secure texts of combinations of frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram exemplifying a functional configuration of a secure computation system;

(2) FIG. 2 is a diagram exemplifying a functional configuration of a secure computation device; and

(3) FIG. 3 is a diagram exemplifying processing procedures of a secure computation method.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(4) Prior to the description of embodiments, the notation scheme in this Description is described.

(5) <Notation>

(6) A value secured by applying encryption or secret sharing to a certain value “a” is called the secure text of “a” and is represented as [a]. Meanwhile, “a” is called the plain text of [a]. In a case where the securing is secret sharing, a set of the secret sharing fragments held by the individual parties according to [a] is referred to.

(7) Hereinafter, embodiments of the present invention are described in detail. In the diagrams, configuration parts having the same functions are assigned the same numerals, and redundant description thereof is omitted.

First Embodiment

(8) A secure computation system of a first embodiment comprises n (≥3) secure computation devices 1.sub.1, . . . , 1.sub.n, as exemplified in FIG. 1. In this embodiment, the secure computation devices 1.sub.1, . . . , 1.sub.n are each connected to a communication network 2. The communication network 2 is a communication network that is of a circuit switching scheme or a packet switching scheme and is configured to allow the secure computation devices 1.sub.1, . . . , 1.sub.n to communicate with each other. For example, the Internet, a LAN (Local Area Network), a WAN (Wide Area Network) or the like may be used. Each device is not necessarily capable of communicating online via the communication network 2. For example, it may be configured such that information to be input into the secure computation devices 1.sub.i (i∈{1, . . . , n}) may be stored in a portable recording medium, such as magnetic tape or a USB memory, and input may be performed offline from the portable recording medium.

(9) As exemplified in FIG. 2, the secure computation device 1 includes an input part 11, a reference frequency computation part 12, a number-of-patterns determination part 13, a pattern computation part 14, and an output part 15. The secure computation device 1 performs the process of each step exemplified in FIG. 3, thereby achieving a secure computation method of the first embodiment.

(10) The secure computation device 1 is, for example, a special device configured to include a publicly known or dedicated computer which includes a central processing unit (CPU) and a main memory (RAM: Random Access Memory) and the like and into which a special program has been read. The secure computation device 1 executes each process under control by the central processing unit, for example. Data input into the secure computation device 1 and data obtained by each process are stored in the main memory, for example. The data stored in the main memory is read into the central processing unit as required, and is used for another process. At least some of the processing parts of the secure computation device 1 may be configured by hardware, such as an integrated circuit.

(11) Referring to FIG. 3, the processing procedures of the secure computation method of the first embodiment are described.

(12) In step S11, a secure text ([a], [b], [c], [d]) of a combination of frequencies (a, b, c, d) in a 2×2 contingency table, and an upper bound N that satisfies a+b+c+d≤T are input into the input part 11. Here, the 2×2 contingency table is defined by the following formulae, and a, b, c and d are non-negative integers.

(13) TABLE-US-00002 Without Subtotal due With event 1 event 1 to event 2 With event 2 a b n.sub.1• Without event 2 c d n.sub.2• Subtotal due to n.sub.•1 n.sub.•2 n event 1

(14) In step S12, the reference frequency computation part 12 uses the secure text ([a], [b], [c], [d]) of the combination of the frequencies (a, b, c, d) to compute a secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of a combination of integers (a.sub.0, b.sub.0, c.sub.0, d.sub.0) satisfying the following equations. Hereinafter, a.sub.0, b.sub.0, c.sub.0 and d.sub.0 are called reference frequencies
a.sub.0+b.sub.0=a+b,
c.sub.0±d.sub.0=c+d,
a.sub.0+c.sub.0=a+c,
b.sub.0+d.sub.0=b+d

(15) For example, the reference frequency computation part 12 may compute the following equations to obtain the secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of the combination of the reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0).
[a.sub.0]=0,
[b.sub.0]=[b]+[a],
[c.sub.0]=[c]+[a],
[d.sub.0]=[d]−[a]

(16) In step S13, the number-of-patterns determination part 13 determines integers h.sub.0 and h.sub.1 that satisfy h.sub.0≤h.sub.1. Here, it is determined such that h.sub.0=0, and h.sub.1=N, for example.

(17) In step S14, the pattern computation part 14 computes the following equations for each integer i ranging from h.sub.0 to h.sub.1, inclusive, to obtain the secure text ([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i]) of the combination of frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i).
[a.sub.i]=[a.sub.0]+i,
[b.sub.i]=[b.sub.0]−i,
[c.sub.i]=[c.sub.0]−i,
[d.sub.i]=[d.sub.0]+i

(18) In step S15, a set S={([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i])}.sub.i=h0, . . . , h1 of secure texts of the combinations of (h.sub.1−h.sub.0+1) frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i) is output from the output part 15.

(19) The set S is a set where only one j∈{h.sub.0, . . . , h.sub.1} resides that satisfies a′=a.sub.j, b′=b.sub.j, c′=c.sub.j and d′=d.sub.j for every combination of integers (a′, b′, c′, d′) satisfying a′≥0, b′≥0, c′≥0, d′≥0, a′+b′=a+b, c′+d′=c+d, a′+c′=a+c and b′+d′=b+d. That is, the set mutually exclusively includes all combinations of non-negative integers with values varying so as not to change the subtotals in the contingency table, for given a, b, c and d. Here, the set S may include combinations of integers (that may include negative integers) with each subtotal being the same in the contingency table.

(20) According to the secure computation technology of the first embodiment, the number of secure texts of the combinations of frequencies included in the output set S is determined by the disclosed value N. Consequently, the given frequencies a, b, c and d cannot be estimated. Accordingly, the combinations of frequencies which are computation targets of the Fisher's exact test can be enumerated, with the input being kept secret.

Second Embodiment

(21) Referring to FIG. 3, the processing procedures of the secure computation method of a second embodiment are described. Hereinafter, differences from the first embodiment described above are mainly described.

(22) In step S12, the reference frequency computation part 12 computes [e]=min([a], [d]). Here min(•) is a function of outputting the minimum value among the arguments. That is, [a] and [d] are compared with each other with the values being kept secret, and secure text of the smaller value is regarded as [e]. Subsequently, the reference frequency computation part 12 computes the following equations to obtain the secure text ([a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of the combination of the reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0).
[a.sub.0]=[a]−[e],
[b.sub.0]=[b]+[e],
[c.sub.0]=[c]+[e],
[d.sub.0]=[d]−[e]

(23) In step S13, the number-of-patterns determination part 13 computes h.sub.0=0 and h.sub.1=floor(N/2) to determine the integers h.sub.0 and h.sub.1. Here, floor(•) is a floor function for outputting the maximum integer equal to or less than •. That is, h.sub.1 can be represented by the following equation.

(24) $h_1=.Math.\frac{N}{2}.Math.$

(25) In step S14, the pattern computation part 14 uses the secure text [a.sub.0], [b.sub.0], [c.sub.0], [d.sub.0]) of the combination of the reference frequencies (a.sub.0, b.sub.0, c.sub.0, d.sub.0) and the integers h.sub.0 and h.sub.1 obtained as described above to obtain the secure text ([a.sub.i], [b.sub.i], [c.sub.i], [d.sub.i]) of the combination of frequencies (a.sub.i, b.sub.i, c.sub.i, d.sub.i), as with the first embodiment.

(26) According to the secure computation technology of the second embodiment, the number of secure texts of the combinations of frequencies included in the output set S is determined by the disclosed value N, as with the first embodiment. Consequently, the given frequencies a, b, c and d cannot be estimated. In comparison with the first embodiment, the number of secure texts of the combination of the frequencies included in the set S decreases. Consequently, Fisher's exact test can be more efficiently computed.

(27) According to the configuration as described above, the secure computation technology of the present invention can enumerate all the combinations of frequencies which are to be computed, without disclosing the number of combinations of the frequencies (a, b, c, d) which are to be computed, and can efficiently compute Fisher's exact test through secure computation without disclosing the input information.

(28) The embodiments of the present invention have thus been described above. However, the specific configuration is not limited to that in these embodiments. Even if the design is appropriately changed in a range without departing from the spirit of the present invention, it is a matter of course that the configuration is included in the present invention. The various processes described in the embodiments can be executed in a time-series manner according to the order of the description. Alternatively, such execution may be performed in parallel or individually, in conformity with the processing capability of the device that executes the processes, or as required.

(29) [Program and Recording Medium]

(30) In the cases where the various processing functions in each device described in the embodiments are implemented with a computer, the processing content of the functions that each device should have is described as a program. The program is executed by the computer, thereby achieving the various processing functions in each device described above on the computer.

(31) The program that describes the processing content can be preliminarily recorded in a computer-readable recording medium. The computer-readable recording medium may be, for example, any computer-readable recording medium, such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory.

(32) The program is distributed by, for example, selling, transferring, or lending a portable recording medium, such as DVD or CD-ROM, where the program is recorded. Alternatively, a configuration may be adopted where the program may be preliminarily stored in a storing device of a server computer, and the program may be transferred from the server computer to another computer via a network, thereby distributing the program.

(33) For example, the computer for executing such a program, first, stores the program recorded in a portable recording medium or transferred from a server computer, temporarily in its storing device. At the time of executing the process, the computer reads the program recorded in its recording medium, and executes the processes according to the read program. According to another execution mode of this program, the computer may directly read the program from the portable recording medium, and execute the processes according to the program. Further alternatively, every time the program is transferred to the computer from the server computer, the computer may successively execute the process according to the received program. Another configuration may be adopted that executes the processes described above through a service of what is called an ASP (Application Service Provider) type according to which the program is not transferred from the server computer to the computer concerned, and the processing function is achieved only by an execution instruction therefor and acquisition of the result. The program according to the embodiments include information that is provided for the processes by the computer and conforms to the program (data and the like that are not direct instructions to the computer but have characteristics defining the processes of the computer).

(34) According to the embodiments, this device is thus configured by executing a predetermined program on the computer. Alternatively, at least a part of the processing content may be achieved as hardware.

INDUSTRIAL APPLICABILITY

(35) As is obvious from the result of application to the genome-wide association study described above, the secure computation technology of the present invention is applicable to execution of Fisher's exact test through secure computation with information on an aggregate table being kept secret, in analysis using Fisher's exact test, for example, genome-wide association study, genome analysis, clinical research, social investigation, academic research, analysis of examination results, marketing research, statistical computation, medical information analysis, customer information analysis, and sales analysis.