COMPUTATION APPARATUS, METHOD AND PROGRAM FOR THE SAME

Abstract

A computation apparatus, a method of the same, and a program which perform a secure computation using fixed-point arithmetic, and overflow is unlikely to occur and the occurrence of division by zero can be detected when an odds ratio is calculated. The computation apparatus includes an odds ratio computation unit for obtaining an odds ratio between a first group (a+b) and a second group (c+d) based on four plaintext values a, b, c, and d, by means of secure computation; a zero-division detection unit for determining, by means of secure computation, whether or not at least one of the plaintext values b and c is not zero, and detecting division by zero; and a selection unit for selecting the odds ratio if division by zero is not detected, by means of secure computation.

Claims

1-5. (canceled)

6. A computation apparatus comprising: processing circuitry configured to: execute an odds ratio computation processing in which the processing circuitry obtains an odds ratio between a first group (a+b) and a second group (c+d) based on four plaintext values a, b, c, and d, by means of secure computation; execute a zero-division detection processing in which the processing circuitry determines, by means of secure computation, whether or not at least one of the plaintext values b and c is not zero, and detects division by zero; and a selection processing in which the processing circuitry selects the odds ratio if division by zero is not detected, by means of secure computation, wherein in the odds ratio computation processing the processing circuitry obtains ciphertexts [[0′.sub.1]] and [[0′.sub.2]] of results o′.sub.1 and o′.sub.2 of calculating a/b and d/c, respectively, by means of secure computation, and thereafter obtains a ciphertext of a result o′ of calculating o′.sub.1×o′.sub.2.

7. A computation apparatus comprising: processing circuitry configured to: take ciphertexts [[a]], [[b]], [[c]], and [[d]] of plaintext values a, b, c, and d as input, and obtain ciphertexts [[o′.sub.1]] and [[o′.sub.2]] of results o′.sub.1 and o′.sub.2 of calculating a/b and d/c, respectively, by [[o′.sub.1]]←[[a]]/[[b]] and [[o′.sub.2]]←[[d]]/[[c]], by means of secure computation; take the ciphertexts [[o′.sub.1]] and [[o′.sub.2]] as input and obtain a ciphertext [[o′]] of a result o′ of computation of plaintext values o′.sub.1×o′.sub.2 by [[o′]]←[[o′.sub.1]]×[[o′.sub.2]], by means of secure computation; take the ciphertexts [[b]] and [[c]] as input and obtain ciphertexts [[f.sub.1]] and [[f.sub.2]] of truth values f.sub.1 and f.sub.2 with predicates b=?0 and c=?0, respectively, by [[f.sub.1]]←[[b]]=?[[0]] and [[f.sub.2]]←[[c]]=?[[0]], by means of secure computation; take the ciphertexts and as input and obtain a ciphertext [[f]] of a result f of calculating f.sub.1 Or f.sub.2 by [[f]]←Or([[f.sub.1]], [[f.sub.2]]), by means of secure computation; and take the ciphertexts [[f]] and [[o′]] as input and obtain a ciphertext [[o]] of o that satisfies $\begin{array}{cc}o=\{\begin{array}{c}\perp \mathrm{if}f=1\\ o^{\prime }\mathrm{otherwise}\end{array}& \left[\mathrm{Math}.4\right]\end{array}$ by [[o]]←If Else([[f]], [[⊥]], [[o′]]), by means of secure computation, wherein ⊥ indicates an invalid value.

8. A computation method, implemented by a computation apparatus that includes processing circuitry, comprising: an odds ratio computation step in which the processing circuitry obtains an odds ratio between a first group (a+b) and a second group (c+d) based on four plaintext values a, b, c, and d, by means of secure computation; a zero-division detection step in which the processing circuitry determines, by means of secure computation, whether or not at least one of the plaintext values b and c is not zero, and detects division by zero; and a selection step in which the processing circuitry selects the odds ratio if division by zero is not detected, by means of secure computation, wherein in the odds ratio computation step, the processing circuitry obtains ciphertexts [[o′.sub.1]] and [[o′.sub.2]] of results o′.sub.1 and o′.sub.2 of calculating a/b and d/c, respectively, by means of secure computation, and thereafter, obtains a ciphertext [[o′]] of a result o′ of calculating o′.sub.1×o′.sub.2.

9. A computation method, implemented by a computation apparatus that includes processing circuitry, comprising: a division step in which the processing circuitry takes ciphertexts [[a]], [[b]], [[c]], and [[d]] of plaintext values a, b, c, and d as input, and obtains ciphertexts [[o′.sub.1]] and [[o′.sub.2]] of results o′.sub.1 and o′.sub.2 of calculating a/b and d/c, respectively, by [[o′.sub.1]]←[[a]]/[[b]] and [[o′.sub.2]]←[[d]]/[[c]], by means of secure computation; a multiplication step in which the processing circuitry takes the ciphertexts [[o′.sub.1]] and [[o′.sub.2]] as input and obtains a ciphertext [[o′]] of a result o′ of computation of plaintext values o′.sub.1×o′.sub.2 by [[o′]]←[[o′.sub.1]]×[[o′.sub.2]], by means of secure computation; an equality judgment step in which the processing circuitry takes the ciphertexts [[b]] and [[c]] as input and obtains ciphertexts [[f.sub.1]] and [[f.sub.2]] of truth values f.sub.1 and f.sub.2 with predicates b=?0 and c=?0, respectively, by [[f.sub.1]]←[[b]]=?[[0]] and [[f.sub.2]]←[[c]]=?[[0]], by means of secure computation; a logical operation step in which the processing circuitry takes the ciphertexts [[f.sub.1]] and [[f.sub.2]] as input and obtains a ciphertext [[f]] of a result f of calculating f.sub.1 Or f.sub.2 by [[f]]←Or([[f.sub.1]], [[f.sub.2]]), by means of secure computation; and a selection step in which the processing circuitry takes the ciphertexts [[f]] and [[o′]] as input and obtains a ciphertext [[o]] of o that satisfies $\begin{array}{cc}o=\{\begin{array}{c}\perp \mathrm{if}f=1\\ o^{\prime }\mathrm{otherwise}\end{array}& \left[\mathrm{Math}.5\right]\end{array}$ by [[o]]←If Else([[f]], [[⊥]], [[o′]]), by means of secure computation, wherein ⊥ indicates an invalid value.

10. A non-transitory computer-readable recording medium having recorded thereon a program for causing a computer to function as the computation apparatus according to claim 6.

11. A non-transitory computer-readable recording medium having recorded thereon a program for causing a computer to function as the computation apparatus according to claim 7.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0017] FIG. 1 is a diagram showing an example of a 2×2 summary table.

[0018] FIG. 2 is a functional block diagram of a computation apparatus according to a first embodiment.

[0019] FIG. 3 is a diagram showing an example of a processing flow of the computation apparatus according to the first embodiment.

[0020] FIG. 4 is a diagram showing an example configuration of a computer to which the present method is applied.

DESCRIPTION OF EMBODIMENTS

[0021] Hereinafter, the embodiment of the present invention will be described. Note that in the diagrams used in the following description, constituent units with the same functions and steps in which the same processing is performed are assigned the same signs, and redundant description is omitted. In the following description, processing performed for each element unit of a vector or a matrix is assumed to be applied to all elements of that vector or matrix, unless otherwise noted.

First Embodiment

[0022] First, the points of the present embodiment will be described, and then the notation used in the present embodiment will be described.

Points of the Present Embodiment

[0023] In the present embodiment, the maximum value of an intermediate computation result is reduced from n.sup.2 to n by devising the computation method, thereby avoiding overflow. In addition, division by zero in the secure odds ratio computation is detected by effectively combining comparison, logic, and selection operations, and ⊥ is returned if division by zero occurs. Here, ⊥ indicates an invalid value.

[0024] <Encryption>

[0025] A value obtained by encrypting a in some way is called a ciphertext of a, and is denoted as [[a]]. Also, a is called a plaintext value of the ciphertext [[a]].

[0026] The following arithmetic operations, logical operations, equality judgments, and selections are performed by means of secure computation. Note that the method for encryption in secure computation may be any method. For example, any of the methods described in NPL 1 and 2, or the like, is used.

[0027] <Arithmetic Operations>

[0028] Each operation of addition, subtraction, multiplication, and division by means of secure computation takes ciphertexts [[a]] and [[b]] of a and b as input, and outputs ciphertexts [[c.sub.1]], [[c.sub.2]], [[c.sub.3]], and [[c.sub.4]] of the results c.sub.1, c.sub.2, c.sub.3, and c.sub.4 of calculating a+b, a−b, ab, and a/b, respectively. The execution of these operations is described as follows.

[[c.sub.1]]←Add([[a]],[[b]])

[[c.sub.2]]←Sub([[a]],[[b]])

[[c.sub.3]]←Mul([[a]],[[b]])

[[c.sub.4]]←Div([[a]],[[b]])

[0029] Note that, in the following, Add([[a]], [[b]]), Sub([[a]], [[b]]), Mul([[a]], [[b]]), and Div([[a]], [[b]]) are also denoted as [[a]]+[[b]], [[a]]-[[b]], [[a]]×[[b]], [[a]]/[[b]], respectively.

[0030] <Logical Operations>

[0031] The Or operation by means of secure computation takes the ciphertexts [[a]] and [[b]] of 1-bit values a and b as input, and outputs a ciphertext [[c]] of a result c of calculating a Or b. The execution of this operation is described as follows. [[c]]←Or([[a]], [[b]])

[0032] <Equality Judgment>

[0033] The operation of equality judgment takes the ciphertexts [[a]] and [[b]] of a and b as input, and outputs the ciphertext [[c]] of a truth value c of a predicate a=?b. The execution of this operation is described as follows. [[c]]←[[a]]=?[[b]]

[0034] <Selection>

[0035] The selection takes the ciphertexts [[c]], [[a]], and [[b]] of a truth value c∈{0,1} and a and b, and outputs a ciphertext [[d]] of d that satisfies

[00002]$\begin{array}{cc}d=\{\begin{array}{c}a\mathrm{if}c=1\\ b\mathrm{otherwise}\end{array}& \left[\mathrm{Math}.2\right]\end{array}$

[0036] The execution of this operation is described as follows.

[[d]]←If Else([[c]],[[a]],[[b]])

[0037] <Secure Summary Table Computation>

[0038] An encrypted summary table itself used as input for the secure odds ratio computation can also be calculated by means of secure computation. In the following, processing for reading an encrypted database [[D]] and returning the ciphertexts ([[a]], [[b]], [[c]], [[d]]) of a contingency table is denoted as ([[a]], [[b]], [[c]], [[d]])←Count([[D]]). There are several possible ways to realize Count ([[D]]), but for example, if n is known and it is assumed the format of the database takes two values of [[0]], [[1]] and has two attributes, subtotal portions (n.sub.1., n.sub.2., n..sub.1, n..sub.2) and a can be calculated by addition and constant multiplication. Then, all elements of the summary table can be calculated based on the relationship between the subtotals and each element.

First Embodiment

[0039] FIG. 2 is a functional block diagram of a computation apparatus according to the first embodiment, and FIG. 3 is a processing flow thereof.

[0040] The computation apparatus includes a division unit 110, a multiplication unit 120, an equality judgment unit 130, a logical operation unit 140, and a selection unit 150.

[0041] The computation apparatus receives input of the ciphertexts [[a]], [[b]], [[c]], and [[d]], obtains an odds ratio o by means of secure computation, and outputs the obtained odds ratio o or ⊥ indicating an invalid value. Note that the computation apparatus may calculate the ciphertexts [[a]], [[b]], [[c]], and [[d]] by calculating a pre-calculated summary table, or by performing secure summary table computation with the encrypted database [[D]] as input.

[0042] The computation apparatus is, for example, a special device configured by loading a special program into a known or dedicated computer that has a central processing unit (CPU), a main storage device (RAM: Random Access Memory), and so on. The computation apparatus executes each processing under the control of the central processing unit, for example. Data input to the computation apparatus and data obtained by each processing is, for example, stored in the main storage device, and the data stored in the main storage device is loaded to the central processing unit and used in other processing as necessary. Each processing unit of the computation apparatus may be constituted at least partially by hardware such as an integrated circuit. Each storage unit included in the computation apparatus may be constituted by, for example, a main storage device such as a RAM (Random Access Memory) or middleware such as a relational database or a key-value store. However, each storage unit does not necessarily need to be installed in the computer, but may alternatively be constituted by an auxiliary storage device constituted by an auxiliary storage device consisting of a hard disk, an optical disk, or a semiconductor memory device such as a flash memory (Flash Memory), and installed outside the computation apparatus.

[0043] Each unit will be described below.

[0044] <Division Unit 110>

[0045] The division unit 110 takes the ciphertexts [[a]], [[b]], [[c]], and [[d]] as input, obtains ciphertexts [[o′.sub.1]] and [[o′.sub.2]] of results o′.sub.1 and o′.sub.2 of calculating a/b and d/c using the following expressions (2) and (3) (S110), and outputs ciphertexts [[o′.sub.1]], [[o′.sub.2]].

[[o′.sub.1]]←[[a]]/[[b]]  (2)

[[o′.sub.2]]←[[d]]/[[c]]  (3)

[0046] <Multiplication Unit 120>

[0047] The multiplication unit 120 takes the ciphertext [[o′.sub.1]], [[o′.sub.2]] as input, obtains, using the following expression (4), a ciphertext [[o′]] of a result o′ of the computation of plaintext values o′.sub.1×o′.sub.2 (S120), and outputs the ciphertext [[o′]].

[[o′]]←[[o′.sub.1]]×[[o′.sub.2]]  (4)

[0048] In other words, the odds ratio o′ that is calculated based on a, b, c, and d in the 2×2 summary table is obtained by the expressions (2)-(4). In other words, the odds ratio between the first group (a+b) and the second group (c+d) are obtained based on the four plaintext values a, b, c, and d. Accordingly, the division unit 110 and the multiplication unit 120 are also collectively called an odds ratio computation unit 160, and processing performed thereby is S160.

[0049] <Equality Judgment Unit 130>

[0050] The equality judgment unit 130 takes the ciphertext [[b]] and [[c]] as input, obtains ciphertexts [[f.sub.1]] and [[f.sub.2]] of truth values f.sub.1 and f.sub.2 with predicates b=?0 and c=?0 by the following expression (S130), and outputs the ciphertexts [[f.sub.1]] and [[f.sub.2]].

[[f.sub.1]]←[[b]]=?[[0]]  (5)

[[f.sub.2]]←[[c]]=?[[0]]  (6)

[0051] <Logical Operation Unit 140>

[0052] The logical operation unit 140 takes the ciphertexts [[f.sub.1]] and [[f.sub.2]] as input, obtains a ciphertext [[f]] of a result f of calculating f.sub.1 Or f.sub.2 by the following expression (S140), and outputs the ciphertext [[f]].

[[f]]←Or([[f.sub.1]],[[f.sub.2]])  (7)

[0053] <Selection Unit 150>

[0054] The selection unit 150 takes the ciphertexts [[f]] and [[o′]] as input, obtains a ciphertext [[o]] of o that satisfies

[00003]$\begin{array}{cc}o=\{\begin{array}{c}\perp \mathrm{if}f=1\\ o^{\prime }\mathrm{otherwise}\end{array}& \left[\mathrm{Math}.3\right]\end{array}$

[0055] by the following equation (S150), and outputs the ciphertext [[o]].

[[o]]←If Else([[f]],[[⊥]],[[o′]])  (8)

[0056] That is to say, division by zero is detected by the expressions (5) to (7). Accordingly, the equality judgment unit 130 and the logical operation unit 140 are also collectively called a zero-division detection unit 170, and processing performed thereby is S170. By the expression (8), the selection unit 150 selects a ciphertext [[⊥]] of ⊥ indicating an invalid value if division by zero is detected, or selects a ratio ciphertext [[o′]] of the odds ratio o′ if division by zero is not detected, and outputs the selection result [[o]].

Effects

[0057] In the present embodiment, division by zero is detected by effectively combining comparison, logic, and selection operations as represented by the expressions (5) to (8), and replaces the computation result of (4) with ⊥ if division by zero is detected.

[0058] When the expression (1) is simply calculated, division and comparison operations can be done at a time by calculating ad and bc and thereafter performing division. In this method, however, overflow occurs when values to be handled are large, and a correct computation result cannot be obtained. In the present embodiment, the number of times of costly division increases compared with multiplication, but instead, the largest value during computation decreases from n.sup.2 to n as a result of calculating [[o′.sub.1]]←[[a]]/[[b]] and [[o′.sub.2]]←[[d]]/[[c]] and thereafter calculating the product [[o′]]←[[o′.sub.1]]×[[o′.sub.2]], and thus, large values can be handled while avoiding overflow.

[0059] In other words, when secure computation of the odds ratio using the expression (1) is performed by means of fixed-point arithmetic, it is possible to detect division by zero and distinguish it from the correct computation result even in secure computation in which the intermediate computation result is invisible. In addition, large input can also be dealt with by avoiding overflow.

[0060] <Other Modifications>

[0061] The present invention is not limited to the above embodiments and modifications. For example, various types of processing described above may be not only performed in time-series in accordance the description, but also performed in parallel or separately in accordance with the performance of the device that performs processing, or as required. In addition, the present invention may be modified, as appropriate, within the scope of the gist thereof.

[0062] <Program and Recording Medium>

[0063] The above-described processing can be implemented by causing a recording unit 2020 of a computer shown in FIG. 4 to load a program for executing the steps of the above-described method, and causing a control unit 2010, an input unit 2030, an output unit 2040, and so on, to operate.

[0064] The program that describes this processing content can be recorded in a computer-readable recording medium. The computer-readable recording medium may be of any kind, e.g., a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, or the like.

[0065] This program is distributed by, for example, selling, transferring, or lending a portable recording medium, such as a DVD or a CD-ROM, in which the program is recorded. Furthermore, a configuration is also possible in which this program is stored in a storage device in a server computer, and is distributed by transferring the program from the server computer to other computers via a network.

[0066] For example, first, a computer that executes such a program temporarily stores the program recorded in the portable recording medium or the program transferred from the server computer in a storage device of this computer. When executing the processing, the computer loads the program stored in its own storage medium, and executes processing in accordance with the loaded program. As another mode of executing this program, the computer may directly load the program from the portable recording medium and execute processing in accordance with the program, or may sequentially execute processing in accordance with a received program every time the program is transferred from the server computer to this computer. A configuration is also possible in which the above-described processing is executed through a so-called ASP (Application Service Provider)-type service that realizes processing functions only by giving instructions to execute the program and acquiring the results, without transferring the program to the computer. Note that the program in this mode may include information for use in processing performed by an electronic computer that is equivalent to a program (e.g., data that is not a direct command to the computer but has properties that define computer processing).

[0067] In this mode, the present device is configured by executing a predetermined program on a computer, but the content of this processing may be at least partially realized in a hardware manner.