Bit decomposition secure computation apparatus, bit combining secure computation apparatus, method and program

Abstract

The present invention provides a bit decomposition secure computation system comprising: a share value storage apparatus to store share values obtained by applying (2, 3) type RSS using modulo of power of 2 arithmetic; a decomposed share value storage apparatus to store a sequence of share values obtained by applying (2, 3) type RSS using modulo 2 arithmetic; and a bit decomposition secure computation apparatus that, with respect to sharing of a value w, r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n, where {circumflex over ( )} is a power operator and n is a preset positive integer, being used as share information by the (2, 3) type RSS stored in the share value storage apparatus, includes: an addition sharing unit that sums two values out of r1, r2 and r3 by modulo 2{circumflex over ( )}n, generates and distributes a share value of the (2, 3) type RSS with respect to the sum; and a full adder secure computation unit that executes addition processing of the value generated by the addition sharing unit and a value not used by the addition sharing unit, for each digit, by using secure computation of a full adder, and stores the result in the decomposed share value storage apparatus.

Claims

1. A bit decomposition secure computing system comprising: a share value storage apparatus to store share values obtained by applying (2, 3) type RSS (Replication type Secret Sharing) using modulo of power of 2 arithmetic; a decomposed share value storage apparatus to store a sequence of share values obtained by applying (2, 3) type RSS using modulo 2 arithmetic; and a bit decomposition secure computation apparatus including: a processor; and a memory storing a program executable by the processor, wherein the processor is configured to perform with respect to sharing of a value w, r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n, where mod is a modulo operator, {circumflex over ( )}is a power operator and n is a preset positive integer, being used as share information by the (2, 3) type RSS stored in the share value storage apparatus, an addition sharing process that sums two values out of r1, r2 and r3 by modulo 2{circumflex over ( )}n arithmetic, generates and distributes a share value with respect to the sum by the (2, 3) type RSS; and a full adder secure computation process that executes addition processing of the value generated by the addition sharing process and a value not used by the addition sharing process, for each digit, by using secure computation of a full adder, and stores the result in the decomposed share value storage apparatus.

2. The bit decomposition secure computing system according to claim 1, wherein the processor in the bit decomposition secure computation apparatus is configured to perform a partial share information extraction process that, using one index out of three values constituting share information by the (2, 3) type RSS, as input, reads the value stored in the share value storage apparatus, and generates share information obtained by setting values to zero except for one of the three values constituting the share information by the (2, 3) type RSS, wherein the full adder secure computation process performs addition processing using secure computation of a full adder on the share information by the (2, 3) type RSS generated and distributed by the addition sharing process and the share information by the (2, 3) type RSS generated by the partial share information extraction process, and stores the value obtained by combining the share information of the computation result, for each bit, in the decomposed share value storage apparatus.

3. A bit decomposition secure computation system comprising: a share value storage apparatus to store share values obtained by applying (2, 3) type RSS (Replication type Secret Sharing) using modulo of power of 2 arithmetic; a decomposed share value storage apparatus to store a sequence of share values obtained by applying (2, 3) type RSS using modulo 2 arithmetic; and a bit decomposition secure computation apparatus including: a processor; and a memory storing a program executable by the processor, wherein the processor is configured to perform with respect to sharing of a value w, r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n, where mod is a modulo operator, {circumflex over ( )}n is a power operator and n is a preset positive integer, being used as share information by the (2, 3) type RSS stored in the share value storage apparatus, a full adder secure computation process that performs secure computation of r12=r1+r2 mod 2{circumflex over ( )}n and secure computation of r123=r12+r3 mod 2{circumflex over ( )}n, for each digit, by using secure computation of a full adder, and stores the computation result in the decomposed share value storage apparatus.

4. The bit decomposition secure computing system according to claim 3, wherein the processor in the bit decomposition secure computation apparatus is configured to perform a partial share information extraction process that, using one index out of three values constituting share information by the (2, 3) type RSS, as input, reads the value stored in the share value storage apparatus, and generates share information obtained by setting values to zero except for one of the three values constituting the share information by the (2, 3) type RSS, wherein the full adder secure computation process, using 3 sets of share information by the (2, 3) type RSS generated by the partial share information extraction process, including r_i, r_j, r_k, where i, j and k being different to each other and selected from 1 to 3, performs secure computation of r_ij=r_i+r_j mod 2{circumflex over ( )}n, and secure computation of r_ij+r_k mod 2{circumflex over ( )}n, by secure computation of a full adder, from low order bit, and stores a sequence of the computation result, for each bit in the decomposed share value storage apparatus.

5. A bit combining secure computing system comprising: a share value storage apparatus to store share values obtained by applying (2, 3) type RSS (Replication type Secret Sharing) using modulo of power of 2 arithmetic; a decomposed share value storage apparatus to store a sequence of share values obtained by applying (2, 3) type RSS using modulo 2 arithmetic; and a bit combining secure computation apparatus including: a processor; and a memory storing a program executable by the processor, wherein the processor is configured to perform with respect to sharing of a value w_i, r_{1, i}, r_{2, i}, r_{3, i} satisfying w_i=r {1, i}+r {2, i}+r_{3, i} mod 2, for i=1 to n, where w_i, r_{1, i}, r_{2, i}, and r_{3, i} indicate respectively an i-th digit bit of w, r1, r2, and r3, and mod is a modulo operator, being used as a sequence of n items of share information by the (2, 3) type RSS stored in the decomposed share value storage apparatus, a full adder secure computation process that performs secure computation of r12=r_{1, n}∥ . . . ∥r_{1, 1}+r_{2, n}∥ . . . ∥r_{2, 1} mod 2{circumflex over ( )}n, where a symbol ∥ is a concatenation operator, {circumflex over ( )} is a power operator and n is a preset positive integer, and performs secure computation of r123=r12+r_{3, n}∥ . . . ∥r_{3, 1} mod 2{circumflex over ( )}n, for each digit, by using secure computation of a full adder, and stores the computation result in the share value storage apparatus.

6. The bit combining secure computing system according to claim 5, wherein the processor in the bit combining secure computation apparatus is configured to perform a partial share information extraction process that, using one index out of three values constituting share information by the (2, 3) type RSS, as input, reads the value stored in the share value storage apparatus, and generates share information obtained by setting values to zero except for one of the three values constituting the share information by the (2, 3) type RSS.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a diagram illustrating an arrangement of a first example embodiment.

(2) FIG. 2 is a flowchart illustrating an operation of the first example embodiment of the present invention.

(3) FIG. 3 is a diagram illustrating an arrangement of a second example embodiment.

(4) FIG. 4 is a flowchart illustrating an operation of the second example embodiment of the present invention.

(5) FIG. 5 is a diagram illustrating an arrangement of a third example embodiment.

(6) FIG. 6 is a flowchart illustrating an operation of the third example embodiment of the present invention.

(7) FIG. 7 is a diagram illustrating an arrangement of a fourth example embodiment of the present invention.

DETAILED DESCRIPTION

(8) Example embodiments will be described with reference to drawings. According to the method of the above described NPL 2, sharing of r3 is performed in the above described Procedure 1. A method for executing this processing without communication will be described.

(9) Suppose that sharing of a value is performed by using r1, r2, and r3 satisfying r=r1+r2+r3 mod p as shares.

(10) When generating shares related to ri (i=1, 2, 3) satisfying r=r1+r2+r3 mod p, the value obtained by setting all the values to zero other than a portion relating ri of share information of r=r1+r2+r3 mod p is the share information of ri.

(11) Suppose that the apparatus 1 retains (r2, r3), the apparatus 2 retains (r3, r1), and the apparatus 3 retains (r1, r2).

(12) For example, if all other than a portion relating to r1 are set to zero, the apparatus 1 will possess (0, 0), the apparatus 2 will possess (0, r1), and the apparatus 3 will possess (r1, 0), which can be made share information of r1.

(13) The fact that the apparatuses 2 and 3 retain r1 itself has no influence on confidentiality. This is because they are values that can be grasped originally. Similarly, for r2 and r3, the share information can be obtained without communicating among apparatuses.

(14) The reason that s is added in the above described Procedure 3, i.e., r12+r3+s mod 2{circumflex over ( )}n, according to the method according to NPL 2, is to obtain r12+r3 mod p, by the secret computation of mod 2{circumflex over ( )}n.

(15) In the case of s=1, if r12+r3=r′+p, where p=2{circumflex over ( )}n−1, then the following holds:
r12+r3+s mod 2{circumflex over ( )}n=r′+p+1 mod 2{circumflex over ( )}n=r′+2{circumflex over ( )}n mod 2{circumflex over ( )}n=r′ mod 2{circumflex over ( )}n.

(16) In the case of s=0, if it is assumed that r12+r3=r′, then r12+r3+s mod 2{circumflex over ( )}n=r′ mod 2{circumflex over ( )}n.

(17) From above, irrespective of the value of s, the computation result of the above described Procedure 3 is r12+r3 mod 2{circumflex over ( )}n.

(18) However, if 2 n is used as p, the processing (the above described Procedure 2) that is executed when r12+r3 exceeds 2{circumflex over ( )}n is unnecessary.

(19) <Modes>

(20) The following describes the bit decomposition method with the above described modification added as one of modes of the present invention.

(21) <Procedure 1>

(22) Execute sharing of r12=r1+r2 mod 2{circumflex over ( )}n.

(23) <Procedure 2>

(24) Generate share of r3 on each apparatus.

(25) <Procedure 3>

(26) Execute secret computation of a full adder for each bit from a lower digit to compute r12+r3+s mod 2{circumflex over ( )}n.

(27) The following evaluates a communication amount of the above processing.

(28) Let r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n be randomly selected and be stored as follows.

(29) (r1, r2) is stored as a share value of w in the apparatus 1.

(30) (r2, r3) is stored as a share value of w in the apparatus 2.

(31) (r3, r1) is stored as a share value of w in the apparatus 3.

(32) <Communication Amount of Procedure 1>

(33) Distribution of r1+r2 is performed by the apparatus 1. First, the apparatus 1 computes r12=r1+r2 mod 2{circumflex over ( )}n and randomly selects r12A and r12B satisfying r12A+r12B=r12 mod 2{circumflex over ( )}n.

(34) Next, the apparatus 1 sends r12A and 12B to the apparatus 2 and the apparatus 3, respectively.

(35) At this time, the apparatus 1 obtains (r12B, r12A) as a share value of r12,

(36) the apparatus 2 obtains (r12A, 0) as a share value of r12, and

(37) the apparatus 3 obtains (0, r12B) as a share value of r12.

(38) In this process, 2n bit communication is performed.

(39) <Communication Amount of Procedure 2>

(40) As described above, share information of r3 can be generated without communication.

(41) <Communication Amount of Procedure 3>

(42) The secure computation of an full adder requires one AND operation to calculate carry of each digit. Therefore, in the case of addition of n digits, communication of 3*(n−1) bits is required.

(43) As a result, it can be seen that the bit decomposition can be calculated with the communication amount of 5n−3 bits. The following describes an example for explaining how to divide the computation result into bit units by processing of an adder.

(44) The computation process of decomposition with be described for p=8, r=6 (110 in binary representation), r1=3 (011 in binary representation), r2=2 (010 in binary representation), r3=1 (001 in binary representation).

(45) Let j-th digit of r_i from a lowest digit be ri_j, j-th digit of r1r2 mod 8 be r12_j, and j-th digit of r1+r2+r3 mod 8 be r123_j.

(46) Next, a procedure for computing
r12+r3 mod 8=5+1 mod 8=6
from the lowest digit will be described.
<First Digit>

(47) Computation of the first digit is as follows:
r123_1=r12_1 XOR r3_1=0 XOR 1 XOR 1=0,

(48) where XOR is a bitwise exclusive OR.

(49) Carry with respect to the computation of the first digit is as follows:
c1=r12_1 AND r3_1=1 AND 1=1
(In the first digit, there is no carry (carry) from a lower digit.)
<Second Digit>

(50) Computation of the second digit is as follows:
r123_2=r12_2 XOR r3_2 XOR c1=0 XOR 0 XOR 1=1

(51) Carry with respect to the computation of the second digit is as follows:
c2=c1 XOR (1 XOR r12_2 XOR r3_2) AND (r3_2 XOR c1)=1 XOR (1 XOR 0 XOR 0) AND (0 XOR 1)=0
<Third Digit>

(52) Computation of the third digit is as follows:
r123_3=r12_3 XOR r2_3 XOR c2=1 XOR 0 XOR 0=1

(53) As described above, it is possible to compute the value obtained by decomposing each digit bit by bit, with one AND processing, as with 123_1=0, r123_2=1, and r123_3=1. This process can be executed by secure computation. The result of the secure computation is a share value of the value obtained by decomposition for each bit.

(54) In the above case, as (2, 3) threshold type RSS,

(55) the apparatus 1 holds (r1, r2),

(56) the apparatus 2 holds (r2, r3), and

(57) the apparatus 3 holds (r3, r1), with the value w given as follows:
w=r1+r2+r3 mod p.

(58) However, the present invention is applicable as long as it is a (2, 3) threshold type RSS that holds information corresponding to two different values among three values of r1, r2, and r3. For example, the apparatus 2 may hold (r2+r3, r3) instead of (r2, r3), or even a method can me also implemented in which the apparatus 2 holds (r2−r3, r2+r3), and so forth, as long as a secure computation is equipped with addition, multiplication and constant.

(59) Alternatively, at first, r12=r1+r2 mod 2{circumflex over ( )}n is calculated by secure computation, and then operation on r12+r3 may be executed by secure computation a full adder. When using this method, the communication amount for calculating r12 is 3n bits, which is rather inefficient as compared with a case where the apparatus 1 distributes, but the total communication amount is 6n−3 bits.

(60) When computation of r1+r2 is performed by secure computation of a full adder, there is no need to perform computation for a carry generated from the most significant digit, so computation on r12 can be executed by a communication amount of 3 n−3 bit. In this case, it is possible to execute bit decomposition with the communication amount of 6n−6 bits.

(61) These variations are also more efficient than the method according to NPL 2.

(62) Also, if both processing (r12=r1+r2 mod 2{circumflex over ( )}n and r12+r3 mod 2{circumflex over ( )}n) are to be executed using secure computation of a full adder, it is possible to use a mechanism for giving tolerance against fraud on the secure computation method using (2, 3) type RSS as described in NPL 3.

(63) Furthermore, it is also possible to create share information for a combined value from bit decomposed share information. Carry computation for each carry from a low order digit to a high order digit is executed by secure computation and when carry computation for the entire digits is finished, the secure computation result of each digit are combined.

(64) In this method, since there is no subject (party) holding information equivalent to r1+r2 mod 2{circumflex over ( )}n, both r12=r1+r2 mod 2{circumflex over ( )}n, and r12+r3 mod 2{circumflex over ( )}n are computed by secure computation of a full adder.

(65) When computation of the full adder is executed sequentially from a lower digit, n−1 AND operations are generated. As a result, the number of times of communication is n−1. In order to reduce this number, a carry save adder may be used, in which the number of AND operations increases but a depth of the circuit can be made shallow.

EXAMPLE EMBODIMENTS

(66) Configuration and operation of a first embodiment of the present invention will be described with reference to the drawings.

Example Embodiment 1

(67) In the first embodiment, when sharing of w is performed by a (2, 3) type RSS scheme using r1, r2, and r3 which are randomly selected to satisfy w=r1+r2+r3 mod 2{circumflex over ( )}n, one apparatus distributes r12=r1+r2 mod 2{circumflex over ( )}n and executes r12+r3 mod 2{circumflex over ( )}n by using secure computation of a full adder, thereby generating bit decomposed share information.

(68) FIG. 1 is a block diagram illustrating an arrangement of the first example embodiment of the present invention. Referring to FIG. 1, a bit decomposition secure computing system 10 according to the first embodiment of the present invention includes a share value storage apparatus 100 that stores share values obtained by applying (2, 3) type RSS using 2{circumflex over ( )}n as p, a decomposed share value storage apparatus 200 that stores bit decomposed share information, and a bit decomposition secure computation apparatus 300 that reads share values stored in the share value storage apparatus 100 and stores bit decomposed values in the decomposed share value storage apparatus 200.

(69) In the first example embodiment, there are provided three sets of apparatuses, wherein the apparatuses 100, 200, and 300 in FIG. 1 constitute one set. That is, there are provided three sets of the systems 10. The apparatuses 100, 200, and 300 or any two apparatuses selected from the apparatuses 100, 200, and 300 may be arranged in one unit, or may be arranged in a distributed manner wherein, for example, at least between the apparatuses 100 and 200 and between the apparatuses 200 and 300, there may be provided one or more communication paths such as local area network (LAN) and/or wide area network (WAN). Note that in FIG. 1, arrowed lines between the apparatuses 100 and 300 and between the apparatuses 300 and 200 each only indicate an example of data flow. The communications between the apparatuses 100 and 300 and between the apparatuses 300 and 200 are as a matter of course not limited to the direction of the arrowed line. The same can be said in later-described other embodiments.

(70) The share value storage apparatus 100 includes a first share value storage unit 101 and a second share value storage unit 102. The first share value storage unit 101 and the second share value storage unit 102 store respectively share values (first share and second share) in such a way that it can be understood which values out of the three values used for generating share information by the (2, 3) type RSS scheme are used and how the values are processed to obtain the stored share value.

(71) The decomposed share value storage apparatus 200 includes a first decomposed share value storage unit 201 and a second decomposed share value storage unit 202. The first decomposed share value storage unit 201 and the second decomposed share value storage unit 202 store respectively the share information (first share value and second share value) in such a way that it can be understood which share values out of the three values used for generating share information by the (2, 3) type RSS scheme are used and how the values are processed to obtain the stored share information.

(72) The bit decomposition secure computation apparatus 300 includes an addition sharing unit 301, a partial share information extraction unit 302, and a full adder secure computation unit 303. The bit decomposition secure computation apparatus 300 reads share values stored in the first share value storage unit 101 and the second share value storage unit 102 of the share value storage apparatus 100, communicates with another bit decomposition secure computation apparatus 300 (not shown), and stores information (bit decomposed share value) in the first decomposed share value storage unit 201 and the second decomposed share value storage unit 202 of the decomposed share value storage apparatus 200.

(73) The addition sharing unit 301, using two indices out of the three values constituting share information by (2, 3) type RSS, as inputs, reads share value(s) stored in the share value storage apparatus 100. If the share value storage apparatus 100 stores share values of both two indices, the addition sharing unit 301 generates share information by the (2, 3) type RSS with respect to a sum of the share values of the two indices and sends the generated share information to the addition sharing units 301 of other two apparatuses (not shown).

(74) The partial share information extraction unit 302, using one index out of the three values constituting share information by (2, 3) type RSS scheme, as input, reads the value stored in the share value storage apparatus 100, and generates share information obtained by setting values to zero except for one of the three values constituting the share information by (2, 3) type RSS scheme.

(75) The full adder secure computation unit 303 performs addition processing using secure computation of a full adder on the share information by (2, 3) type RSS generated and distributed by the addition sharing unit 301 and the share information by (2, 3) type RSS scheme generated by the partial share information extraction unit 302, and stores the value obtained by combining the share information of the computation result for each bit obtained for each bit in the decomposed share value storage apparatus 200.

(76) FIG. 2 is a flowchart illustrating an operation of the first example embodiment of the present invention. It is assumed that in the share value storage apparatus 100, share values that are shared with the (2, 3) type RSS by using r_1, r_2, and r_3 satisfying r=r_1+r_2+r_3 mod 2{circumflex over ( )}n are stored.

(77) In the operation of the first example embodiment,
r_ij=r_i+r_j mod 2{circumflex over ( )}n is shared, and
addition of r_ij and r_k is executed by secure computation of a full adder.

(78) Any combination of i, j, and k may be used as long as i, j and k are values different to each other and selected from a combination of values 1, 2 and 3.

(79) The following processing is executed by 3 sets of share value storage apparatuses 100, decomposed share value storage apparatuses 200, and bit decomposition secure computation apparatuses 300.

(80) First, each addition sharing unit 301 decides whether or not the share value storage apparatus 100 associated with the bit decomposition secure computation apparatus 300 stores information on r_i and r_j. When stored, each addition sharing unit 301 computes r_ij=r_i+r_j mod 2{circumflex over ( )}n and then sends the computed result to the addition sharing unit 301 of the other two bit decomposition secure computation apparatuses 300. After that, each addition sharing unit 301 outputs the share information of r_ij (Step A1).

(81) Next, the partial share information extraction unit 302 produces partial share information in which values other than the portion related to r_k are set to 0 from the values stored in the share value storage apparatus 100 (Step A 2).

(82) Next, the full adder secure computation 303 executes addition processing using secure computation of a full adder with respect to the share information of r_ij and the share information of r_k, and then stores a sequence of the results in the decomposed share value storage apparatus 200 (Step A3).

Example Embodiment 2

(83) The following describes configuration and operation of a second example embodiment of the present invention with reference to the drawings.

(84) In the second example embodiment, when w is shared by (2, 3) type RSS scheme using r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n,

(85) r12=r1+r2 mod 2{circumflex over ( )}n is computed by secure computation of a full adder, and

(86) r12+r3 mod 2{circumflex over ( )}n is computed from lower order bits by secure computation of a full adder.

(87) FIG. 3 is a block diagram illustrating an arrangement of a second example embodiment of the present invention. Referring to FIG. 3, a bit decomposition secure computing system 10A according to the second embodiment of the present invention includes a share value storage apparatus 100 that stores share values obtained by applying (2, 3) type RSS scheme using 2{circumflex over ( )}n as p, a decomposed share value storage apparatus 200 that stores bit decomposed share information, a bit decomposition apparatus 300A that reads share values stored in the share value storage apparatus 100 and stores bit decomposed values in the decomposed share value storage apparatus 200.

(88) There are provided three sets of apparatuses, where apparatuses 100, 200, and 300 in FIG. 1 constitute one set, as with the first example embodiment. That is, there are provided three sets of the systems 10A.

(89) The share value storage apparatus 100 includes a first share value storage unit 101 and a second share value storage unit 102. The first share value storage unit 101 and the second share value storage unit 102 store share values in such a way that it can be understood which values out of the three values used for generating share information by (2, 3) type RSS are used and how the values are processed to obtain the stored share value.

(90) The decomposed share value storage apparatus 200 includes a first decomposed share value storage unit 201 and a second decomposed share value storage unit 202. The first decomposed share value storage unit 201 and the second decomposed share value storage unit 202 store the values (bit decomposed share values) in such a way that it can be understood which values out of the three values used for generating share information by (2, 3) type RSS are used and how the values are processed to obtain the stored share value.

(91) The bit decomposition secure computation apparatus 300 includes a partial share information extraction unit 302 and a full adder secure computation unit 303.

(92) The bit decomposition secure computation apparatus 300A reads values stored in the share value storage apparatus 100, communicates with other two bit decomposition secure computation apparatuses 300A, and stores information in the decomposed share value storage apparatus 200.

(93) The partial share information extraction unit 302 reads, using the index of one of the three values constituting share information by (2, 3) type RSS scheme, as an input, values stored in the share value storage apparatus 100, and generates share information obtained by setting values to zero except for one of the three values constituting the share information by (2, 3) type RSS.

(94) The full adder secure computation apparatus 303A, using 3 sets of share information by the (2, 3) type RSS generated by the partial share information extraction unit 302 as inputs, executes secure computation of a full adder from low order bit, for the three values, and stores the share information of the computation result for each bit in the decomposed share value storage apparatus 200.

(95) FIG. 4 is a flowchart illustrating an operation of the second example embodiment of the present invention.

(96) In the share value storage apparatus 100, there are stored share values of n bit value r to be shared that have been obtained by applying (2, 3) type RSS scheme using r_1, r_2, and r_3, which satisfy r=r_1+r_2+r_3 mod 2{circumflex over ( )}n.

(97) In the operation of the second example embodiment, r_ij=r_i+r_j mod 2{circumflex over ( )}n is executed by secure computation of a full adder, and

(98) r_ij+r_k mod 2{circumflex over ( )}n is executed by secure computation of a full adder, where i, j, and k are values different to each other and selected from a combination of values 1, 2 and 3.

(99) The following processing is executed by the three sets of share value storage apparatuses 100, decomposed share value storage apparatuses 200, and bit decomposition secure computation apparatuses 300A.

(100) First, the partial share information extraction unit 302 outputs partial share information in which values other than the portion related to r_i are regarded as 0 from the values stored in the share value storage apparatus 100. (Step B1)

(101) Next, the partial share information extraction unit 302 outputs partial share information in which values other than the portion related to r_j are regarded as 0 from the values stored in the share value storage apparatus 100. (Step B2)

(102) Next, the partial share information extraction unit 302 outputs partial share information in which values other than the portion related to r_k are regarded as 0 from the values stored in the share value storage apparatus 100. (Step B3)

(103) Next, the full adder secure computation 303 executes secure computation of a full adder in descending order of the least significant bit with respect to the share information of r_i and the share information of r_j, and outputs a sequence of the results as the share information of r_ij. (Step B4)

(104) Next, the full adder secure computation 303 executes secure computation of a full adder with respect to the share information of r_ij and the share information of r_k, and stores a sequence of the results in the decomposed share value storage apparatus 200. (Step B5).

Example Embodiment 3

(105) The following describes a configuration and operation of a third example embodiment of the present invention with reference to the drawings.

(106) In the third example embodiment, with respect to i=1, . . . , N, when a bit w_i is shared by (2, 3) type RSS using r_{1, i}, r_{2, i}, r_{3, i} satisfying w_i=r_{1, i}+r_{2, i}+r_{3, i} mod 2, where w_i, r_{1, i}, r_{2, i}, and r_{3, i} indicate respectively an i-th digit bit of w, r1, r2, and r3, bit combining is performed by executing by secure computation of a full adder,
r12=r_{1,n}∥ . . . ∥r_{1,1}+r_{2,n}∥r_{2,1} mod 2{circumflex over ( )}; and
r12=r12+r_{3,n}∥ . . . ∥r_{3,1} mod 2{circumflex over ( )}n,
where a symbol ∥ is a bit concatenation operator.

(107) FIG. 5 is a block diagram illustrating an arrangement of the third embodiment of the present invention. Referring to FIG. 5, a bit combining secure computing system 20 according to the third embodiment of the present invention comprises a share value storage apparatus 100 that stores share values obtained by applying (2, 3) type RSS using 2{circumflex over ( )}n as p, a bit decomposed share value storage apparatus 200 that stores the share information, and a bit combining secure computation apparatus 400 that reads the values stored in the decomposed share value storage apparatus 200 and stores the values in the share value storage apparatus 100.

(108) There are provided three sets of apparatuses, where apparatuses 100, 200, and 400 in FIG. 5 constitute one set. That is, there are provided three sets of the systems 20.

(109) The share value storage apparatus 100 includes a first share value storage unit 101 and a second share value storage unit 102. The first share value storage unit 101 and the second share value storage unit 102 store share values in such a way that it can be understood which values out of the three values used for generating share information by (2, 3) type RSS scheme are used and how the values are processed to obtain the stored share value.

(110) The decomposed share value storage apparatus 200 includes a first decomposed share value storage unit 201 and a second decomposed share value storage unit 202. The first decomposed share value storage unit 201 and the second decomposed share value storage unit 202 store share values in such a way that it can be understood which values out of the three values used for generating share information by (2, 3) type RSS are used and how the values are processed to obtain the stored share value.

(111) The bit combining secure computation apparatus 400 includes a partial share information extraction unit 302, and a full adder secure computation unit 303.

(112) The bit combining secure computation apparatus 400 reads values stored in the decomposed share value storage apparatus 200, communicates with other binding secure computation apparatuses 400 and stores information in the share value storage apparatus 100.

(113) The partial share information extraction unit 302 extracts, using an index of one of three values constituting share information by (2, 3) type RSS, as an input, reads the value stored in the decomposed share value storage apparatus 200 and generates share information obtained by setting values to zero except for one of the three values constituting the share information by (2, 3) type RSS.

(114) The full adder secure computation unit 303 receives, as inputs, 3 sets of share information by the (2, 3) type RSS generated by the partial share information extraction unit 302, executes secure computation of a full adder, from low order bit of respective three values, and then stores share information of the computation result for each bit in the share value storage apparatus 100.

(115) FIG. 6 is a flowchart illustrating an operation of the third embodiment of the present invention. It is assumed that the decomposed share value storage apparatus 200 stores share values shared with (2,3) type RSS using r_{1, i}, r_{2, i}, r_{3, i} satisfying ri=r_{1, i}+r_{2, i}+r_{3, i} mod 2.

(116) In the operation of the third example embodiment,
r_ij=r_{i,n}∥ . . . ∥r_{i,1}+r_{j,n}∥ . . . r_{j,1} mod 2 n
is executed by secure computation of a full adder, and
r_ij+r_{k,n}∥ . . . r_{k,1} mod 2{circumflex over ( )}n
is executed by secure computation of a full adder, where indices i, j, and k are values different to each other and selected from a combination of values 1, 2, and 3.

(117) The following processing is executed by the three sets of share value storage apparatuses 100, decomposed share value storage apparatuses 200, and bit combining secure computation apparatuses 400.

(118) First, the partial share information extraction unit 302 outputs partially decomposed share information in which values other than a portion related to r_{i, n}∥ . . . ∥r_{i, 1} are regarded as 0 from the values stored in the decomposed share storage apparatus 200 (Step C1).

(119) Next, the partial share information extraction unit 302 extracts partially decomposed share information in which values other than a portion relating to r_{j, n}∥ . . . r_{j, 1} are regarded as 0 from the values stored in the decomposed share value storage apparatus 200 (Step C2).

(120) Next, the partial share information extraction unit 302 extracts partially decomposed share information in which values other than a portion relating to r_{k, n}∥ . . . ∥r_{k, 1} are regarded as 0 from the values stored in the decomposed share value storage apparatus 200 (Step C3).

(121) Next, the full adder secure computation unit 303 performs secure computation of a full adder for partially decomposed share information of r_{i, n}∥ . . . ∥r_{i, 1} and partially decomposed share information of r_{j, n}∥ . . . ∥r_{j, 1} and outputs a sequence of the results, as share information of r_ij (Step C4).

(122) Next, the full adder secure computation unit 303 performs secure computation of a full adder for the share information of r_ij and the partially decomposed share information of r_{k, n}∥ . . . ∥r_{k, 1}, and stores the result in the share value storage apparatus 100 (Step C5).

(123) The bit decomposition secure computing systems 10 and 10A in respectively described in the first and second embodiments may be implemented on a computer system as illustrated in FIG. 7, for example. Referring to FIG. 7, a computer system 500, such as a server system, includes a processor (Central Processing Unit) 502, a memory 504 including, for example, a semiconductor memory (for example, Random Access Memory (RAM), Read Only Memory (ROM), Electrically Erasable and Programmable ROM (EEPROM), and/or a storage device including at least one of Hard Disk Drive (HDD), Compact Disc (CD), Digital Versatile Disc (DVD) and so forth, a display device 506, and a communication interface 508. The communication interface 508 (such as a network interface controller (NIC)) may well be configured to communicate with other computer systems (parties) via LAN and/or WAN, for example. A program for executing the process of the bit decomposition secure computation apparatus in FIG. 1 or FIG. 3 is stored in a memory 504 and the processor 112 reads the program from the memory to execute the program to realize the bit decomposition secure computation. The memory 504 may includes the share value storage apparatus 100 and the decomposed Share value storage apparatus 200. The bit coupling secure computing system 20 in the third example embodiment may well be implemented on a computer system as illustrated in FIG. 7.

(124) According to the first and second example embodiments, it is possible to convert share value shared by (2, 3) type RSS into a value in which each bit is shared by (2, 3) type RSS.

(125) According to the third example embodiment, it is also possible to execute the reverse processing efficiently.

(126) With the processing, it becomes possible to efficiently execute such complex processing that combines secure computation of values and secure computation of bits.

(127) The disclosure of the aforementioned NPLs 1-3 is incorporated by reference herein. The particular exemplary embodiments or examples may be modified or adjusted within the scope of the entire disclosure of the present invention, inclusive of claims, based on the fundamental technical concept of the invention. In addition, a variety of combinations or selections of elements disclosed herein may be used within the concept of the claims. That is, the present invention may encompass a wide variety of modifications or corrections that may occur to those skilled in the art in accordance with the entire disclosure of the present invention, inclusive of claims and the technical concept of the present invention.