SECURE COMPUTATION SYSTEM, SECURE COMPUTATION SERVER APPARATUS, SECURE COMPUTATION METHOD, AND SECURE COMPUTATION PROGRAM

Abstract

An individual one of secure computation server apparatuses in a secure computation system includes: a local reshare part that computes an arithmetic share from a logic share without communicating with the other secure computation server apparatuses by setting a sub-share not held thereby to zero; a secure computation part that performs a secure computation with communications by using the arithmetic share acquired by the local reshare part, to acquire an arithmetic share from the logic share through a bit conversion; and a comparison and verification part that compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopts the received values that are same at least two received values as an accurate value. The comparison and verification part verifies the received values acquired in the secure computation with communications.

Claims

1. A secure computation system, which includes five secure computation server apparatuses connected to each other via a network and which performs a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more), an individual one of the secure computation server apparatuses comprising: a local reshare part that computes an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus to zero; a secure computation part that performs a secure computation with communications by using the arithmetic share acquired by the local reshare part, to acquire an arithmetic share from the logic share through a bit conversion; and a comparison and verification part that compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopts the received values that are same at least two received values as an accurate value; wherein the comparison and verification part verifies the received values acquired in the secure computation with communications.

2. The secure computation system according to claim 1; wherein the individual one of the secure computation server apparatuses further includes a reshare part that shares, as arithmetic shares, temporary variables computed from sub-shares in the logic shares; wherein the comparison and verification part verifies received values of the arithmetic shares of the temporary variables shared by the reshare part; and wherein, by using the arithmetic shares of the temporary variables shared by the reshare part and the arithmetic share obtained by the local reshare part, the secure computation part performs a secure computation to obtain an arithmetic share from the logic share through a bit conversion.

3. The secure computation system according to claim 2; wherein the temporary variables are computed from sub-shares in the logic share commonly held by three of the five secure computation server apparatuses; wherein the reshare part shares arithmetic shares determinably generated from the temporary variables commonly computed by the three secure computation server apparatuses; and wherein, regarding the arithmetic shares received from the three secure computation server apparatuses, the comparison and verification part adopts the received values that are same at least two or more received values as an accurate value.

4. The secure computation system according to claim 1; wherein the comparison and verification part determines that the received values are each an accurate value by determining that hash values of the received values are same.

5. A secure computation server apparatus, which is one of at least five secure computation server apparatuses connected to each other via a network for performing a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more), the secure computation server apparatus comprising: a local reshare part that computes an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus to zero; a secure computation part that performs a secure computation with communications by using the arithmetic share acquired by the local reshare part, to acquire an arithmetic share from the logic share through a bit conversion; and a comparison and verification part that compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopts the received values that are same at least two received values as an accurate value; wherein the comparison and verification part verifies the received values acquired in the secure computation with communications.

6. A secure computation method, for performing a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more) by using five secure computation server apparatuses connected to each other via a network, the secure computation method comprising: causing an individual one of the secure computation server apparatuses to perform reshare to an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held thereby to zero; causing the individual one of the secure computation server apparatuses to perform a secure computation with communications by using the arithmetic share acquired by the reshare, to acquire an arithmetic share from the logic share through a bit conversion; and causing the individual one of the secure computation server apparatuses to compare received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopt the received values, that are same at least two received values as an accurate value, so as to verify the received values acquired in the secure computation with communications.

7. The secure computation method according to claim 6; wherein the individual one of the secure computation server apparatuses performs: resharing, as arithmetic shares, temporary variables computed from sub-shares in the logic shares; comparing received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopting at least two of the received values, the two received values being the same value, as an accurate value, so as to verify the received values of the arithmetic shares of the reshared temporary variables; and performing, by using the arithmetic shares of the reshared temporary variables and the arithmetic share computed without communications, a secure computation to obtain an arithmetic share from the logic share through a bit conversion.

8. The secure computation method according to claim 7; wherein the temporary variables are computed from sub-shares in the logic share commonly held by three of the five secure computation server apparatuses; wherein arithmetic shares determinably generated from the temporary variables commonly computed by the three secure computation server apparatuses are reshared; and wherein, regarding the arithmetic shares received from the three secure computation server apparatuses, the received values that are same at least two or more received values is adopted as an accurate value.

9. The secure computation method according to claim 6; wherein it is determined that the received values are each an accurate value by determining that hash values of the received values are same.

10. A non-transient computer readable medium storing a secure computation program, causing at least five secure computation server apparatuses connected to each other via a network to perform a secure computation on values held in a secret sharing manner and causing five secure computation server apparatuses connected to each other via a network to perform a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more), an individual one of the secure computation server apparatuses performing: resharing to an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held thereby to zero; a secure computation with communications by using the arithmetic share acquired by the reshare, to acquire an arithmetic share from the logic share through a bit conversion; and comparing received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopting the received values that are same at least two received values as an accurate value, so as to verify the received values acquired in the secure computation with communications.

11. The secure computation server apparatus according to claim 5, further includes a reshare part that shares, as arithmetic shares, temporary variables computed from sub-shares in the logic shares; wherein the comparison and verification part verifies received values of the arithmetic shares of the temporary variables shared by the reshare part; and wherein, by using the arithmetic shares of the temporary variables shared by the reshare part and the arithmetic share obtained by the local reshare part, the secure computation part performs a secure computation to obtain an arithmetic share from the logic share through a bit conversion.

12. The secure computation server apparatus according to claim 11; wherein the temporary variables are computed from sub-shares in the logic share commonly held by three of the five secure computation server apparatuses; wherein the reshare part shares arithmetic shares determinably generated from the temporary variables commonly computed by the three secure computation server apparatuses; and wherein, regarding the arithmetic shares received from the three secure computation server apparatuses, the comparison and verification part adopts the received values that are same at least two or more received values as an accurate value.

13. The secure computation server apparatus according to claim 5; wherein the comparison and verification part determines that the received values are each an accurate value by determining that hash values of the received values are same.

14. The non-transient computer readable medium storing the secure computation program according to claim 10, causing the individual one of the secure computation server apparatuses to perform: resharing, as arithmetic shares, temporary variables computed from sub-shares in the logic shares; comparing received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopting at least two of the received values, the two received values being the same value, as an accurate value, so as to verify the received values of the arithmetic shares of the reshared temporary variables; and performing, by using the arithmetic shares of the reshared temporary variables and the arithmetic share computed without communications, a secure computation to obtain an arithmetic share from the logic share through a bit conversion.

15. The non-transient computer readable medium storing the secure computation program according to claim 14; wherein the temporary variables are computed from sub-shares in the logic share commonly held by three of the five secure computation server apparatuses; wherein arithmetic shares determinably generated from the temporary variables commonly computed by the three secure computation server apparatuses are reshared; and wherein, regarding the arithmetic shares received from the three secure computation server apparatuses, the received values that are same at least two or more received values is adopted as an accurate value.

16. The non-transient computer readable medium storing the secure computation program according to claim 10; wherein it is determined that the received values are each an accurate value by determining that hash values of the received values are same.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0017] FIG. 1 is a block diagram illustrating a functional configuration example of a secure computation system according to a first example embodiment.

[0018] FIG. 2 is a block diagram illustrating a functional configuration example of a secure computation server apparatus according to the first example embodiment.

[0019] FIG. 3 is a flowchart illustrating an outline of a procedure of a secure computation method.

[0020] FIG. 4 is a block diagram illustrating a functional configuration example of a secure computation system according to a second example embodiment.

[0021] FIG. 5 is a block diagram illustrating a functional configuration example of a secure computation server apparatus according to the second example embodiment.

[0022] FIG. 6 is a block diagram illustrating a functional configuration example of a secure computation system according to a third example embodiment.

[0023] FIG. 7 is a block diagram illustrating a functional configuration example of a secure computation server apparatus according to the third example embodiment.

[0024] FIG. 8 is a flowchart illustrating an outline of a procedure of a secure computation method.

[0025] FIG. 9 is a diagram illustrating a hardware configuration example of a secure computation server apparatus.

EXAMPLE EMBODIMENTS

[0026] Hereinafter, example embodiments of the present invention will be described with reference to the accompanying drawings. However, the present invention is not limited to the following example embodiments. In addition, in the drawings, the same or equivalent elements are denoted by the same reference characters, as necessary. In addition, the drawings are schematic drawings, and therefore, it should be noted that the sizes, ratios, etc. of the individual elements may differ from their actual sizes, ratios, etc. An element in a drawing may have a portion whose size or ratio differs from that of the portion of the element in a different drawing.

[First Example Embodiment]

[0027] Hereinafter, a secure computation system and secure computation server apparatuses according to a first example embodiment will be described with reference to FIGS. 1 and 2. The first example embodiment is an example embodiment for describing only a basic concept of the present invention.

[0028] FIG. 1 is a block diagram illustrating a functional configuration example of a secure computation system according to the first example embodiment. As illustrated in FIG. 1, a secure computation system 100 according to the first example embodiment includes a first secure computation server apparatus 100_0, a second secure computation server apparatus 100_1, a third secure computation server apparatus 100_2, a fourth secure computation server apparatus 100_3, and a fifth secure computation server apparatus 100_4. The first secure computation server apparatus 100_0, the second secure computation server apparatus 100_1, the third secure computation server apparatus 100_2, the fourth secure computation server apparatus 100_3, and the fifth secure computation server apparatus 100_4 are connected to each other via a network such that these apparatuses can communicate with each other.

[0029] In the secure computation system 100 including the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from a value inputted to any one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) while keeping the input value and the values acquired in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4).

[0030] In addition, in the secure computation system 100 including the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from the shares dispersedly stored in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) while keeping the values in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4).

[0031] The shares of the computation results may be reconstructed by causing the first to fifth secure computation server apparatuses 100_0 to 100_4 exchange their shares with each other. Alternatively, the shares may be decoded by transmitting the shares to an external apparatus other than the first to fifth secure computation server apparatuses 100_0 to 100_4.

[0032] In addition, in the secure computation system 100 including the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), even when one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is operated by a dishonest person, it is possible to continue an accurate secure computation without stopping the processes.

[0033] For example, the following construction may be adopted as the construction of the shares that enables continuation of an accurate secure computation without stopping the processes even when one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is operated by a dishonest person as described above.

[0034] Shares of an element x of a residue class ring Z.sub.n of modulo n, that is, x?Z.sub.n, on the residue class ring Z.sub.n are defined as follows (the shares may be referred to as arithmetic shares, as necessary). Note that n=2.sup.m, where m is an integer of 2 or more. That is, a residue class ring Z.sub.2 of modulo 2 is distinguished from the residue class ring Z.sub.n of modulo n.

[0035] An element x of the residue class ring Z.sub.n of modulo n, that is, x?Z.sub.n, is decomposed to satisfy the following relationship:

x=x.sub.0+x.sub.1+x.sub.2+x.sub.3+x.sub.4 mod n

[x].sub.i dispersedly held by the individual participants Pi (i=0, 1, 2, 3, 4) is defined as follows.

[x].sub.i=(x.sub.i,x.sub.i+1,x.sub.i+2,x.sub.i+3), note that x.sub.4+1=x.sub.0

[0036] Shares of an element x of the residue class ring Z.sub.2 of modulo 2, that is, x?Z.sub.2, on the residue class ring Z.sub.2 (the shares may be referred to as logic shares, as necessary) are defined in the same way as the above shares on the residue class ring Z.sub.n where n=2. However, a different notation [x].sup.B is used to distinguish the residue class ring Z.sub.2 of order 2 from the residue class ring Z.sub.n of modulo n. That is, the shares are specifically defined as follows.

[0037] An element x of the residue class ring Z.sub.2 of modulo 2, that is, x?Z.sub.2, is decomposed as follows. In Equation 1, + inside a circle represents an exclusive-or.

x=x.sub.0?x.sub.1?x.sub.2?x.sub.3?x.sub.4 mod 2 [Equation 1]

[0038] [x].sup.B.sub.i dispersedly held by the individual participants Pi (i=0, 1, 2, 3, 4) is defined as follows.

[x].sup.B.sub.i=(x.sub.i,x.sub.i+1,x.sub.i+2,x.sub.i+3), note that x.sub.4+1=x.sub.0

[0039] If these shares [x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, and [x].sub.4 held by the individual participants Pi (i=0, 1, 2, 3, 4) are determined as described above, the individual participants Pi (i=0, 1, 2, 3, 4) cannot reconstruct x from their shares [x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, and [x].sub.4 held thereby. However, it is possible to realize secret sharing in which x can be reconstructed if the shares held by at least two of the participants Pi (i=0, 1, 2, 3, 4) are combined. This secret sharing scheme is referred to as a 2-out-of-5 Replicated Secret Sharing Scheme.

[0040] In a secure computation based on this secret sharing scheme, not only when x is reconstructed but also when a bit conversion is performed, there is a situation in which the individual participants directly or indirectly receive the values of the sub-shares not held thereby from other participants.

[0041] For example, in the case of value 1, each of (1, 0, 0, 0, 0) and (1, 1, 1, 1, 1) is the result of decomposition of value 1 into an exclusive-or. However, although 1+0+0+0+0=1, 1+1+1+1+1=5. Thus, (1, 1, 1, 1, 1) is not the arithmetic sum of value 1. That is, although (1, 0, 0, 0, 0) and (1, 1, 1, 1, 1) represent the same value as shares of an element x of the residue class ring Z.sub.2 of modulo 2, that is, x?Z.sub.2, on the residue class ring Z.sub.2, (1, 0, 0, 0, 0) and (1,1, 1, 1, 1) do not represent the same value as shares of an element x of the residue class ring Z.sub.n of modulo n, that is, x?Z.sub.n, on the residue class ring Z.sub.n.

[0042] Thus, when a bit conversion is performed, too, there is a situation in which an individual participant also directly or indirectly receives the value of a sub-share not held thereby from other participants. In this situation, if one of the other participants is a dishonest person, a participant could receive a different value instead of a value that the participant is originally supposed to receive. If this happens, the secure computation is performed based on an erroneous value, resulting in an erroneous computation. In some cases, the computation itself cannot be performed properly.

[0043] To solve this problem, in the secure computation system 100 according to the present example embodiment, as illustrated in FIG. 2, an individual one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) includes a local reshare part 101_i, a secure computation part 102_i, and a comparison and verification part 103_i. FIG. 2 is a block diagram illustrating a functional configuration example of a secure computation server apparatus according to the first example embodiment.

[0044] The local reshare part 101_i computes an arithmetic share without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus 100_i to zero from a logic share. The secure computation part 102 i performs a secure computation with communications by using the arithmetic share acquired by the local reshare part 101_i, to acquire an arithmetic share from the logic share through a bit conversion. The comparison and verification part 103_i compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the comparison and verification part 103_i verifies the received values acquired in the secure computation with communications.

[0045] As described above, in the secure computation system 100 according to the present example embodiment, when the bit conversion is performed from logic shares on a residue class ring of modulo 2 to arithmetic shares on a residue class ring of modulo n, reshare (local reshare) is first performed without performing communications. Next, a secure computation with communications is performed to acquire an arithmetic share from the logic share through a bit conversion by using the arithmetic share on which the local reshare has been performed. Next, by comparing received values with each other, which are received in the secure computation with communications from at least three of the secure computation server apparatuses and which are supposed to be the same value, the received values are verified.

[0046] Next, a secure computation method according to the present example embodiment will be described. FIG. 3 is a flowchart illustrating an outline of a procedure of the secure computation method.

[0047] As illustrated in FIG. 3, the secure computation method according to the present example embodiment includes a local reshare step (S11), a secure computation step (S12) with communications, and a comparison and verification step (S13). In the local reshare step (S11), an individual secure computation server apparatus computes an arithmetic share without communicating with the other secure computation server apparatuses by setting a sub-share not held thereby to zero from a logic share. In the secure computation step (S12) with communications, to acquire an arithmetic share from the logic share through a bit conversion, the individual secure computation server apparatus performs a secure computation with communications by using the arithmetic share on which the local reshare has been performed. Next, in the comparison and verification step (S13), the individual secure computation server apparatus compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the individual secure computation server apparatus verifies the received values acquired in the secure computation with communications. The comparison and verification step (S13) is performed each time the secure computation step (S12) with communications is performed.

[0048] As described above, in the secure computation system 100 and the secure computation method according to the present example embodiment, a participant receives received values, which are received from at least three of the other participants and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, even if one of the other participants is a dishonest person, the participant can determine an accurate value. That is, even if there is a dishonest person, it is possible to realize Guaranteed Output Delivery (GOD) that can acquire an accurate computation without stopping the processes. In addition, because no hash function is used in the above processes, Guaranteed Output Delivery (GOD) is realized in a normal model.

[0049] In addition, in the secure computation system 100 and the secure computation method according to the present example embodiment, because reshare (local reshare) is first performed without communications and a secure computation with communications is next performed, reduction in communication cost is achieved.

[0050] The first example embodiment described above is an example embodiment for describing only a basic concept of the present invention. A second example embodiment described below is a practical example embodiment to which the above-described concept is applied.

[Second Example Embodiment]

[0051] Hereinafter, a secure computation system and secure computation server apparatuses according to a second example embodiment will be described with reference to FIGS. 4 and 5.

[0052] FIG. 4 is a block diagram illustrating a functional configuration example of a secure computation system according to the second example embodiment. As illustrated in FIG. 4, a secure computation system 200 according to the second example embodiment includes a first secure computation server apparatus 200_0, a second secure computation server apparatus 200_1, a third secure computation server apparatus 200_2, a fourth secure computation server apparatus 200_3, and a fifth secure computation server apparatus 200_4. The first secure computation server apparatus 200_0, the second secure computation server apparatus 200 1, the third secure computation server apparatus 200_2, the fourth secure computation server apparatus 200_3, and the fifth secure computation server apparatus 200_4 are connected to each other via a network such that these apparatuses can communicate with each other.

[0053] In the secure computation system 200 including the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from a value inputted to any one of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) while keeping the input value and the values acquired in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4).

[0054] In addition, in the secure computation system 200 including the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), even when one of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) is operated by a dishonest person, it is possible to continue an accurate secure computation without stopping the processes.

[0055] FIG. 5 is a block diagram illustrating a functional configuration example of a secure computation server apparatus according to the second example embodiment. As illustrated in FIG. 5, in the secure computation system 200 according to the present example embodiment, an individual one of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) includes a local reshare part 201_i, a secure computation part 202_i, and a comparison and verification part 203_i.

[0056] The local reshare part 201_i computes an arithmetic share without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus 200_i to zero from a logic share. The secure computation part 202_i performs a secure computation with communications by using the arithmetic share acquired by the local reshare part 201_i, to acquire an arithmetic share from the logic share through a bit conversion. The comparison and verification part 203_i compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the comparison and verification part 203_i verifies the received values acquired in the secure computation with communications.

[0057] Hereinafter, building blocks used for execution of the bit conversion according to the present example embodiment will be described. Note that not all the building blocks used for execution of the bit conversion will be described. Of all the four basic arithmetic operations used for the secure computation, multiplication, which is not obvious, will be mainly described.

[Generation of Pseudo Random Numbers and Sharing of Seeds]

[0058] Pseudo-random functions F.sub.n and F2, seeds, and an identifier have a relationship as follows. The pseudo-random functions F.sub.n and F2 are binary operations defined with a security parameter k.

F.sub.n:{0,1}.sup.??{0,1}.sup.?.fwdarw.{0,1}.sup.n

F.sub.2: {0,1}.sup.??{0,1}.sup.?.fwdarw.{0,1}.sup.2

Seeds seed.sub.i?{0,1}.sup.? (i=0, 1, 2, 3, 4) are values appropriately shared by the individual secure computation server apparatuses 200_i, and an identifier vid?{0,1}.sup.? is a public value such as a counter. The pseudo-random functions F.sub.n and F2 determinably generate pseudo random numbers by using the seeds and the identifier as their inputs.

[0059] Regarding the five seeds seed.sub.i?{0,1}.sup.? (i=0, 1, 2, 3, 4), an individual one of the secure computation server apparatuses 200_i holds (seed.sub.i, seed.sub.i+1, seed.sub.i+2, seed.sub.i+3). Note that seed.sub.4+1=seed.sub.0. That is, an individual one of the secure computation server apparatuses 200_i holds the seeds seed.sub.i other than the seed seed.sub.i+4. For example, the sharing of these seeds can be appropriately set by an administrator or the like as a presetting of the secure computation server apparatuses 200_i.

[Creation of Mask]

[0060] Next, a pseudo random number (Correlated Randomness) that is seen as a random number by the participant P.sub.i+4 and cannot be removed and that can be determinably computed by the other participants P.sub.i, P.sub.i+1, P.sub.i+2, and P.sub.i+3 is created, and this pseudo random number will be used as a mask in the multiplication in the secure computation, which will be described below.

[0061] First, since the participant P.sub.i+4 does not hold the seed seed.sub.i+3, if the seed seed.sub.i+3 is used as an input of the pseudo-random function F.sub.n, the following pseudo random number satisfies the above condition. That is, although the following ?.sub.k is seen as a random number by the participant P.sub.i+4 and cannot be removed, the following ?.sub.k can be determinably computed by the other participants P.sub.i, P.sub.i+1, P.sub.i+2, and P.sub.i+3.

?.sub.k=F.sub.n(vid.sub.k,seed.sub.i+3)?F.sub.n(vid.sub.k+1,seed.sub.i+3) mod n

[0062] In addition, by changing the index k in the identifier vid.sub.k from k=0 to k=4, five pseudo random numbers ?.sub.k can be created. A set of these pseudo random numbers ?.sub.k is defined as follows. Whether the following pseudo random numbers ?.sub.0, ?.sub.1, ?.sub.2, ?.sub.3, and ?.sub.4 determined as follows satisfy ?.sub.0+?.sub.1+?.sub.2+?.sub.3+?.sub.4=0 can be easily determined.

(?.sub.0,?.sub.1,?.sub.2,?.sub.3,?.sub.4)=CR(i+4,{vid.sub.k}.sup.4.sub.k=0,seed.sub.i+3)

[0063] Although the pseudo random numbers ?.sub.1, ?.sub.1, ?.sub.2, ?.sub.3, and ?.sub.4 created as described above are seen as random numbers by the participant P.sub.i+4 and cannot be removed, these pseudo random numbers can be determinably computed by the other participants P.sub.i, P.sub.i+1, P.sub.i+2, and P.sub.i+3. However, although the pseudo random numbers ?.sub.0, ?.sub.1, ?.sub.2, ?.sub.3, and ?.sub.4 cannot be removed by the participant P.sub.i+4, if all the pseudo random numbers ?.sub.0, ?.sub.1, ?.sub.2, ?.sub.3, and ?.sub.4 are collected, because the sum is 0, the pseudo random numbers ?.sub.0, ?.sub.1, ?.sub.2, ?.sub.3, and ?.sub.4 can be removed by the participant P.sub.i+4.

[0064] In addition, the creation of the above pseudo random numbers can be performed in the same way for all the other participants P.sub.i+4. Specifically, the pseudo random numbers can be defined as follows.

(?.sub.i,0,?.sub.i,1,?.sub.i,2,?.sub.i,3,?.sub.i,4)=CR(i,{vid.sub.k}.sup.4.sub.k=0,seed.sub.i+4) for i=0, 1, 2, 3, 4

?.sub.i,k=F.sub.n(vid.sub.k,seed.sub.i+4)?F.sub.n(vid.sub.k+1,seed.sub.i+4) mod n for i=0, 1, 2, 3, 4

[0065] The sets of pseudo random numbers created as described above are defined as follows.

TABLE-US-00001 TABLE 1 ?.sub.0, 0 ?.sub.1, 0 ?.sub.2, 0 ?.sub.3, 0 ?.sub.4, 0 ?.sub.0, 1 ?.sub.1, 1 ?.sub.2, 1 ?.sub.3, 1 ?.sub.4, 1 ?.sub.0, 2 ?.sub.1, 2 ?.sub.2, 2 ?.sub.3, 2 ?.sub.4, 2 ?.sub.0, 3 ?.sub.1, 3 ?.sub.2, 3 ?.sub.3, 3 ?.sub.4, 3 ?.sub.0, 4 ?.sub.1, 4 ?.sub.2, 4 ?.sub.3, 4 ?.sub.4, 4

[0066] In the above table of the pseudo random numbers, the sum of first indexes (in the vertical direction) is zero, and the sum of second indexes (in the horizontal direction) is not zero.

[Secure Computation (Multiplication)]

[0067] Next, multiplication, which is an important factor in the secure computation, will be described. That is, a specific example of a secure computation for calculating [z]=[x.Math.y]=[x].Math.[y] from two shares [x] and [y] will be described. Note that x, y, and z have been decomposed as follows.

[00001]$$\begin{gathered} \begin{array}{cc}z=\underset{i=0}{\overset{4}{.Math.}}{z}_i\mathrm{mod}n \\ x=\underset{i=0}{\overset{4}{.Math.}}{x}_i\mathrm{mod}n \\ y=\underset{i=0}{\overset{4}{.Math.}}{y}_i\mathrm{mod}n \\ {z}_i=x_i.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j\mathrm{mod}n& \left[\mathrm{Equations}2\right]\end{array} \end{gathered}$$

[0068] The participant P.sub.i (i=0, 1, 2, 3, 4) computes tmp.sub.zk as follows. x.sub.k.Math.y.sub.i+4 is needed for the participant P.sub.i to compute z.sub.k (the participant P.sub.i cannot compute z.sub.k from the share held thereby), and this tmp.sub.zk is a value that the participant P.sub.i computes instead. In the following Equation 3, ?.sub.j,k represents a pseudo random number described in the above section [Creation of Mask].

[00002]$$\begin{gathered} \begin{array}{cc}{\mathrm{tmp}}_{z_k}=x_k.Math.\left(y_i+y_{i+1}+y_{i+2}+y_{i+3}\right)+\underset{j?i}{.Math.}{?}_{j,k}\mathrm{mod}n \\ \left(k=i,i+1,i+2,i+3\right)& \left[\mathrm{Equation}3\right]\end{array} \end{gathered}$$

[0069] Next, sender groups S.sub.i, S.sub.i+1, S.sub.i+2, and S.sub.i+3 are defined as S.sub.i={P.sub.i+2, P.sub.i+3, P.sub.i+4}, S.sub.i+1={P.sub.i+3, P.sub.i+4, P.sub.i+1}, S.sub.i+2={P.sub.i+4, P.sub.i+1, P.sub.i+2}, and S.sub.i+3={P.sub.i+1, P.sub.i+2, P.sub.i+3}. In this way, the participants belonging to S.sub.k can compute x.sub.ky.sub.i+4 from the shares held thereby. Thus, for example, the participants P.sub.i+2, P.sub.i+3, and P.sub.i+4 belonging to the sender group S.sub.i={P.sub.i+2, P.sub.i+3, P.sub.i+4} compute m.sub.k,i+2, m.sub.k,i+3, and m.sub.k,i+4 in which x.sub.k.Math.y.sub.i+4 is masked by the above pseudo random number ?.sub.i,k.

P.sub.i+2: m.sub.k,i+2=?.sub.i,k+x.sub.k.Math.y.sub.i+4 mod n

P.sub.i+3: m.sub.k,i+3=?.sub.i,k+x.sub.k.Math.y.sub.i+4 mod n

P.sub.i+4: m.sub.k,i+4=?.sub.i,k+x.sub.k.Math.y.sub.i+4 mod n

[0070] In addition, among the participants P.sub.i+2, P.sub.i+3, and P.sub.i+4 belonging to the sender group S.sub.i={P.sub.i+2, P.sub.i+3, P.sub.i+4}, for example, the participants P.sub.i+2 and P.sub.i+3 send m.sub.k,i+2 and m.sub.k,i+3 to the participant P.sub.i without change, and the participant P.sub.i+4 sends a hash value h.sub.k,i+4 of m.sub.k,i+4 to the participant P.sub.i. In this case, since m.sub.k,i+2, m.sub.k,i+3, and m.sub.k,i+4 are masked by the pseudo random number ?.sub.i,k, x.sub.ky.sub.i+4 will not be leaked. That is, although a hash function is used in this case, use of the hash function is not for ensuring security but for reducing the communication cost.

[0071] Next, upon receiving m.sub.k,i+2 and m.sub.k,i+3 and the hash value h.sub.k,i+4 of m.sub.k,i+4, the participant P.sub.i performs comparison and verification on m.sub.k,i+2 and m.sub.k,i+3 and the hash value h.sub.k,i+4 of m.sub.k,i+4. First, the participant P.sub.i computes hash values h.sub.k,i+2 and h.sub.k,i+3 of m.sub.k,i+2 and m.sub.k,i+3. Next, if h.sub.k,i+2=h.sub.k,i+3 or if h.sub.k,i+2=h.sub.k,i+4, the participant P.sub.i determines that m.sub.k=m.sub.k,i+2. If h.sub.k,i+3=h.sub.k,i+4, the participant P.sub.i determines that m.sub.k=m.sub.k,i+2.

[0072] When x.sub.ky.sub.i+4 is sent to the participant P.sub.i as described above, the participant P.sub.i receives the values m.sub.k (hash values thereof), which are supposed to be the same value, from at least three of the other participants P.sub.j and adopts the received values that are same at least two received values as an accurate value. In this way, even when one of the other participants P.sub.j is a dishonest person, it is possible to determine an accurate value.

[0073] Next, the participant P.sub.i computes z.sub.k=tmp.sub.zk+m.sub.k mod n (k=i, i+1, i+2, i+3) by using m.sub.k, which has been determined to be an accurate value.

[00003]$\begin{array}{cc}{z}_k={\mathrm{tmp}}_{z_k}+m_k=\left(x_k.Math.\left(y_i+y_{i+1}+y_{i+2}+y_{i+3}\right)+\underset{j?i}{.Math.}{?}_{j,k}\right)+\left({?}_{j,k}+x_k.Math.y_{i+4}\right)=x_k.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{?}_{j,k}& \left[\mathrm{Equation}4\right]\end{array}$

[0074] Although z.sub.k calculated as described above includes an extra additional term, z.sub.k functions as a share [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3) of the computation result of [z]=[xy]=[x][y]. This becomes clear when z=z.sub.0+z.sub.1+z.sub.2+z.sub.3+z.sub.4 is actually computed as follows.

[00004]$\begin{array}{cc}z=z_0+z_1+z_2+z_3+z_4=\left(x_0.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{?}_{j,0}\right)+\left(x_1.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{?}_{j,1}\right)+\left(x_2.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{?}_{j,2}\right)+\left(x_3.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{?}_{j,3}\right)+\left(x_4.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{?}_{j,4}\right)=\left(x_0+x_1+x_3+x_4\right).Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{k=0}{\overset{4}{.Math.}}{?}_{0,k}+\underset{k=0}{\overset{4}{.Math.}}+{?}_{1,k}+\underset{k=0}{\overset{4}{.Math.}}{?}_{2,k}+\underset{k=0}{\overset{4}{.Math.}}{?}_{3,k}+\underset{k=0}{\overset{4}{.Math.}}{?}_{4,k}=x.Math.y\mathrm{mod}n& \left[\mathrm{Equation}5\right]\end{array}$

[0075] The reason why the pseudo random number ?.sub.i,k can be removed is that the following relational expression is established from the construction of the pseudo random number.

[00005]$\begin{array}{cc}\underset{k=0}{\overset{4}{.Math.}}{?}_{0,k}=\underset{k=0}{\overset{4}{.Math.}}{?}_{1,k}=\underset{k=0}{\overset{4}{.Math.}}{?}_{2,k}=\underset{k=0}{\overset{4}{.Math.}}{?}_{3,k}=\underset{k=0}{\overset{4}{.Math.}}{?}_{4,k}=0& \left[\mathrm{Equation}6\right]\end{array}$

[0076] That is, as described in the above section [Creation of Mask], the pseudo random numbers having the present construction have the nature that the sum of first indexes (in the vertical direction) is zero and that the sum of second indexes (in the horizontal direction) is not zero. The additional term that appears in the computation result of z.sub.k=tmp.sub.zk+m.sub.k mod n (k=i, i+1, i+2, i+3) is the sum of the second indexes (in the horizontal direction) and is not zero. However, when the computation result of [z]=[x.Math.y]=[x].Math.[y] is reconstructed, it becomes consequently possible to remove the impact of the additional term (mask) by using the nature that the sum of first indexes (in the vertical direction) is zero. That is, although z.sub.k calculated as described above includes the extra additional term, z.sub.k functions as a share [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3) of the computation result of [z]=[x.Math.y ]=[x].Math.[y].

[0077] Thus, regarding the share [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3) of the computation result of [z]=[x.Math.y]=[x].Math.[y] as described above, a participant P.sub.i receives the values m.sub.k (hash values thereof), which are supposed to be the same value, from at least three of the other participants P.sub.j and adopts the received values that are same at least two received values as an accurate value. In this way, even when one of the other participants P.sub.j is a dishonest person, it is possible to determine an accurate value. That is, even if there is a dishonest person, it is possible to realize Guaranteed Output Delivery (GOD) that can acquire an accurate computation without stopping the processes. In addition, although a hash function is used in the above processes, this is to reduce the communication amount. Even if the input is deduced from the output, the security is not affected. Thus, Guaranteed Output Delivery (GOD) in a standard model is realized.

[Bit Conversion]

[0078] The bit conversion is a bit conversion: [x]?BC ([x].sup.B) for acquiring arithmetic shares [x] on a residue class ring Z.sub.n of order n from logic shares [x].sup.B on a residue class ring Z.sub.2 of modulo 2. First, as local reshare, an individual secure computation server apparatus performs reshare from a logic share to an arithmetic share without communicating with the other secure computation server apparatuses, by setting a sub-share not held thereby to zero. Specifically, the local reshare is performed as follows.

[0079] The individual participants Pi (i=0, 1, 2, 3, 4) set [x.sub.0].sub.i as follows. [0080] P.sub.0: [x.sub.0].sub.0=(x.sub.0,0,0,0) [0081] P.sub.1: [x.sub.0].sub.1=(0,0,0,0) [0082] P.sub.2: [x.sub.0].sub.2=(0,0,0,x.sub.0) [0083] P.sub.3: [x.sub.0].sub.3=(0,0,x.sub.0,0) [0084] P.sub.4: [x.sub.0].sub.4=(0,x.sub.0,0,0)

[0085] The individual participants Pi (i=0, 1, 2, 3, 4) set [x.sub.1].sub.i as follows. [0086] P.sub.0: [x.sub.1].sub.0=(0,x.sub.1,0,0) [0087] P.sub.1: [x.sub.1].sub.1=(x.sub.1,0,0,0) [0088] P.sub.2: [x.sub.1].sub.2=(0,0,0,0) [0089] P.sub.3: [x.sub.1].sub.3=(0,0,0,x.sub.1) [0090] P.sub.4: [x.sub.1].sub.4=(0,0,x.sub.1,0)

[0091] The individual participants Pi (i=0, 1, 2, 3, 4) set [x.sub.2].sub.i as follows. [0092] P.sub.0: [x.sub.2].sub.0=(0,0,x.sub.2,0) [0093] P.sub.1: [x.sub.2].sub.1=(0,x.sub.2,0,0) [0094] P.sub.2: [x.sub.2].sub.2=(x.sub.2,0,0,0) [0095] P.sub.3: [x.sub.2].sub.3=(0,0,0,0) [0096] P.sub.4: [x.sub.2].sub.4=(0,0,0,x.sub.2)

[0097] The individual participants Pi (i=0, 1, 2, 3, 4) set [x.sub.3].sub.i as follows. [0098] P.sub.0: [x.sub.3].sub.0=(0,0,0,x.sub.3) [0099] P.sub.1: [x.sub.3].sub.1=(0,0,x.sub.3,0) [0100] P.sub.2: [x.sub.3].sub.2=(0,x.sub.3,0,0) [0101] P.sub.3: [x.sub.3].sub.3=(x.sub.3,0,0,0) [0102] P.sub.4: [x.sub.3].sub.4=(0,0,0,0)

[0103] The individual participants Pi (i=0, 1, 2, 3, 4) set [x.sub.4].sub.i as follows. [0104] P.sub.0: [x.sub.4].sub.0=(0,0,0,0) [0105] P.sub.1: [x.sub.4].sub.1=(0,0,0,x.sub.4) [0106] P.sub.2: [x.sub.4].sub.2=(0,0,x.sub.4,0) [0107] P.sub.3: [x.sub.4].sub.3=(0,x.sub.4,0,0) [0108] P.sub.4: [x.sub.4].sub.4=(x.sub.4,0,0,0)

[0109] The above local reshare is not a computation with communications, and therefore, even if one of the participants is a dishonest person, the execution of the computation is not affected.

[0110] Next, a secure computation with communications is performed by using the arithmetic share reshared as described above, to acquire an arithmetic share from the logic share through a bit conversion. Note that, for example, although, as shares of an element x of the residue class ring Z.sub.2 of modulo 2, that is, x?Z.sub.2, on residue class ring Z.sub.2, (1, 0, 0, 0, 0) and (1, 1, 1, 1, 1) are the same value, (1, 0, 0, 0, 0) and (1, 1, 1, 1, 1) are not the same value, as shares of an element x of the residue class ring Z.sub.n of modulo n, that is, x?Z.sub.n, on residue class ring Z.sub.n. This is because decomposition using an exclusive-or does not match decomposition of an arithmetic sum. Thus, the following secure computation is performed to cancel out the difference between the exclusive-or and arithmetic sum.

[x.sub.0?x.sub.1]=([x.sub.0]?[x.sub.1]).sup.2

[x.sub.2?x.sub.3]=([x.sub.2]?[x.sub.3]).sup.2

[(x.sub.0?x.sub.1)?(x.sub.2?x.sub.3)]=([x.sub.0?x.sub.1]?[x.sub.2?x.sub.3]).sup.2

[x]=[(x.sub.0?x.sub.1)?(x.sub.2?x.sub.3)?x.sub.4]=([(x.sub.0?x.sub.1)?(x.sub.2?x.sub.3)]?[x.sub.4]).sup.2 [Equations 7]

[0111] The above secure computation includes squares, that is, multiplications. These multiplications need communications with the other secure computation server apparatuses. Thus, by using the above [Secure Computation (Multiplication)], a secure computation server apparatus compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the secure computation server apparatus verifies the received values acquired in the secure computation with communications.

[0112] As described above, in the secure computation system 200 and the secure computation method according to the second example embodiment, a participant receives received values, which are received from at least three of the other participants and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, even if one of the other participants is a dishonest person, the participant can determine an accurate value. That is, even if there is a dishonest person, it is possible to realize Guaranteed Output Delivery (GOD) that can acquire accurate computation without stopping the processes.

[0113] In addition, although a hash function is used in the above processes, this is to reduce the communication amount. Even if the input is deduced from the output, the security is not affected. Thus, Guaranteed Output Delivery (GOD) in a standard model is realized. In addition, in the secure computation system 200 and the secure computation method according to the present example embodiment, because reshare (local reshare) is first performed without communications, and a secure computation with communications is next performed, reduction in communication cost is achieved.

[Third Example Embodiment]

[0114] Next, a secure computation system and secure computation server apparatuses according to a third example embodiment will be described with reference to FIGS. 6 and 7.

[0115] FIG. 6 is a block diagram illustrating a functional configuration example of a secure computation system according to the third example embodiment. As illustrated in FIG. 6, a secure computation system 300 according to the third example embodiment includes a first secure computation server apparatus 300_0, a second secure computation server apparatus 300_1, a third secure computation server apparatus 300_2, a fourth secure computation server apparatus 300_3, and a fifth secure computation server apparatus 300_4. The first secure computation server apparatus 300_0, the second secure computation server apparatus 300_1, the third secure computation server apparatus 300_2, the fourth secure computation server apparatus 300_3, and the fifth secure computation server apparatus 300_4 are connected to each other via a network such that these apparatuses can communicate with each other.

[0116] In the secure computation system 300 including the first to fifth secure computation server apparatuses 300_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from a value inputted to any one of the first to fifth secure computation server apparatuses 300_i (i=0, 1, 2, 3, 4) while keeping the input value and the values acquired in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 300_i (i=0, 1, 2, 3, 4).

[0117] In addition, in the secure computation system 300 including the first to fifth secure computation server apparatuses 300_i (i=0, 1, 2, 3, 4), even when one of the first to fifth secure computation server apparatuses 300_i (i=0, 1, 2, 3, 4) is operated by a dishonest person, it is possible to continue an accurate secure computation without stopping the processes.

[0118] FIG. 7 is a block diagram illustrating a functional configuration example of a secure computation server apparatus according to the third example embodiment. As illustrated in FIG. 7, in the secure computation system 300 according to the present example embodiment, each of the first to fifth secure computation server apparatus 300_i (i=0, 1, 2, 3, 4) includes a local reshare part 301_i, a secure computation part 302_i, a comparison and verification part 303_i, and a reshare part 304_i.

[0119] The local reshare part 301_i computes an arithmetic share without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus 300_i to zero from a logic share. The secure computation part 302_i performs a secure computation with communications by using the arithmetic share acquired by the local reshare part 301_i, to acquire an arithmetic share from the logic share through a bit conversion. The comparison and verification part 303_i compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the comparison and verification part 303_i verifies the received values acquired in the secure computation with communications. The reshare part 304_i reshares the temporary variables computed from the sub-shares in the logic share as arithmetic shares.

[0120] As described above, the secure computation server apparatus 300_i according to the third example embodiment includes the reshare part 304_i, in addition to the configuration of the secure computation server apparatus 200_i according to the second example embodiment. Hereinafter, the function of this reshare part 304_i in a secure computation method will be described. FIG. 8 is a flowchart illustrating an outline of a procedure of the secure computation method.

[0121] As illustrated in FIG. 8, the secure computation method according to the present example embodiment includes a reshare step (S21), a local reshare step (S22), a secure computation step (S23) with communications, and a comparison and verification step (S24). In the reshare step (S21), temporary variables computed from sub-shares in a logic share are reshared as arithmetic shares. In the local reshare step (S22), a secure computation server apparatus computes an arithmetic share without communicating with the other secure computation server apparatuses, by setting a sub-share not held thereby to zero from the logic share. The local reshare step (S22) may be performed before the reshare step (S21).

[0122] In the secure computation step (S23) with communications, to acquire an arithmetic share from the logic share through a bit conversion, the individual secure computation server apparatus performs a secure computation with communications by using the arithmetic share on which the local reshare has been performed. Next, in the comparison and verification step (S24), the individual secure computation server apparatus compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the individual secure computation server apparatus verifies the received values acquired in the secure computation with communications. The comparison and verification step (S24) is performed each time the secure computation with communications is performed. Thus, the comparison and verification step (S24) is performed not only on the received values acquired in the secure computation step (S23) with communications but also on the received values in the reshare step (S21).

[Reshare]

[0123] First, the function of the reshare part 304_i added in the present example embodiment will be described. The reshare used in the present example embodiment is defined as follows. That is, the reshare is determinably defined from seeds and an identifier when participants P.sub.i, P.sub.i+1 and P.sub.i+2 hold a value c.

[00006]$\begin{array}{cc}\left[c\right]?\mathrm{Reshare}\left(P_i,P_{i+1},P_{i+2},c,{\left\{\mathrm{vi}{d}_j\right\}}_{j=1}^4,{\mathrm{seed}}_{i+2},{\mathrm{seed}}_{i+3}\right)& \left[\mathrm{Equation}8\right]\end{array}$$c_i=\begin{array}{cc}c-r_1-r_2-r_3-r_4-r_1^{}-r_2^{}-r_3^{}-r_4^{}& \left(i=0\right)\\ r_i+r_i^{}& \left(\mathrm{else}\right)\end{array}$$\mathrm{where}c=c_0+c_1+c_2+c_3+c_4\mathrm{mod}n$

[0124] Note that r.sub.j=F.sub.n (vid.sub.k, seed.sub.i+2) and r.sub.j=F.sub.n (vid.sub.k+1, seed.sub.i+3), and that the seeds seed.sub.i?{0, 1}.sup.? (i=0, 1, 2, 3, 4) are those having the nature described in the above section [Generation of Pseudo Random Number and Sharing of Seeds]. Thus, a participant P.sub.i+3 does not know seed.sub.i+2, and a participant P.sub.i+4 does not know seed.sub.i+3. That is, the participant P.sub.i+3 cannot compute c.sub.i+3 by himself or herself and the participant P.sub.i+4 cannot compute c.sub.i+4 by himself or herself. Therefore, the participant P.sub.i+3 needs to receive c.sub.i+3 from the participants P.sub.i, P.sub.i+1, and P.sub.i+2, and the participant P.sub.i+4 needs to receive c.sub.i+4 from the participants P.sub.i, P.sub.i+1, and P.sub.i+2.

[0125] In this step, since a secure computation with communications is performed, the participant P.sub.i+3 compares the received values c.sub.i+3, which are received from the participants P.sub.i, P.sub.i+1, and P.sub.i+2 and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. Similarly, the participant P.sub.i+4 compares the received values c.sub.i+4, which are received from the participants P.sub.i, P.sub.i+1, and P.sub.i+2 and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. Specifically, this step can be performed as follows.

[0126] The participants P.sub.i and P.sub.i+1 send c.sub.j+1, c.sub.j+2, and c.sub.j+3 (j=i+3) to the participant P.sub.i+3. In contrast, the participant P.sub.i+2 sends hash values of c.sub.j+1, c.sub.j+2, and c.sub.j+3 (j=i+3) to the individual participant. In addition, the participants P.sub.i and P.sub.i+1 send c.sub.j+1, c.sub.j+2, and c.sub.j+3 (j=i+3) to the participant P.sub.i+4. In contrast, the participant P.sub.i+2 sends c.sub.j+1, c.sub.j+2, and c.sub.j+3 (j=i+3) to the individual participant. Next, each of the participants P.sub.i+3 and P.sub.i+4 adopts the received values received from the participants P.sub.i, P.sub.i+1, and P.sub.i+2 that are same at least two received values as an accurate value.

[0127] Next, how the above-described reshare is used in the bit conversion will be described.

[Bit Conversion]

[0128] The bit conversion is a bit conversion: [x]?BC ([x].sup.B) for acquiring arithmetic shares [x] on a residue class ring Z.sub.n of modulo n from logic shares [x].sup.B on a residue class ring Z.sub.2 of modulo 2. First, the participants P.sub.3, P.sub.4, and P.sub.0 and the participants P.sub.0, P.sub.1, and P.sub.2 compute temporary variables y.sub.0 and y.sub.1 from sub-shares x.sub.i in the logic share [x].sup.B as follows.

y.sub.0=x.sub.0?x.sub.1

y.sub.1=x.sub.2?x.sub.3 [Equations 9]

[0129] Next, the participants P.sub.3, P.sub.4, and P.sub.0 and the participants P.sub.0, P.sub.1, and P.sub.2 reshare the temporary variables y.sub.0 and y.sub.1.

[y.sub.0]?Reshare(P.sub.3,P.sub.4,P.sub.0,y.sub.0,{vid.sub.0,k}.sub.k=1.sup.4,seed.sub.0,seed.sub.1)

[y.sub.1]?Reshare(P.sub.0,P.sub.1,P.sub.2,y.sub.1,{vid.sub.1,k}.sub.k=1.sup.4,seed.sub.2,seed.sub.3) [Equations 10]

[0130] As described above, since the above reshare is a secure computation with communications, each of the participants P.sub.i+3 and P.sub.i+4 adopts the received values received from the participants P.sub.i, P.sub.i+1, and P.sub.i+2 that are same at least two received values as an accurate value.

[0131] In contrast, the individual participant Pi (i=0, 1, 2, 3, 4) sets [x.sub.4].sub.i as follows. This process is not a secure computation with communications, and therefore, no verification is needed. [0132] P.sub.0: [x.sub.4].sub.0=(0,0,0,0) [0133] P.sub.1: [x.sub.4].sub.1=(0,0,0,x.sub.4) [0134] P.sub.2: [x.sub.4].sub.2=(0,0,x.sub.4,0) [0135] P.sub.3: [x.sub.4].sub.3=(0,x.sub.4,0,0) [0136] P.sub.4: [x.sub.4].sub.4=(x.sub.4,0,0,0)

[0137] Next, finally, by using the arithmetic shares of the temporary variables y.sub.0 and y.sub.1 and the arithmetic shares [x.sub.4].sub.i (i=0, 1, 2, 3, 4), the individual participant Pi (i=0, 1, 2, 3, 4) performs a secure computation as follows to obtain an arithmetic share from the logic share through a bit conversion.

[y.sub.1?x.sub.4]=([y.sub.1]?[x.sub.4]).sup.2

[x]=[y.sub.1?x.sub.4+y.sub.0]=([y.sub.1?x.sub.4]?[y.sub.0]).sup.2 [Equations 11]

[0138] In this step, too, the above secure computation includes multiplications. Thus, by using the above [Secure Computation (Multiplication)], the individual participant Pi compares received values, which are received from at least three of the secure computation server apparatuses and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, the participant Pi verifies the received values acquired in the secure computation with communications.

[0139] As described above, in the secure computation system 300 and the secure computation method according to the third example embodiment, a participant receives received values, which are received from at least three of the other participants and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, even if one of the other participants is a dishonest person, the participant can determine an accurate value. That is, even if there is a dishonest person, it is possible to realize Guaranteed Output Delivery (GOD) that can acquire an accurate computation without stopping the processes.

[0140] In addition, although a hash function is used in the above processes, this is to reduce the communication amount. Even if the input is deduced from the output, the security is not affected. Thus, Guaranteed Output Delivery (GOD) in a standard model is realized. In addition, in the secure computation system 300 and the secure computation method according to the present example embodiment, because reshare (local reshare) is first performed without communications, and a secure computation with communications is next performed, reduction in communication cost is achieved.

[0141] In particular, in the secure computation system 300 and the secure computation method according to the third example embodiment, reshare with communications and reshare without communications are used in combination, and therefore, the communication cost is less than that achieved according to the second example embodiment. Specifically, regarding the communication cost according to the second example embodiment, the number of rounds is 3, and the communication amount is 160 kbits. In contrast, regarding the communication cost according to the third example embodiment, the number of rounds is 3, and the communication amount is 112 kbits. That is, compared with the second example embodiment, the secure computation system 300 and the secure computation method according to the third example embodiment can reduce the communication amount by 48 kbis with the same number of rounds.

[Hardware Configuration Example]

[0142] FIG. 9 is a diagram illustrating a hardware configuration example of a secure computation server apparatus. That is, the hardware configuration example illustrated in FIG. 9 is a hardware configuration example of any one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4). An information processing apparatus (a computer) that adopts the hardware configuration illustrated in FIG. 9 can realize the individual functions of any one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4) by executing the corresponding one of the above secure computation methods as a program.

[0143] The hardware configuration example illustrated in FIG. 9 is an example of the hardware configuration that realizes the individual functions of any one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4), and does not limit the hardware configuration of any one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4). The secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4) may include hardware not illustrated in FIG. 9.

[0144] As illustrated in FIG. 9, a hardware configuration 10 that can be adopted by any one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4) includes, for example, a CPU (Central Processing Unit) 11, a main storage device 12, an auxiliary storage device 13, and an IF (Interface) part 14, which are connected to each other via an internal bus.

[0145] The CPU 11 executes various commands included in the secure computation program executed by the corresponding one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4). The main storage device 12 is, for example, a RAM (Random Access Memory) and temporarily stores various kinds of programs such as the secure computation program executed by the corresponding one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4) so that the CPU 11 can execute the programs.

[0146] The auxiliary storage device 13 is, for example, an HDD (Hard Disk Drive) and can store, in the mid-to-long term, various kinds of programs such as the secure computation program executed by the corresponding one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4). These various kinds of programs such as the secure computation program can be recorded in a non-transitory computer-readable storage medium and can be provided as a program product. The auxiliary storage device 13 can be used to store, in the mid-to-long term, various kinds of programs such as the secure computation program recorded in a non-transitory computer-readable storage medium. The IF part 14 provides an interface regarding the input and output among the corresponding secure computation server apparatuses 100_i, 200_i, or 300_i (i=0, 1, 2, 3, 4).

[0147] An information processing apparatus that adopts the hardware configuration 10 as described above realizes the functions of any one of the secure computation server apparatuses 100_i, 200_i, and 300_i (i=0, 1, 2, 3, 4) by executing the corresponding one of the above-described secure computation methods as a program.

[0148] The above example embodiments can partially or entirely be described, but not limited to, as the following notes.

[Note 1]

[0149] A secure computation system, which includes five secure computation server apparatuses connected to each other via a network and which performs a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more), an individual one of the secure computation server apparatuses including: [0150] a local reshare part that computes an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus to zero; [0151] a secure computation part that performs a secure computation with communications by using the arithmetic share acquired by the local reshare part, to acquire an arithmetic share from the logic share through a bit conversion; and [0152] a comparison and verification part that compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopts the received values that are same at least two received values as an accurate value; [0153] wherein the comparison and verification part verifies the received values acquired in the secure computation with communications.

[Note 2]

[0154] The secure computation system according to note 1; [0155] wherein the individual one of the secure computation server apparatuses further includes a reshare part that shares, as arithmetic shares, temporary variables computed from sub-shares in the logic shares; [0156] wherein the comparison and verification part verifies received values of the arithmetic shares of the temporary variables shared by the reshare part; and [0157] wherein, by using the arithmetic shares of the temporary variables shared by the reshare part and the arithmetic share obtained by the local reshare part, the secure computation part performs a secure computation to obtain an arithmetic share from the logic share through a bit conversion.

[Note 3]

[0158] The secure computation system according to note 2; [0159] wherein the temporary variables are computed from sub-shares in the logic share commonly held by three of the five secure computation server apparatuses; [0160] wherein the reshare part shares arithmetic shares determinably generated from the temporary variables commonly computed by the three secure computation server apparatuses; and [0161] wherein, regarding the arithmetic shares received from the three secure computation server apparatuses, the comparison and verification part adopts the received values that are same at least two or more received values as an accurate value.

[Note 4]

[0162] The secure computation system according to any one of notes 1 to 3; wherein the comparison and verification part determines that the received values are each an accurate value by determining that hash values of the received values are same.

[Note 5]

[0163] A secure computation server apparatus, which is one of at least five secure computation server apparatuses connected to each other via a network for performing a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more), the secure computation server apparatus including: [0164] a local reshare part that computes an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held by its host secure computation server apparatus to zero; [0165] a secure computation part that performs a secure computation with communications by using the arithmetic share acquired by the local reshare part, to acquire an arithmetic share from the logic share through a bit conversion; and [0166] a comparison and verification part that compares received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopts the received values that are same at least two received values as an accurate value; [0167] wherein the comparison and verification part verifies the received values acquired in the secure computation with communications.

[Note 6]

[0168] A secure computation method, for performing a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more) by using five secure computation server apparatuses connected to each other via a network, the secure computation method including: [0169] causing an individual one of the secure computation server apparatuses to perform reshare to an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held thereby to zero; [0170] causing the individual one of the secure computation server apparatuses to perform a secure computation with communications by using the arithmetic share acquired by the reshare, to acquire an arithmetic share from the logic share through a bit conversion; and [0171] causing the individual one of the secure computation server apparatuses to compare received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopt the received values that are same at least two received values as an accurate value, so as to verify the received values acquired in the secure computation with communications.

[Note 7]

[0172] The secure computation method according to note 6; wherein the individual one of the secure computation server apparatuses performs: [0173] resharing, as arithmetic shares, temporary variables computed from sub-shares in the logic shares; [0174] comparing received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopting at least two of the received values, the two received values being the same value, as an accurate value, so as to verify the received values of the arithmetic shares of the reshared temporary variables; and [0175] performing, by using the arithmetic shares of the reshared temporary variables and the arithmetic share computed without communications, a secure computation to obtain an arithmetic share from the logic share through a bit conversion.

[Note 8]

[0176] The secure computation method according to note 7;

[0177] wherein the temporary variables are computed from sub-shares in the logic share commonly held by three of the five secure computation server apparatuses; [0178] wherein arithmetic shares determinably generated from the temporary variables commonly computed by the three secure computation server apparatuses are reshared; and [0179] wherein, regarding the arithmetic shares received from the three secure computation server apparatuses, the received values that are same at least two or more received value is adopted as an accurate value.

[Note 9]

[0180] The secure computation method according to any one of notes 6 to 8; wherein it is determined that the received values are each an accurate value by determining that hash values of the received values are same.

[Note 10]

[0181] A secure computation program, causing at least five secure computation server apparatuses connected to each other via a network to perform a secure computation on values held in a secret sharing manner and causing five secure computation server apparatuses connected to each other via a network to perform a bit conversion from logic shares on a residue class ring of modulo 2 that are held in a secret sharing manner to arithmetic shares on a residue class ring of modulo n (n=2.sup.m; m is an integer of 2 or more), an individual one of the secure computation server apparatuses performing: [0182] resharing to an arithmetic share from the logic shares without communicating with the other secure computation server apparatuses by setting a sub-share not held thereby to zero; [0183] a secure computation with communications by using the arithmetic share acquired by the reshare, to acquire an arithmetic share from the logic share through a bit conversion; and comparing received values with each other, which are received from at least three of the secure computation server apparatuses and which are supposed to be a same value, and adopting the received values that are same at least two received values as an accurate value, so as to verify the received values acquired in the secure computation with communications.

[0184] The disclosure of the above NPL is incorporated herein by reference thereto. Modifications and adjustments of the example embodiments or examples are possible within the scope of the overall disclosure (including the claims) of the present invention and based on the basic technical concept of the present invention. Various combinations or selections (including partial deletion) of various disclosed elements (including the elements in each of the claims, example embodiments, examples, drawings, etc.) are possible within the scope of the disclosure of the present invention. That is, the present invention of course includes various variations and modifications that could be made by those skilled in the art according to the overall disclosure including the claims and the technical concept. The description discloses numerical value ranges. However, even if the description does not particularly disclose arbitrary numerical values or small ranges included in the ranges, these values and ranges should be deemed to have been specifically disclosed. In addition, as needed and based on the gist of the present invention, partial or entire use of the individual disclosed matters in the above literatures that have been referred to in combination with what is disclosed in the present application should be deemed to be included in what is disclosed in the present application, as a part of the disclosure of the present invention.

REFERENCE SIGNS LIST

[0185] 100, 200, 300 secure computation system [0186] 100 i, 200_i, 300_i secure computation server apparatus [0187] 101_i, 201_i, 301_i local reshare part [0188] 102_i, 202_i, 302_i secure computation part [0189] 103_i, 203_i, 303_i comparison and verification part [0190] 304_i reshare part [0191] 10 hardware configuration [0192] 11 CPU (Central Processing Unit) [0193] 12 main storage device [0194] 13 auxiliary storage device [0195] 14 IF (Interface) part