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

Abstract

A secure computation system comprises at least five secure computation server apparatuses connected to each other via a network and performs secure computation on a value stored while being secret-shared, and each of the secure computation server apparatuses has a comparative verification part that compares values, which should be the same, received from at least three secure computation server apparatuses and that accepts a received value identical to at least another received value as a correct value.

Claims

1. A secure computation system comprising at least five secure computation server apparatuses connected to each other via a network and performing secure computation on a value stored while being secret-shared, wherein each of the secure computation server apparatuses comprises: a comparative verification part that compares values, which should be the same, received from at least three secure computation server apparatuses and accepts a received value identical to at least another received value as a correct value.

2. The secure computation system according to claim 1, wherein each of the secure computation server apparatuses further comprises: a pseudorandom function computation part that deterministically generates a pseudorandom number using a seed and an identifier as inputs and makes a set of masks that sum to zero with respect to a first index and sum to a nonzero value with respect to a second index by using the pseudorandom numbers, and wherein the received value is sent while being kept in secret with the mask.

3. The secure computation system according to claim 2, wherein a share value of multiplication of two share values secret-shared by each of the secure computation server apparatuses includes the sum with respect to the second index as an additional term, and removing the mask using the fact that the sum with respect to the first index is zero when reconstructing the result of the multiplication.

4. The secure computation system according to claim 1, wherein the comparative verification part determines that the received values are correct by verifying that hash values of the received values are the same.

5. A secure computation server apparatus out of at least five secure computation server apparatuses, connected to each other via a network, for performing secure computation on a value stored while being secret-shared, the secure computation server apparatus comprising: a comparative verification part that compares values, which should be the same, received from at least three secure computation server apparatuses and accepts a received value identical to at least another received value as a correct value.

6. A secure computation method comprising at least five secure computation server apparatuses connected to each other via a network and performing secure computation on a value stored while being secret-shared, wherein each of the secure computation server apparatuses compares values, which should be the same, received from at least three secure computation server apparatuses and accepts a received value identical to at least another received value as a correct value.

7. The secure computation method according to claim 6 deterministically generating a pseudorandom number using a seed and an identifier as inputs, making a set of masks that sum to zero with respect to a first index and sum to a nonzero value with respect to a second index by using the pseudorandom numbers, and sending the received value being kept in secret with the mask.

8. The secure computation method according to claim 7, wherein a share value of multiplication of two share values secret-shared by each of the secure computation server apparatuses includes the sum with respect to the second index as an additional term, and removing the mask using the fact that the sum with respect to the first index is zero when reconstructing the result of the multiplication.

9. The secure computation method according to claim 6 determining that the received values are correct by verifying that hash values of the received values are the 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 secure computation on a value stored while being secret-shared, the secure computation program including: a process of comparing values, which should be the same, received from at least three secure computation server apparatuses and accepting a received value identical to at least another received value as a correct value.

11. The secure computation server apparatus according to claim 5, further comprises: a pseudorandom function computation part that deterministically generates a pseudorandom number using a seed and an identifier as inputs and makes a set of masks that sum to zero with respect to a first index and sum to a nonzero value with respect to a second index by using the pseudorandom numbers, and wherein the received value is sent while being kept in secret with the mask.

12. The secure computation server apparatus according to claim 11, wherein a share value of multiplication of two share values secret-shared by each of the secure computation server apparatuses includes the sum with respect to the second index as an additional term, and removing the mask using the fact that the sum with respect to the first index is zero when reconstructing the result of the multiplication.

13. The secure computation server apparatus according to claim 5, wherein the comparative verification part determines that the received values are correct by verifying that hash values of the received values are the same.

14. The non-transient computer readable medium storing a secure computation program according to claim 10, including: a process of deterministically generating a pseudorandom number using a seed and an identifier as inputs, making a set of masks that sum to zero with respect to a first index and sum to a nonzero value with respect to a second index by using the pseudorandom numbers, and a process of sending the received value being kept in secret with the mask.

15. The non-transient computer readable medium storing a secure computation program according to claim 14, wherein a share value of multiplication of two share values secret-shared by each of the secure computation server apparatuses includes the sum with respect to the second index as an additional term, and including: a process of removing the mask using the fact that the sum with respect to the first index is zero when reconstructing the result of the multiplication.

16. The non-transient computer readable medium storing a secure computation program according to claim 10, including: a process of determining that the received values are correct by verifying that hash values of the received values are the same.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0015] FIG. 1 is a block diagram showing an example of the functional configuration of a secure computation system according to a first example embodiment.

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

[0017] FIG. 3 is a block diagram showing an example of the functional configuration of a secure computation system according to a second example embodiment.

[0018] FIG. 4 is a flowchart showing an outline of the procedure of a secure computation method.

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

[0020] FIG. 6 is a drawing showing an example of the hardware configuration of the secure computation server apparatus.

EXAMPLE EMBODIMENTS

[0021] Example embodiments of the present invention will be described with reference to the drawings. The present invention, however, is not limited to the example embodiments described below. Further, in each drawing, the same or corresponding elements are appropriately designated by the same reference signs. It should also be noted that the drawings are schematic, and the dimensional relationships and the ratios between the elements may differ from the actual ones. The dimensional relationships and the ratios between drawings may also be different in some sections.

First Example Embodiment

[0022] The following describes a secure computation system and secure computation server apparatus relating to a first example embodiment with reference to FIGS. 1 and 2. In the first example embodiment, only the basic concept of the present invention is described.

[0023] FIG. 1 is a block diagram showing an example of the functional configuration of the secure computation system according to the first example embodiment. As shown in FIG. 1, the secure computation system 100 according to the first example embodiment comprises 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, the second, the third, the fourth, and the fifth secure computation server apparatuses 100_0, 100_1, 100_2, 100_3, and 100_4 are connected to each other via a network so as to be able to communicate with each other. A circle in the center of FIG. 1 indicates the network.

[0024] The secure computation system 100 comprising the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is able to compute desired shares of a value supplied by any one of the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) as an input while keeping the input value and the values during the computation process secret, and distribute the computation results to the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) to store them therein.

[0025] Further, the secure computation system 100 comprising the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is able to compute desired shares of shares distributed to and stored in the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) while keeping the values during the computation process secret, and distribute the computation results to the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) to store them therein.

[0026] Further, the shares that resulted from the computations above may be reconstructed by exchanging the shares with the first to the fifth secure computation server apparatuses 100_0 to 100_4. Alternatively, the shares may be reconstructed by transmitting them to an external apparatus, instead of the first to the fifth secure computation server apparatuses 100_0 to 100_4.

[0027] Further, the secure computation system 100 comprising the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is able to continue correct secure computation without interrupting the process even when one of the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is operated by an adversary.

[0028] For instance, the following share configuration may be employed so that correct secure computation can be continued without interrupting the process even when one of the first to the fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is operated by an adversary.

[0029] Shares of a residue class ring Z.sub.n of order n for each party P.sub.i (i=0, 1, 2, 3, 4) are defined as follows.

[0030] The shares over the residue class ring Z.sub.n of an element x∈Z.sub.n of the residue class ring Z.sub.n of order n are expressed as below. Further, m is an integer of 2 or more and n=2.sup.m. In other words, a residue class ring Z.sub.2 of order 2 is distinguished from the residue class ring Z.sub.n of order n.

[x]=([x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, [x].sub.4)

[0031] Decompose the element x∈Z.sub.n of the residue class ring Z.sub.n of order n to satisfy the relationship with:

x=x.sub.0+x.sub.1+x.sub.2+x.sub.3+x.sub.4 mod n, [0032] and define [x].sub.i distributed to and held by each party P.sub.i (i=0, 1, 2, 3, 4) as follows:

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

[0033] Meanwhile, shares over the residue class ring Z.sub.2 of an element x∈Z.sub.2 of the residue class ring Z.sub.2 of order 2 are defined in the same manner as shares over the residue class ring Z.sub.n when n=2, however, they are notated differently from the residue class ring Z.sub.n of order n and expressed as [x].sup.B.

[0034] When the shares [x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, [x].sub.4 held by each party P.sub.i (i=0, 1, 2, 3, 4) are defined as above, each party P.sub.i (i=0, 1, 2, 3, 4) cannot reconstruct x from one of the shares [x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, [x].sub.4 that he/she holds. There is a secret sharing scheme in which x can be reconstructed by combining the shares held by at least two of the parties P.sub.i (i=0, 1, 2, 3, 4). This secret sharing scheme is called a 2-out-of-5 additive secret sharing scheme.

[0035] In this secret sharing scheme, in addition to when reconstructing x, when performing secure computation, a party P.sub.i needs to receive from another party P.sub.j a share value x.sub.i+4 that P.sub.i does not have. At this time, since all the other parties P.sub.j should have the share value x.sub.i+4 that the party P.sub.i does not have, the party P.sub.i should essentially be able to receive the share value x.sub.i+4, which P.sub.i does not have, from any one of the other parties P.sub.j. If, however, there is an adversary among the other parties P.sub.j, he/she may transmit the wrong value, instead of the value x.sub.i+4 that P.sub.i should receive. Then, P.sub.i may end up performing secure computation based on the wrong value, obtaining the wrong computation, or may not be able to execute the computation itself normally in the first place.

[0036] Therefore, in the present example embodiment, each secure computation server apparatus 100_i comprises a comparative verification part 101_i, as shown in FIG. 2, and compares values, which should be the same, received from at least three other secure computation server apparatuses. When at least two other secure computation server apparatuses send the same value, the secure computation server apparatus 100_i accepts this value as a correct value. As a result, correct computation results can be obtained without interrupting the process even if there is an adversary among the parties.

[0037] More specifically, the following process example is conceivable. Here, let us imagine a situation in which, when reconstructing x, a party P.sub.i receives from another party P.sub.j a share value x.sub.i+4, which P.sub.i does not have. Further, each party P.sub.i (i=0, 1, 2, 3, 4) operates each secure computation server apparatus 100_i (i=0, 1, 2, 3, 4), but actual processing is executed by each secure computation server apparatus 100_i (i=0, 1, 2, 3, 4), not each party P.sub.i (i=0, 1, 2, 3, 4).

[0038] Reconstructing x requires all the values x.sub.0, x.sub.1, x.sub.2, x.sub.3, x.sub.4 due to the relational expression x=x.sub.0+x.sub.1+x.sub.2+x.sub.3+x.sub.4 mod n. However, since the share held by a party P.sub.i is [x].sub.i=(x.sub.i, x.sub.i+1, x.sub.i+2, x.sub.i+3) (where x.sub.4+1=x.sub.0), P.sub.i does not have x.sub.i+4. Therefore, the party P.sub.i needs to receive x.sub.i+4 from another party P.sub.j.

[0039] Meanwhile, because of the way the shares are defined, all the other parties P.sub.j hold x.sub.i+4. Therefore, all P.sub.i needs to do is receive x.sub.i+4 from one of the other parties P.sub.j, but here, P.sub.i receives supposedly same x.sub.i+4 from at least three other parties P.sub.j. Further, with the assumption that x.sub.i+4 is received from three other parties P.sub.j, the values received from each of the three parties are notated as x.sub.i+4, 1, x.sub.i+4, 2, x.sub.i+4, 3 in order to distinguish them.

[0040] Then, the party P.sub.i compares the received values x.sub.i+4, 1, x.sub.i+4, 2, x.sub.i+4, 3, which should be the same. When at least two of the received values are identical, the party P.sub.i accepts this value as the correct value x.sub.i+4.

[0041] For instance, if x.sub.i+4, 1=x.sub.i+4, 2 or x.sub.i+4, 1=x.sub.i+4, 3, then P.sub.i takes x.sub.i+4, 1 as the correct value x.sub.i+4 (x.sub.i+4=x.sub.i+4, 1). Further, if x.sub.i+4, 2=x.sub.i+4, 3, then P.sub.i takes x.sub.i+4, 2 as the correct value x.sub.i+4 (x.sub.i+4=x.sub.i+4, 2). As described, when at least two of the received values are the same, by accepting this value as the correct value, even if one of the received values x.sub.i+4, 1, x.sub.i+4, 2, x.sub.i+4, 3 is false, the correct value can be determined. Then, by calculating x=x.sub.0+x.sub.1+x.sub.2+x.sub.3+x.sub.4 mod n using the correct value x.sub.i+4, x can be reconstructed.

[0042] As described, even if there is an adversary among the other parties P.sub.j, the correct value can be determined by receiving the supposedly same x.sub.i+4 from at least three other parties P.sub.j and accepting a value sent by at least two parties as the correct value. In other words, even if there is an adversary, the correct computation can be obtained without interrupting the process, thereby achieving Guaranteed Output Delivery (GOD). Further, in the above process, since no hash function is used in the first place, Guaranteed Output Delivery (GOD) is achieved in the standard model.

[0043] In the first example embodiment described above, only the basic concept of the present invention was discussed. Therefore, in order to apply the present invention to a practical example embodiment, it is necessary to apply the concept described above to a series of processes including addition and multiplication. In the following second example embodiment, the concept described above is applied to a practical example embodiment.

Second Example Embodiment

[0044] The following describes a secure computation system and secure computation server apparatus relating to the second example embodiment with reference to FIGS. 3 and 4.

[0045] FIG. 3 is a block diagram showing an example of the functional configuration of the secure computation system according to the second example embodiment. As shown in FIG. 3, the secure computation system 200 according to the second example embodiment comprises 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, the second, the third, the fourth, and the fifth secure computation server apparatuses 200_0, 200_1, 200_2, 200_3, and 200_4 are connected to each other via a network so as to be able to communicate with each other. The secure computation system 200 comprising the first to the fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) is able to compute desired shares of a value supplied by any one of the first to the fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) as an input while keeping the input value and the values during the computation process secret, and distribute the computation results to the first to the fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) to store them therein.

[0046] Further, the secure computation system 200 comprising the first to the fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) is able to continue correct secure computation without interrupting the process even when one of the first to the fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) is operated by an adversary.

[0047] FIG. 4 is a flowchart showing an outline of the procedure of a secure computation method. The procedure of the secure computation method shown in FIG. 4 is merely a typical example of a secure computation procedure for facilitating the description, and in an actual secure computation method, it is normal to make changes such as executing only some steps, executing the steps in a different order, or repeating some steps.

[0048] As shown in FIG. 4, a typical secure computation procedure includes a preparation step (step S1), a pseudorandom number computation step (step S2), an input step (step S3), a secure computation step (step S4), and a reconstruction step (step S5).

[0049] For instance, the preparation step (the step S1) includes a process for having each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) appropriately share seeds for generating pseudorandom numbers. The pseudorandom number computation step (the step S2) includes a process of deterministically generating pseudorandom numbers using the seeds shared by each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) in the preparation step (the step S1) and an identifier. Further, the generated pseudorandom numbers are used for masking in the secure computation step (the step S4).

[0050] The input step (the step S3) is a step for distributing inputs, to be securely computed, to each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) and storing them therein. The secure computation step (the step S4) is a step of performing desired computation on the shares distributed to and stored in each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) while maintaining secrecy. Any computation can be performed in the secure computation step (the step S4), but multiplication is particularly important. The results of the secure computation step (the step S4) are generally shares, which are distributed to and stored in each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4). The reconstruction step (the step S5) is a step of reconstructing the shares resulting from the secure computation step (the step S4).

[0051] The following describes the process details for each step.

Preparation (Seed Sharing)

[0052] The seeds generated in the preparation step (the step S1) are for having pseudorandom functions F.sub.n, F.sub.2 to deterministically generate pseudorandom numbers. The secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) appropriately share the seeds for generating pseudorandom numbers so that the secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) can generate pseudorandom numbers appropriately associated with each other. The seeds shared by the secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) may be configured and given to each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) by a trusted third party as an initial setting, however, the following describes a procedure for having the secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) share the seeds while subsequently maintaining secrecy. When the secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) cooperate with each other to share the seeds, for instance, the secure computation server apparatus 200_i comprises a comparative verification part 201_i as shown in FIG. 5, and Guaranteed Output Delivery (GOD) in the standard model is achieved by having the comparative verification part 201_i choose the correct value. Further, it is possible to realize the comparative verification part 201_i as a program executed in a hardware configuration described later.

[0053] The relationship between the pseudorandom functions F.sub.n, F.sub.2, the seeds and the identifier is as follows. The pseudorandom functions F.sub.n, F.sub.2 are binary operations defined for a security parameter κ.

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

[0054] Meanwhile, seed.sub.i∈{0, 1}.sup.κ (i=0, 1, 2, 3, 4) are values appropriately shared by the secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), and the identifier vid∈{0, 1}.sup.κ is a public value such as a counter. The pseudorandom functions F.sub.n, F.sub.2 receive these seeds and the identifier as inputs and deterministically generate pseudorandom numbers.

[0055] Of five seeds (seed.sub.i∈{0, 1}.sup.κ (i=0, 1, 2, 3, 4)), each secure computation server apparatus 200_i holds (seed.sub.i, seed.sub.i+1, seed.sub.i+2, seed.sub.i+3), where seed.sub.4+1=seed.sub.0. In other words, each secure computation server apparatus 200_i does not hold every seed.sub.i; the only seed each secure computation server apparatus 200_i does not have is seed.sub.i+4.

[0056] In order for the secure computation server apparatuses 200_i to share the seeds as described above, information must be exchanged among them. Then, if there is any secure computation server apparatus 200_i operated by an adversary, the seeds cannot be appropriately shared. Therefore, in the preparation step (the step S1) of the present example embodiment, the seeds are shared as follows.

[0057] The following describes an example of generating a seed.sub.i. The seed.sub.i should be held by the four parties P.sub.i, P.sub.i+1, P.sub.i+2, P.sub.i+3, who therefore cooperate with each other to generate the seed.sub.i.

[0058] Initially, each party P.sub.i, P.sub.i+1, P.sub.i+2, P.sub.i+3 randomly generates s.sub.i.sup.(i), s.sub.i.sup.(i+1), s.sub.i.sup.(i+2), s.sub.i.sup.(i+3)∈{0, 1}.sup.κ.

[0059] Then, the party P.sub.i sends s.sub.i.sup.(i) to the other parties P.sub.i+1, P.sub.i+2, P.sub.i+3. Meanwhile, the parties P.sub.i+1, P.sub.i+2, P.sub.i+3 exchange the received s.sub.i.sup.(i) with each other. The parties P.sub.i+1, P.sub.i+2, P.sub.i+3 make the following judgments on s.sub.i.sup.(i) exchanged with each other.

(1) When s.sub.i.sup.(i) obtained from the other two parties match, P.sub.i+1, P.sub.i+2, P.sub.i+3 deem s.sub.i.sup.(i) obtained from the other two to be correct and send an “accept” message to the other two parties.
(2) When s.sub.i.sup.(i) obtained from the other two parties do not match, but either of them matches their own s.sub.i.sup.(i), P.sub.i+1, P.sub.i+2, P.sub.i+3 deem their own s.sub.i.sup.(i) to be correct. They then send a “revise” message along with their own s.sub.i.sup.(i) to the party who sent the unmatched s.sub.i.sup.(i) and send an “accept” message to the party who sent the matched s.sub.i.sup.(i).
(3) When s.sub.i.sup.(i) obtained from the other two parties do not match and they do not match their own s.sub.i.sup.(i) either, P.sub.i+1, P.sub.i+2, P.sub.i+3 send a (corrupted, P.sub.i) message to the other two parties.

[0060] When P.sub.i+1, P.sub.i+2, P.sub.i+3 receive “accept” messages from the other two, they continue to the next step, and when they receive a “revise” message, they accept s.sub.i.sup.(i) sent along with the message as the correct one and continue to the next step. Meanwhile, if they receive a (corrupted, P.sub.i) message, they exclude P.sub.i and perform semi-honest secure four-party computation since P.sub.i is an adversary.

[0061] The procedure described above is also performed on the parties P.sub.i+1, P.sub.i+2, P.sub.i+3 so that the parties P.sub.i, P.sub.i+1, P.sub.i+2, P.sub.i+3 share the correct values of s.sub.i.sup.(i), s.sub.i.sup.(i+1), s.sub.i.sup.(i+2), s.sub.i.sup.(i+3)∈{0, 1}.sup.κ. Then, the seed.sub.i is generated from the shared s.sub.i.sup.(i), s.sub.i.sup.(i+1), s.sub.i.sup.(i+2), s.sub.i.sup.(i+3) as follows:

seed.sub.i=s.sub.i.sup.(i)⊕s.sub.i.sup.(i+1)⊕s.sub.i.sup.(i+2)⊕s.sub.i.sup.(i+3)   [Math. 1]

[0062] By performing the procedure described above for the five seeds (seed.sub.i∈{0, 1}.sup.κ (i=0, 1, 2, 3, 4)), each secure computation server apparatus 200_i is able to correctly hold (seed.sub.i, seed.sub.i+1, seed.sub.i+2, seed.sub.i+3).

[0063] In the seed sharing method described above, by receiving the supposedly same s.sub.i.sup.(i) from at least three other parties P.sub.j and accepting a value sent by at least two parties as the correct value, even if there is an adversary among the other parties P.sub.j, the correct value can be determined. In other words, the correct computation can be obtained without interrupting the process even if there is an adversary, thereby achieving Guaranteed Output Delivery (GOD). Further, in the above process, since no hash function is used in the first place, Guaranteed Output Delivery (GOD) is achieved in the standard model.

Pseudorandom Number Computation (Mask Generation)

[0064] The pseudorandom number computation step (the step S2) deterministically generates pseudorandom numbers using the seeds generated in the preparation step (the step S1) and the identifier. The pseudorandom numbers generated in the pseudorandom number computation step (the step S2) are used to mask values to be sent in secure computation later. For this purpose, pseudorandom numbers that follow the rules described below (correlated randomness) are generated. For instance, in order to generate pseudorandom numbers following the rules described below, each secure computation server apparatus 200_i may comprise a pseudorandom function computation part 202_i, as shown in FIG. 5, and each pseudorandom function computation part 202_i may generate pseudorandom numbers following the rules described below. Further, it is possible to realize the pseudorandom function computation part 202_i as the program executed in the hardware configuration described later.

[0065] Here, let us look at a case where the parties P.sub.i, P.sub.i+1, P.sub.i+2, P.sub.i+3 cooperate and create correlated randomness that appears random to the party P.sub.i+4 and cannot be removed by him/her, but that can be deterministically computed by the remaining parties P.sub.i, P.sub.i+1, P.sub.i+2, P.sub.i+3. In order to achieve this, because the party P.sub.i+4 does not have seed.sub.i+3, the pseudorandom number below satisfies these conditions when seed.sub.i+3 is used as an input of the pseudorandom function F.sub.n.

α.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

[0066] Further, it is possible to generate five ak by varying the index k of the identifier vidk from k=0 to k=4. Therefore, a set of α.sub.k is defined as shown below. It can be easily verified that α.sub.0, α.sub.1, α.sub.2, α.sub.3, α.sub.4 defined as below satisfy α.sub.0+α.sub.1+α.sub.2+α.sub.3+α.sub.4=0.

(α.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)

[0067] The pseudorandom numbers α.sub.0, α.sub.1, α.sub.2, α.sub.3, α.sub.4 generated in this way look like random numbers to the party P.sub.i+4 and cannot be removed by him/her, but the remaining parties P.sub.i, P.sub.i+1, P.sub.i+2, P.sub.i+3 can compute them deterministically. Meanwhile, although the party P.sub.i+4 cannot remove each of the pseudorandom numbers α.sub.0, α.sub.1, α.sub.2, α.sub.3, α.sub.4, when he/she has all the pseudorandom numbers α.sub.0, α.sub.1, α.sub.2, α.sub.3, α.sub.4, the sum thereof is zero and can be removed.

[0068] Further, the pseudorandom number generation described above can be performed for each P.sub.i+4 in the same manner. Specifically, this 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

[0069] Below is a set of the pseudorandom numbers generated as described above.

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

[0070] The pseudorandom number table above has a property that the sum with respect to the first index (vertical direction) is zero and the sum with respect to the second index (horizontal direction) is not zero.

[0071] Further, by appropriately sharing the five seeds (seed.sub.i∈{0, 1}.sup.κ (i=0, 1, 2, 3, 4)), each secure computation server apparatus 200_i is able to generate the pseudorandom number set. In other words, the secure computation server apparatuses 200_i need not exchange each pseudorandom number α.sub.i, k and therefore need not determine whether or not it is the correct value.

Input

[0072] The input step (the step S3) is a step for distributing inputs, to be securely computed, to each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) and storing them therein. Here, we will assume that a party P.sub.i is an input dealer and shares [x] of x∈Z.sub.n are created. The process of the input step (the step S3) described below achieves Guaranteed Output Delivery (GOD) in the standard model by, for instance, providing the comparative verification part 201_i in the secure computation server apparatus 200_i, as shown in FIG. 5, and having the comparative verification part 201_i choose the correct value. Further, it is possible to realize the comparative verification part 201_i as the program executed in the hardware configuration described later.

[0073] The party P.sub.i computes r.sub.i, r.sub.i+1, r.sub.i+2, r.sub.i+3 using a pseudorandom function as follows:

r.sub.i=F.sub.n(vid.sub.i, seed.sub.i)

[0074] Then, P.sub.i computes x.sub.4 from x∈Z.sub.n using these r.sub.i, r.sub.i+1, r.sub.i+2, r.sub.i+3 as follows:

x.sub.4=x−r.sub.i−r.sub.i+1−r.sub.i+2+r.sub.i+3 mod n

[0075] Then, the party P.sub.i lets his/her own share [x].sub.i be [x].sub.i=(x.sub.i+1, x.sub.i+2, x.sub.i+3, x.sub.i+4)=(r.sub.i+1, r.sub.i+2, r.sub.i+3, r.sub.i+4). Meanwhile, the party P.sub.i sends x.sub.4 to the other parties P.sub.i+1, P.sub.i+2, P.sub.i+3, P.sub.i+4.

[0076] Here, in order to simplify the description, we will notate the parties P.sub.i+1, P.sub.i+2, P.sub.i+3, P.sub.i+4 as R.sub.j, R.sub.j+1, R.sub.j+2, R.sub.j+3, where R.sub.j+4=R.sub.j and R.sub.j−4=R.sub.j+3. Further, let h.sub.j, h.sub.j+1, h.sub.j+2, h.sub.j+3 be the hash values computed by R.sub.j, R.sub.j+1, R.sub.j+2, R.sub.j+3, respectively, for the received x.sub.i+4, where h.sub.i+4=h.sub.j. Here, the reason for computing the hash values is to make communication efficient, and any hash function that does not assume the random oracle property and has collision resistance can be fully utilized.

[0077] Each R.sub.j (k=j, j+1, j+2, j+3) sends x.sub.i+4 he/she received to R.sub.k−1 as m.sub.k. Further, each R.sub.j (k=j, j+1, j+2, j+3) sends h.sub.k to R.sub.k−2 and R.sub.k−3. Each R.sub.j compares his/her own h.sub.k with hash values h.sub.k+1, h.sub.k+2, and h.sub.k+3 of the received m.sub.k+1 and verifies whether three or more identical values are included. According to the result, one of the following processes is performed depending on the scenario.

(1) If only two or fewer identical values are included, P.sub.i is an adversary. Therefore, semi-honest secure four-party computation is executed with P.sub.i (and the initial inputs) excluded.
(2) If three or more identical values are included and m.sub.k is among them, m.sub.k is deemed to be the correct x.sub.i+4.
(3) If three or more identical values are included and m.sub.k is not among them, m.sub.k+1 is deemed to be the correct x.sub.i+4.

[0078] Finally, each R.sub.j (k=j, j+1, j+2, j+3; j=i+1 mod 5) obtains a share [x].sub.k as follows:

[00001]$\begin{array}{cc}{\left[x\right]}_k=\left(x_k,x_{k+1},x_{k+2},x_{k+3}\right)x_k=\{\begin{array}{c}{x}_{i+4}\left(k=i+4\right)\\ r_k\left(\mathrm{else}\right)\end{array}\mathrm{where}{r}_k=F_n\left({\mathrm{vid}}_k,{\mathrm{seed}}_k\right)& \left[\mathrm{Math}.2\right]\end{array}$

[0079] In the input method described above, by receiving the supposedly same (hash value of) x.sub.i+4 from at least three other parties P.sub.j and accepting a value sent by at least three parties as the correct value, even if there is an adversary among the other parties P.sub.j, the correct value can be determined. In other words, the correct computation can be obtained without interrupting the process even if there is an adversary, thereby achieving Guaranteed Output Delivery (GOD). Further, although a hash function is used in the above process, Guaranteed Output Delivery (GOD) is achieved in the standard model since security is not affected even if the input is inferred from the output.

Secure Computation (Multiplication)

[0080] The secure computation step (the step S4) is a step of performing desired computation on the shares distributed to and stored in each secure computation server apparatus 200_i (i=0, 1, 2, 3, 4) while maintaining secrecy. The following describes multiplication, which is an important factor in secure computation, followed by other instances of secure computation such as addition and constant multiplication. The process of the secure computation step (the step S4) described below achieves Guaranteed Output Delivery (GOD) in the standard model by, for instance, providing the comparative verification part 201_i in the secure computation server apparatus 200_i, as shown in FIG. 5, and having the comparative verification part 201_i choose the correct value. Further, it is possible to realize the comparative verification part 201_i as the program executed in the hardware configuration described later.

[0081] Here, we will compute [z]=[x.Math.y]=[x].Math.[y] from two shares [x], [y]. Further, we will assume that that x, y, and z are decomposed as follows.

[00002]$\begin{array}{cc}z=\underset{i=0}{\overset{4}{.Math.}}{z}_i\mathrm{mod}nx=\underset{i=0}{\overset{4}{.Math.}}{x}_i\mathrm{mod}ny=\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{Math}.3\right]\end{array}$

[0082] A party P.sub.i (i=0, 1, 2, 3, 4) computes tmp.sub.zk as shown below. Since the party P.sub.i lacks x.sub.k.Math.y.sub.i+4 to compute z.sub.k (cannot compute it from his/her share), P.sub.i computes this tmp.sub.zk instead.

[00003]$\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\ne i}{.Math.}{\alpha }_{j,k}\mathrm{mod}n\left(k=i,i+1,i+2,i+3\right)& \left[\mathrm{Math}.4\right]\end{array}$

[0083] Note that α.sub.j, k is a pseudorandom number generated in the pseudorandom number computation step (the step S2) and is used here. Note that, in the first index (vertical direction), what appears to be random numbers to a party P.sub.i are listed. Meanwhile, the second index (horizontal direction) lists those used to compute z.sub.k.

TABLE-US-00002 TABLE 2 P.sub.0 P.sub.1 P.sub.2 P.sub.3 P.sub.4 z.sub.0 α.sub.0, 0 α.sub.1, 0 α.sub.2, 0 α.sub.3, 0 α.sub.4, 0 z.sub.1 α.sub.0, 1 α.sub.1, 1 α.sub.2, 1 α.sub.3, 1 α.sub.4, 1 z.sub.2 α.sub.0, 2 α.sub.1, 2 α.sub.2, 2 α.sub.3, 2 α.sub.4, 2 z.sub.3 α.sub.0, 3 α.sub.1, 3 α.sub.2, 3 α.sub.3, 3 α.sub.4, 3 z.sub.4 α.sub.0, 4 α.sub.1, 4 α.sub.2, 4 α.sub.3, 4 α.sub.4, 4

[0084] Here, sender groups 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}, S.sub.i+3={P.sub.i+1, P.sub.i+2, P.sub.i+3} are defined. Then, the parties belonging to S.sub.k are able to compute x.sub.ky.sub.i+4 from their shares. Therefore, for instance, the parties P.sub.i+2, P.sub.i+3, 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, m.sub.k, i+4 where x.sub.k.Math.y.sub.i+4 is masked with the pseudorandom number α.sub.i, k above:

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

[0085] Then, of the parties P.sub.i+2, P.sub.i+3, 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 instance, the parties P.sub.i+2, P.sub.i+3 send m.sub.k, i+2, m.sub.k, i+3 as they are to the party P.sub.i, and the party P.sub.i+4 sends a hash value h.sub.k, i+4 of m.sub.k, i+4 to the party P.sub.i. Here, since m.sub.k, i+2, m.sub.k, i+3, m.sub.k, i+4 are masked with the pseudorandom number α.sub.i, k, x.sub.ky.sub.i+4 is not leaked. In other words, a hash function is used here to reduce the communication cost, not to ensure security. Further, the communication cost here is an amortized communication volume of a round and 2n [bits] to compute one z.sub.k. This is quadrupled to 8n [bits] since each party has four z.sub.k. Because there are five parties, this is further quintupled, totaling one round and 40n [bits].

[0086] Then, having received m.sub.k, i+2, m.sub.k, i+3, and the hash value h.sub.k, i+4 of m.sub.k, i+4, the party P.sub.i compares and verifies m.sub.k, i+2, m.sub.k, i+3, and the hash value h.sub.k, i+4 of m.sub.k, i+4. First, the party P.sub.i computes hash values h.sub.k, i+2, h.sub.k, i+3 of m.sub.k, i+2, m.sub.k, i+3. Then, P.sub.i deems m.sub.k, i+2 to be m.sub.k if h.sub.k, i+2=h.sub.k, i+3 or h.sub.k, i+2=h.sub.k, i+4. Meanwhile, P.sub.i deems m.sub.k, i+2 to be m.sub.k if h.sub.k, i+3=h.sub.k, i+4.

[0087] With x.sub.ky.sub.i+4 sent to the party P.sub.i as described above, even if there is an adversary among the other parties P.sub.j, P.sub.i can determine the correct value by receiving the supposedly same (hash value of) m.sub.k from at least three other parties P.sub.j and accepting a value sent by at least two parties as the correct value.

[0088] Then, the party P.sub.i computes z.sub.k=tmp.sub.zk+m.sub.k mod n (k=i, i+1, i+2, i+3) using m.sub.k determined to be the correct value.

[00004]$\begin{array}{cc}\begin{array}{c}{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\ne i}{.Math.}{\alpha }_{j,k}\right)+\left({\alpha }_{i,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.}}{\alpha }_{j,k}\end{array}& \left[\mathrm{Math}.5\right]\end{array}$

[0089] z.sub.k computed in this way contains additional terms, which function as the shares [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3) of the result of computing [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:

[00005]$\begin{array}{cc}\begin{array}{c}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.}}{\alpha }_{j,0}\right)+\left(x_1.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{\alpha }_{j,1}\right)+\\ \left(x_2.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{\alpha }_{j,4}\right)+\left(x_3.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{\alpha }_{j,3}\right)+\\ \left(x_4.Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{j=0}{\overset{4}{.Math.}}{\alpha }_{j,4}\right)\\ =\left(x_0+x_1+x_2+x_3+x_4\right).Math.\underset{j=0}{\overset{4}{.Math.}}{y}_j+\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{0,k}+\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{1,k}+\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{2,k}+\\ \underset{k=0}{\overset{4}{.Math.}}{\alpha }_{3,k}+\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{4,k}=x.Math.y\mathrm{mod}n\end{array}& \left[\mathrm{Math}.6\right]\end{array}$

[0090] Here, the reason that the pseudorandom numbers α.sub.i, k are removed is that the following relational expression holds due to the way the pseudorandom numbers are configured.

[00006]$\begin{array}{cc}\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{0,k}=\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{1,k}=\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{2,k}=\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{3,k}=\underset{k=0}{\overset{4}{.Math.}}{\alpha }_{4,k}=0& \left[\mathrm{Math}.7\right]\end{array}$

[0091] As mentioned in the description of the pseudorandom number computation step (the step S2), the pseudorandom numbers in the present configuration have the property that the sum with respect to the first index (vertical direction) is zero and the sum with respect to the second index (horizontal direction) is not zero. The additional terms appearing in the computation result of z.sub.k=tmp.sub.zk+m.sub.k mod n (k=i, i+1, i+2, i+3) are the sums with respect to the second index (horizontal direction), which are not zero, but it is ultimately possible to remove the effects of the additional terms (masks) using the property that the sum with respect to the first index (vertical direction) is zero when the result of computing [z]=[x.Math.y]=[x].Math.[y] is reconstructed. In other words, z.sub.k computed above contains additional terms, which function as the shares [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3) of the result of computing [z]=[x.Math.y]=[x].Math.[y].

[0092] With respect to the shares [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3) of the result of computing [z]=[x.Math.y]=[x].Math.[y] described above, by receiving the supposedly same (hash value of) m.sub.k from at least three other parties P.sub.j and accepting a value sent by at least two parties as the correct value, even if there is an adversary among the other parties P.sub.j, the correct value can be determined. In other words, the correct computation can be obtained without interrupting the process even if there is an adversary among the parties, thereby achieving Guaranteed Output Delivery (GOD). Further, although a hash function is used in the above process, Guaranteed Output Delivery (GOD) is achieved in the standard model since security is not affected even if the input is inferred from the output.

Secure Computation (Addition, Etc.)

[0093] In the secure computation step (the step S4), it is also possible to perform types of secure computation other than multiplication, such as addition and constant multiplication. The following describes these instances of secure computation that are not multiplication.

Constant Addition

[0094] Let us assume a situation in which a constant c∈Z.sub.n is shared by all the parties P.sub.i. In this case, constant addition [x]+c=[x+c] can be performed by computing [x+c].sub.i=(x′.sub.i, x′.sub.i+1, x′.sub.i+2, x′.sub.i+3) using [x].sub.i and c, where x′.sub.i=x.sub.0+x mod n (i=0), x′.sub.i=x.sub.i (i≠0).

Constant Multiplication

[0095] Let us assume another situation in which a constant c∈Z.sub.n is shared by all the parties P.sub.i. In this case, constant multiplication [x].Math.c=[x.Math.c] can be performed by computing [x.Math.c].sub.i=(x′.sub.i, x′.sub.i+1, x′.sub.i+2, x′.sub.i+3) using [x].sub.i and c, where x′.sub.i=c.Math.x.sub.i mod n.

Addition of Shares

[0096] Share addition [x]+[y]=[z] can be performed by computing [z].sub.i=(z.sub.i, z.sub.i+1, z.sub.i+2, z.sub.i+3), where z.sub.i=x.sub.i+y.sub.i mod n.

Dot Product

[0097] The dot product of vectors of shares is a simple extension of share multiplication, and z.sub.k can simply be sent all together since no local multiplication is necessary.

[00007]$\begin{array}{cc}\left[\underset{j=0}{\overset{m-1}{.Math.}}{x}^{\left(j\right)}.Math.y^{\left(j\right)}\right]\leftarrow \mathrm{DotProduct}\left({\left\{\left[x^{\left(j\right)}\right]\right\}}_{j=0}^{m-1},{\left\{\left[y^{\left(j\right)}\right]\right\}}_{j=0}^{m-1}\right)& \left[\mathrm{Math}.8\right]\end{array}$

Reconstruction

[0098] The reconstruction step (the step S5) is a step of reconstructing the shares resulting from the secure computation step (the step S4). The reconstruction step (the step S5) is essentially the same as the process in the first example embodiment, but the following describes a process incorporating a hash function. The process of the reconstruction step (the step S5) described below achieves Guaranteed Output Delivery (GOD) in the standard model by, for instance, providing the comparative verification part 201_i in the secure computation server apparatus 200_i, as shown in FIG. 5, and having the comparative verification part 201_i choose the correct value. Further, it is possible to realize the comparative verification part 201_i as the program executed in the hardware configuration described later.

[0099] Let us look at a case where a party P.sub.i receives the share value x.sub.i+4, which P.sub.i does not have, from the other parties P.sub.i+1, P.sub.i+2, P.sub.i+3 in order to reconstruct x. The parties P.sub.i+1, P.sub.i+2 send the value x.sub.i+4 as is to the party P.sub.i, and the party P.sub.i+3 sends the hash value h.sub.i+4 of the value x.sub.i+4 to the party P.sub.i. Then, the party P.sub.i computes a hash value of x.sub.i+4 received from the parties P.sub.i+1, P.sub.i+2 as h.sub.i+1 and a hash value of x.sub.i+4 received from the party P.sub.i+2 as h.sub.i+2.

[0100] At this time, if h.sub.i+1=h.sub.i+2 or h.sub.i+1=h.sub.i+3, then P.sub.i accepts x.sub.i+4 received from the party P.sub.i+1 as the correct value. Further, if h.sub.i+2=h.sub.i+3, then P.sub.i accepts x.sub.i+4 received from the party P.sub.i+2 as the correct value. As described, even if one of the received values is false, the correct value can be determined by accepting as the correct value a received value identical to at least another received value. Then, it is possible to reconstruct x by calculating x=x.sub.0+x.sub.1+x.sub.2+x.sub.3+x.sub.4 mod n using the correct value x.sub.i+4.

[0101] In the reconstruction method described above, by receiving the supposedly same (hash value of) x.sub.i+4 from at least three other parties P.sub.j and accepting a value sent by at least two parties as the correct value, even if there is an adversary among the other parties P.sub.j, the correct value is determined. In other words, the correct computation can be obtained without interrupting the process even if there is an adversary, thereby achieving Guaranteed Output Delivery (GOD). Further, although a hash function is used in the above process, Guaranteed Output Delivery (GOD) is achieved in the standard model since security is not affected even if the input is inferred from the output.

[0102] The typical steps of secure computation shown in FIG. 4 have been described, and as stated above, across all the steps, the correct computation can be obtained without interrupting the process even if there is an adversary, thereby achieving Guaranteed Output Delivery (GOD).

Hardware Configuration

[0103] FIG. 6 is a drawing illustrating an example of the hardware configuration of the secure computation server apparatus. In other words, FIG. 6 shows an example of the hardware configuration of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4). An information processing apparatus (computer) employing the hardware configuration shown in FIG. 6 can achieve the functions of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) by executing the secure computation method described above as a program.

[0104] It should be noted that the hardware configuration example shown in FIG. 6 is merely an example of the hardware configuration that achieves the functions of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4), and is not intended to limit the hardware configuration of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4). The secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) may include hardware not shown in FIG. 6.

[0105] As shown in FIG. 6, the hardware configuration 10 that may be employed by the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) comprises a CPU (Central Processing Unit) 11, a primary storage device 12, an auxiliary storage device 13, and an IF (interface) part 14. These elements are connected to each other by, for instance, an internal bus.

[0106] The CPU 11 executes each instruction included in the secure computation program executed by the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4). The primary storage device 12 is, for instance, a RAM (Random Access Memory) and temporarily stores various programs such as the secure computation program executed by the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) so that the CPU 11 can process the programs.

[0107] The auxiliary storage device 13 is, for instance, an HDD (Hard Disk Drive) and is capable of storing the various programs, such as the secure computation program executed by the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4), in the medium to long term. The various programs such as the secure computation program may be provided as a program product stored in a non-transitory computer-readable storage medium. The auxiliary storage device 13 can be used to store the various programs such as the secure computation program stored in the non-transitory computer-readable storage medium in the medium to long term. The IF part 14 provides an interface to the input and output between the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4).

[0108] The information processing apparatus employing the hardware configuration 10 described above can achieve the functions of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) by executing the secure computation method described above as a program.

[0109] Some or all of the example embodiments above can be described as (but not limited to) the following Supplementary Notes.

Supplementary Note 1

[0110] A secure computation system comprising at least five secure computation server apparatuses connected to each other via a network and performing secure computation on a value stored while being secret-shared, wherein [0111] each of the secure computation server apparatuses comprises: [0112] a comparative verification part that compares values, which should be the same, received from at least three secure computation server apparatuses and accepts a received value identical to at least another received value as a correct value.

Supplementary Note 2

[0113] The secure computation system according to Supplementary Note 1, wherein [0114] each of the secure computation server apparatuses further comprises: [0115] a pseudorandom function computation part that deterministically generates a pseudorandom number using a seed and an identifier as inputs and makes a set of masks that sum to zero with respect to a first index and sum to a nonzero value with respect to a second index by using the pseudorandom numbers, and [0116] wherein the received value is sent while being kept in secret with the mask.

Supplementary Note 3

[0117] The secure computation system according to Supplementary Note 2, wherein a share value of multiplication of two share values secret-shared by each of the secure computation server apparatuses includes the sum with respect to the second index as an additional term, and removing the mask using the fact that the sum with respect to the first index is zero when reconstructing the result of the multiplication.

Supplementary Note 4

[0118] The secure computation system according to any one of Supplementary Notes 1 to 3, wherein the comparative verification part determines that the received values are correct by verifying that hash values of the received values are the same.

Supplementary Note 5

[0119] A secure computation server apparatus out of at least five secure computation server apparatuses, connected to each other via a network, for performing secure computation on a value stored while being secret-shared, the secure computation server apparatus comprising: [0120] a comparative verification part that compares values, which should be the same, received from at least three secure computation server apparatuses and accepts a received value identical to at least another received value as a correct value.

Supplementary Note 6

[0121] A secure computation method comprising at least five secure computation server apparatuses connected to each other via a network and performing secure computation on a value stored while being secret-shared, wherein [0122] each of the secure computation server apparatuses compares values, which should be the same, received from at least three secure computation server apparatuses and accepts a received value identical to at least another received value as a correct value.

Supplementary Note 7

[0123] The secure computation method according to Supplementary Note 6 deterministically generating a pseudorandom number using a seed and an identifier as inputs, making a set of masks that sum to zero with respect to a first index and sum to a nonzero value with respect to a second index by using the pseudorandom numbers, and sending the received value being kept in secret with the mask.

Supplementary Note 8

[0124] The secure computation method according to Supplementary Note 7, wherein a share value of multiplication of two share values secret-shared by each of the secure computation server apparatuses includes the sum with respect to the second index as an additional term, and removing the mask using the fact that the sum with respect to the first index is zero when reconstructing the result of the multiplication.

Supplementary Note 9

[0125] The secure computation method according to any one of Supplementary Notes 6 to 8 determining that the received values are correct by verifying that hash values of the received values are the same.

Supplementary Note 10

[0126] A secure computation program causing at least five secure computation server apparatuses connected to each other via a network to perform secure computation on a value stored while being secret-shared, the secure computation program including: [0127] a process of comparing values, which should be the same, received from at least three secure computation server apparatuses and accepting a received value identical to at least another received value as a correct value.

[0128] Further, the disclosure of Non-Patent Literature cited above is incorporated herein in its entirety by reference thereto. It is to be noted that it is possible to modify or adjust the example embodiments or examples within the scope of the whole disclosure of the present invention (including the Claims) and based on the basic technical concept thereof. Further, it is possible to variously combine or select (or partially omit) a wide variety of the disclosed elements (including the individual elements of the individual claims, the individual elements of the individual example embodiments or examples, and the individual elements of the individual figures) within the scope of the whole disclosure of the present invention. That is, it is self-explanatory that the present invention includes any types of variations and modifications to be done by a skilled person according to the whole disclosure including the Claims and the technical concept of the present invention. Particularly, any numerical ranges disclosed herein should be interpreted that any intermediate values or subranges falling within the disclosed ranges are also concretely disclosed even without specific recital thereof. In addition, using some or all of the disclosed matters in the literatures cited above as necessary, in combination with the matters described herein, as part of the disclosure of the present invention in accordance with the object of the present invention shall be considered to be included in the disclosed matters of the present application.

REFERENCE SIGNS LIST

[0129] 100, 200: secure computation system
100_i, 200_i: secure computation server apparatus
101_i, 201_i: comparative verification part
202_i: pseudorandom function computation part
10: hardware configuration

11: CPU (Central Processing Unit)

[0130] 12: primary storage device
13: auxiliary storage device
14: IF (interface) part