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

Abstract

A secure computation server apparatus in a secure computation system includes: a table storage part that stores a table of secret shares of the product of a first value and a second value for combinations of shares of possible values of the first value and shares of possible values of the second value; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

Claims

1. A secure computation system, comprising a plurality of secure computation server apparatuses connected to each other via a network and performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein each of the secure computation server apparatuses includes: a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

2. The secure computation system according to claim 1, wherein the secret sharing is achieved by using an (N?3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which the permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses.

3. The secure computation system according to claim 2, wherein the comparative verification part accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.

4. The secure computation system according to claim 2, wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.

5. The secure computation system according to claim 2, wherein the shuffling is a composition of .sub.NC.sub.t sequences of the mini-shuffles with .sub.NC.sub.t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.

6. The secure computation system according to claim 1, wherein the comparative verification part verifies that the received value is a correct value by verifying that hash values of the plurality of received data are identical.

7. A secure computation server apparatus out of a plurality of secure computation server apparatuses connected to each other via a network to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, the secure computation server apparatus including: a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

8. A secure computation method, with a plurality of secure computation server apparatuses connected to each other via a network, performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein each of the secure computation server apparatuses: stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; shuffles indices of possible values of the first value and indices of possible values of the second value in the table; selects an element in the table whose indices in the shuffled table match the first and the second values; and accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

9. The secure computation method according to claim 8, wherein the secret sharing is achieved by using an (N?3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which the permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses.

10. A non-transient computer readable medium storing a secure computation program causing a plurality of secure computation server apparatuses connected to each other via a network to execute processing to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, the secure computation program: stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; shuffles indices of possible values of the first value and indices of possible values of the second value in the table; selects an element in the table whose indices in the shuffled table match the first and the second values; and accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

11. The secure computation server apparatus according to claim 7, wherein the secret sharing is achieved by using an (N?3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which the permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses.

12. The secure computation server apparatus according to claim 11, wherein the comparative verification part accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.

13. The secure computation server apparatus according to claim 11, wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.

14. The secure computation server apparatus according to claim 11, wherein the shuffling is a composition of .sub.NC.sub.t sequences of the mini-shuffles with .sub.NC.sub.t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.

15. The secure computation method according to claim 9, wherein each of the secure computation server apparatuses accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.

16. The secure computation server method according to claim 9, wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.

17. The secure computation server method according to claim 9, wherein the shuffling is a composition of .sub.NC.sub.t sequences of the mini-shuffles with .sub.NC.sub.t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.

18. The non-transient computer readable medium storing the secure computation program according to claim 10, wherein the secret sharing is achieved by using an (N?3t)-out-of-N replicated secret sharing scheme, and the shuffling is a composition of mini-shuffles in which the permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses.

19. The non-transient computer readable medium storing the secure computation program according to claim 18, wherein the secure computation program accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.

20. The non-transient computer readable medium storing the secure computation program according to claim 18, wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

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

[0019] 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.

[0020] FIG. 3 is a flowchart showing an outline of the procedure of a secure computation method relating to the first example embodiment.

[0021] FIG. 4 is a block diagram showing an example of the functional configuration of a secure computation system relating to a second example embodiment.

[0022] FIG. 5 is a flowchart showing an outline of the procedure of a secure computation method relating to the second example embodiment.

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

EXAMPLE EMBODIMENTS

[0024] 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

[0025] The following describes a secure computation system and a 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.

[0026] FIG. 1 is a block diagram showing an example of the functional configuration of the secure computation system relating to the first example embodiment. As shown in FIG. 1, the secure computation system 100 relating to the first example embodiment comprises 0-th to (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) (N is a natural number). The 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) 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.

[0027] The secure computation system 100 comprising the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) is able to compute desired shares of a value supplied by any one of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) as an input while keeping the input value and the values during the computation process secret, and distribute the computation results to the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) to store them therein.

[0028] Further, the secure computation system 100 comprising the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) is able to compute desired shares of shares distributed to and stored in the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) while keeping the values during the computation process secret, and distribute the computation results to the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) to store them therein.

[0029] Further, the shares that resulted from the computations above may be reconstructed by having the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) exchange the shares with each other. Alternatively, the shares may be reconstructed by transmitting them to an external apparatus, instead of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1).

[0030] Each of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) is operated by an independent party P.sub.i (i=0, 1, . . . , N?1). Further, the secure computation system 100 comprising the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) is able to continue correct secure computation without interrupting the process even when some of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) are operated by adversaries.

[0031] For instance, each of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) may employ the following configuration.

[0032] Shares of a residue class ring Z.sub.L of modulo L for each party P.sub.i (i=0, 1, . . . , N?1) are defined as follows.

[0033] The shares over the residue class ring Z.sub.L of an element x?Z.sub.L of the residue class ring Z.sub.L of modulo L are expressed as below:

[x].sub.L=([x].sub.L,0, [x].sub.L,1, . . . , [x].sub.L,N?1)

Decompose the element x?Z.sub.L of the residue class ring Z.sub.L of modulo L to satisfy the relationship with:

x=x.sub.0+x.sub.1+ . . . +x.sub.N?1 mod L,

and define [x].sub.L, i distributed to and held by each party P.sub.i (i=0, 1, . . . , N?1) as follows. In other words, the degree of replication is 3t+1, where t is the permissible number of adversaries and a natural number that satisfies t(3t+1)<N.

[x].sub.L,i=(x.sub.i, x.sub.i+1, . . . , x.sub.i+3t), where x.sub.(N?1)+1=x.sub.0

[0034] When the shares [x].sub.L,0, [x].sub.L,1, . . . , [x].sub.L,N?1 held by each party P.sub.i (i=0, 1, . . . , N?1) are defined as above, each party P.sub.i (i=0, 1, . . . , N?1) cannot reconstruct x from one of the shares [x].sub.L,0, [x].sub.L,1, . . . , [x].sub.L,N?1 that he/she holds. Meanwhile, there is a secret sharing scheme in which x can be reconstructed by combining the shares held by at least t+1 of the parties P.sub.i (i=0, 1, . . . , N?1). This secret sharing scheme is called an (N?3t)-out-of-N replicated secret sharing scheme.

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

[0036] Therefore, in the present example embodiment, the secure computation server apparatus 110.sub.i comprises a table storage part 111, a table shuffle part 112, a multiplication part 113, and a comparative verification part 114, as shown in FIG. 2, to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value. FIG. 2 is a block diagram showing an example of the functional configuration of the secure computation server apparatus according to the first example embodiment.

[0037] More concretely, the following process example is conceivable.

[0038] The table storage part 111 stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value. Here, the table is obtained by secret-sharing a so-called multiplication table. For instance, when the shares of the first value are [i.sub.x].sub.L (i.sub.x?Z.sub.L) and the shares of the second value are [j.sub.y].sub.L (j.sub.y?Z.sub.L), we get the following table. Although the table storage part 111 may store the table below in advance, it is sufficient to store [Z.sub.i,j;]=[i.sub.xj.sub.y] in a variable as needed during actual implementation since this table can be easily constructed from ordinary multiplication.

TABLE-US-00001 TABLE 1 [0] [1] . . . [i] . . . [L ? 1] [0] [1] . . . . . . [j] . . . [Z.sub.i, j] = [i.sub.x j.sub.y] . . . [L ? 1]

[0039] With the table shown above, the secret shares [i.sub.xj.sub.y] of the product of the first value i.sub.x and the second value j.sub.y can be obtained from the shares [i.sub.x] of the first value and the shares [j.sub.y] of the second value. Referring to the table directly, however, is problematic in secure computation because the share values [i.sub.xj.sub.y] leak from the reference location in the table.

[0040] Therefore, the table shuffle part 112 shuffles the indices i of possible values of the first value ix and the indices j of possible values of the second value j.sub.y in the table. Here, we'll say that, by performing this shuffling, an index i is replaced with an index p, and an index j is replaced with an index q. Then, the shuffled table does not have row and column information, as shown below, for instance.

TABLE-US-00002 TABLE 2 . . . [p] . . . . . . . . . [q] . . . [Z.sub.p, q] . . .

[0041] As a result, it is not clear which row j.sub.y and which column i.sub.x should be referred to in order to obtain the secret shares [i.sub.xj.sub.y] of the product of the first value i.sub.x and the second value j.sub.y since now each party does not know which index p replaced the index i and which index q replaced the index j.

[0042] Then, the multiplication part 113 obtains the secret shares [i.sub.xj.sub.y] of the product of the first value i.sub.x and the second value j.sub.y by selecting a table element whose indices in the shuffled table match the first and the second values. In other words, since a pair of the indices (p, q) in the shuffled table matches the first and the second values (i.sub.x, j.sub.y), [Z.sub.p,q] of the matched indices (p, q) is the secret shares [i.sub.xj.sub.y] of the product of the first value i.sub.x and the second value j.sub.y.

[0043] Further, whether or not the indices (p, q) in the shuffled table match the first and the second values (i.sub.x, j.sub.y) may be determined and securely computed using the shares [i.sub.x] of the first value and the shares [j.sub.y] of the second value as inputs and shares ([p], [q]) of the indices in the shuffled table. One only needs to calculate ([i.sub.x?p], [j.sub.y?q]) and see if it equals ([0], [0]).

[0044] Meanwhile, as stated above, the computation above also requires a party to receive from another party a share value that he/she does not have. In such a situation in which a party receives from another party a share value that he/she does not have, there may be an adversary among the parties who may transmit the wrong value, instead of the correct value.

[0045] Therefore, the comparative verification part 114 accepts data that a majority agrees on as a correct value out of a plurality of data received from other secure computation server apparatuses. As stated above, the present configuration example uses a secret sharing scheme with a replication degree of 3t+1. This means that 3t+1 parties hold the same share element. In other words, when a party receives a share value that he/she does not have from another party, the same element can be received from 3t+1 parties, and out of a plurality of values received, data that a majority agrees on is accepted as a correct value. Therefore, in the configuration of the first example embodiment, it is possible to continue to perform correct secure computation without interrupting the process even if some of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) are operated by adversaries.

[0046] As described, in the secure computation system 100 relating to the first example embodiment, each of the 0-th to the (N?1)-th secure computation server apparatuses .sub.i (i=0, 1, . . . , N?1) comprises the table storage part 111, the table shuffle part 112, the multiplication part 113, and the comparative verification part 114 to perform secure computation of secret shares of the product of the secret-shared first value and the secret-shared second value from shares of the first value and shares of the second value. Further, in the secure computation system 100 relating to the first example embodiment, by having each of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) configured as above, it is possible to continue to perform correct secure computation without interrupting the process even if some of the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) are operated by adversaries. Moreover, a number of the secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N-1) that satisfies t(3t+1)<N can be employed. In other words, each of the secure computation system 100 and the 0-th to the (N?1)-th secure computation server apparatuses 110.sub.i (i=0, 1, . . . , N?1) relating to the first example embodiment can contribute to improving the security and flexibility of secure computation technology.

(Secure Computation Method)

[0047] FIG. 3 is a flowchart showing an outline of the procedure of a secure computation method relating to the first example embodiment. The procedure of the secure computation method shown in FIG. 3 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. 3, the secure computation method relating to the first example embodiment has a table storage step (step S1), a table shuffle step (step S2), a multiplication step (step S3), and a comparative verification step (step S4).

[0049] In the table storage step (the step S1), the secure computation server apparatus 110.sub.i stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value. Here, the table is obtained by secret-sharing a multiplication table, as stated above. Since this table can be easily constructed from ordinary multiplication, it is sufficient to store it in variables as needed during actual implementation. Further, the table can be constructed in so-called offline processing without waiting for input.

[0050] In the table shuffle step (the step S2), the secure computation server apparatus 110.sub.i shuffles the indices of possible values of the first value and the indices of possible values of the second value in the table. The shuffled table loses the row and column information.

[0051] In the multiplication step (the step S3), the secure computation server apparatus 110.sub.i obtains the secret shares [i.sub.xj.sub.y] of the product of the first value i.sub.x and the second value j.sub.y by selecting a table element whose indices in the shuffled table match the first and the second values.

[0052] Meanwhile, in the comparative verification step (the step S4), the secure computation server apparatus 110.sub.i accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses. Note that the comparative verification step (the step S4) is executed when a party receives from another party a share value that he/she does not have. In other words, as part of the table shuffle step (the step S2) and the multiplication step (the step S3), the comparative verification step is executed each time a party receives from another party a share value that he/she does not have.

[0053] As described, the secure computation method relating to the first example embodiment has the table storage step (the step 1), the table shuffle step (the step 2), the multiplication step (the step 3), and the comparative verification step (the step 4) to perform secure computation of secret shares of the product of the secret-shared first value and the secret-shared second value from shares of the first value and shares of the second value. Further, in the secure computation method relating to the first example embodiment, by executing the processes described above, it is possible to continue to perform correct secure computation without interrupting the process even if some of the secure computation server apparatuses 110.sub.i are operated by adversaries. Moreover, a number of the secure computation server apparatuses 110.sub.i that satisfies t(3t+1)<N can be employed. In other words, the secure computation method relating to the first example embodiment can contribute to improving the security and flexibility of secure computation technology.

[0054] In the first example embodiment described above, only the basic concept of the present invention was discussed. 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

[0055] The following describes a secure computation system relating to the second example embodiment with reference to FIG. 4.

[0056] FIG. 4 is a block diagram showing an example of the functional configuration of the secure computation system relating to the second example embodiment. As shown in FIG. 4, the secure computation system 200 relating to the second example embodiment comprises 0-th to (N?1)-th secure computation server apparatuses 210.sub.i (i=0, 1, . . . , N?1). The 0-th to the (N?1)-th secure computation server apparatuses 210.sub.i (i=0, 1, . . . , N?1) are connected to each other via a network so as to be able to communicate with each other.

[0057] Each of the 0-th to the (N?1)-th secure computation server apparatuses 210.sub.i (i=0, 1, . . . , N?1) is operated by an independent party P.sub.i (i=0, 1, . . . , N?1). Further, the secure computation system 200 comprising the 0-th to the (N?1)-th secure computation server apparatuses 210.sub.i (i=0, 1, . . . , N?1) is able to continue correct secure computation without interrupting the process even when some of the 0-th to the (N?1)-th secure computation server apparatuses 210.sub.i (i=0, 1, . . . , N?1) are operated by adversaries.

Preparation

[0058] For instance, the secure computation system 200 relating to the second example embodiment may employ the following configuration.

[0059] As in the first example embodiment, the secure computation system 200 relating to the second example embodiment may employ the (N?3t)-out-of-N replicated secret sharing scheme. In other words, the shares over the residue class ring Z.sub.L of an element x?Z.sub.L of the residue class ring Z.sub.L of order L are configured as below:

[x].sub.L=([x].sub.L,0, [x].sub.L,1, . . . , [x].sub.L, N?1)

x=x.sub.0+x.sub.1+ . . . +x.sub.N?1 mod L

[x].sub.L,i=(x.sub.i, x.sub.i+1, . . . , x.sub.i+3t) where x.sub.(N?1)+1=x.sub.0

[0060] Here, P(x.sub.i) is defined as a set of parties holding an element x.sub.i of the secret shares described above. As can be seen from the definitions, the number of elements in the set is: |P(x.sub.i)|=3t+1.

[0061] Further, each party P.sub.i has (k.sub.i, . . . , k.sub.i+3t) as seeds, where k.sub.i?{0, 1}.sup.?.

[0062] In addition, a party belonging to P(x.sub.i)?N.sub.j has an additional seed k.sub.x,j for shuffling described later. Note that N.sub.j is a set of any t parties (j=0, 1, . . . , .sub.NC.sub.t?1).

[0063] A pseudorandom function F.sub.L outputs Z.sub.L using the seeds as inputs as follows:

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

[0064] Further, with an M-length array x=(x.sub.0, . . . , x.sub.j, . . . , x.sub.M?1), x.sub.j is decomposed as follows: x.sub.j=x.sub.j,0+x.sub.j,1, +. . . +x.sub.j,N?1, mod L. Then, x.sub.i=(x.sub.0,i, . . . , x.sub.M?1, i).

Building Blocks

[0065] The following describes building blocks used as elements to perform secure computation of secret shares of the product of the secret-shared first value and the secret-shared second value from shares of the first value and shares of the second value in the secure computation system 200 relating to the second example embodiment.

Reconstruction

[0066] Here, we will consider a case where a party P.sub.i reconstructs x?Z.sub.L from [x].sub.L.

[0067] The party P.sub.i needs x.sub.1, . . . , x.sub.i?1, x.sub.i+(3t+1), . . . , x.sub.N?1, in order to reconstruct x?Z.sub.L. In other words, since the party P.sub.i has [x].sub.L,i=(x.sub.i, x.sub.i+1, . . . , x.sub.i+3t), he/she needs the rest: x.sub.1, . . . , x.sub.i?1, x.sub.i+(3t+1), . . . , x.sub.N?1.

[0068] Now, let's take a look at a set P(x.sub.j) of parties holding a share element x.sub.j(j=1, . . . , i?1, i+(3t+1), . . . , N?1). Then, a party P.sub.z?P(x.sub.j) transmits x.sub.j to the party P.sub.i. Note that this transmission process is executed for each share element x.sub.j(j=1, . . . , i?1, i+(3t+1), . . . , N?1).

[0069] Meanwhile, the party P.sub.i compares and verifies the values transmitted by the parties belonging to the set P(x.sub.j) and selects x.sub.j that a majority agrees on as a correct value. Since |P(x.sub.i)|=3t+1, he/she can always select x.sub.j that a majority agrees on as a correct value, as long as the number of adversaries is not greater than t. Further, the communication cost can be reduced by making the values transmitted by some of the parties belonging to the set P(x.sub.j) hash values.

[0070] Finally, the party P.sub.i verifies x.sub.1, . . . , x.sub.i?1. x.sub.i+(3t+1), . . . , x.sub.N?1 as the correct values by comparing them with [x].sub.L,i=(x.sub.i, x.sub.i+1, . . . , x.sub.1+3t) and calculates x=?.sub.i+0.sup.N?1x.sub.i mod L using the confirmed values. This x is the desired value.

Input

[0071] Now, let's consider a case where the party P.sub.i supplies x?Z.sub.L as an input. The output in this case is [x].sub.L.

[0072] First, the party P.sub.i generates random numbers x.sub.1, . . . , x.sub.N?1?Z.sub.L and then lets x.sub.0 be x.sub.0=x??.sub.i=1.sup.N-1x.sub.i mod L.

[0073] Next, the party P.sub.i transmits [x].sub.L,i to the other parties P.sub.i (j?i).

[0074] All the parties P.sub.i generates [r].sub.L from the seeds and the pseudorandom function. More concretely, when r.sub.i=F.sub.L(uid, k.sub.i) and r=?.sub.i=1.sup.N?1r.sub.i mod L, shares of the random number r may be created without any communication. It should be noted that nobody knows the value of r at this time.

[0075] Then, all the parties P.sub.i calculate [x+r].sub.L=[x].sub.L+[r].sub.L. Note that the addition of the shares [x].sub.L+[y].sub.L=[z].sub.L can be done by calculating [z].sub.L=([z].sub.L,0, [z].sub.L,1, . . . , [z].sub.L,N?t) so that z.sub.i=x.sub.i+y.sub.i mod L.

[0076] Then, all the parties P.sub.i reconstruct [x +r].sub.L to obtain x+r. The building block [Reconstruction] described above can be used for the reconstruction here.

[0077] Now the values of x+r obtained by reconstructing [x+r].sub.L by all the parties P.sub.i are exchanged and compared to verify the received value of x+r. Then, a value that a majority agrees on is selected from the received values of x+r as a correct value. If no majority is established, the party P.sub.i who is the input dealer is an adversary. Therefore, the party P.sub.i and x?Z.sub.L supplied by the party P.sub.i as the input are eliminated. Note that, when the values of x+r are exchanged, it is possible to reduce the communication cost by using hash values in some of the communication.

[0078] Finally, [x].sub.L=x+r?[r].sub.L is obtained as an output.

Shuffle

[0079] The shuffle here is a composition of mini-shuffles in which permutation for t parties is computed locally by the other parties. Therefore, the following first describes how to configure these mini-shuffles.

[0080] Firstly, a permutation that is unknown to t parties but known to the other parties is configured. As stated above, when N, is a set of any t parties (j=0, 1, . . . , .sub.NC.sub.t?1), the parties belonging to P(x.sub.i)?N.sub.j share the seed k.sub.x,j. Therefore, a permutation using a pseudorandom number generated from the seed k.sub.x,j is unknown to the (t) parties belonging to N.sub.j but known to the other parties belonging to P(x.sub.i)?N.sub.j.

[0081] Then, by applying this permutation it configured by themselves to a share element x.sub.i, the parties belonging to P(x.sub.i)?N.sub.j are able to calculate ?(x.sub.i) locally (without any communication).

[0082] Meanwhile, since the (t) parties belonging to N.sub.j cannot calculate ?(x.sub.i), they ask for the transmission of ?(x.sub.i) calculated by the parties belonging to P(x.sub.i)?N.sub.j. At this time, from |P(x.sub.i)|=3t+1 and |N.sub.j|=t, it can be seen that the number of the parties belonging to P(x.sub.i)?N.sub.j is 2t+1. This means that, even when there are t adversaries among the parties belonging to P(x.sub.i)?N.sub.j, they form a minority among 2t+1 parties.

[0083] Therefore, the (t) parties belonging to N.sub.j compare and verify ?(x.sub.i) received from the parties belonging to P(x.sub.i)?N.sub.j and accept one that at least t+1 parties agree on as a correct value. Note that it is possible to reduce the communication cost by transmitting the permutation of the shares sent from the parties belonging to P(x.sub.i)?N.sub.j to those belonging to N.sub.j as a hash value.

[0084] By performing such permutation on all x.sub.i, one can constitute a mini-shuffle in which permutation for t parties is computed locally by the other parties.

[0085] Here, the mini-shuffle configured as described above functions as a shuffle for the parties belonging to N.sub.j since they are not able to track the destination of the permutation. Meanwhile, it does not function as a shuffle for the parties belonging to P(x.sub.i)?N.sub.j since they are able to track the destination of the permutation.

[0086] Therefore, a shuffle is constituted by a composition of .sub.NC.sub.t mini-shuffles (.sub.NC.sub.t is the number of sets of t selected parties). Then, out of the combined mini-shuffles, every party has one that functions as a shuffle since he/she cannot track the destination of the permutation.

Multiplication

[0087] FIG. 5 is a flowchart showing an outline of the procedure of a secure computation method relating to the second example embodiment. In other words, the flowchart in FIG. 5 shows a method for performing secure computation of secret shares of the product of the secret-shared first value and the secret-shared second value from shares of the first value and shares of the second value using the building blocks.

[0088] As shown in FIG. 5, the secure computation method relating to the second example embodiment has a table storage step (step S11), a table shuffle step (step S12), a multiplication step (step S13), and a comparative verification step (step S14).

[0089] In the table storage step (the step S11), the secure computation server apparatus 210.sub.i stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value. Here, the same table described in the first example embodiment may be used.

[0090] In the table shuffle step (the step S12), the secure computation server apparatus 210.sub.i shuffles the indices of possible values of the first value and the indices of possible values of the second value in the table. The shuffling here may be executed as in [Shuffle] of the building blocks described above.

[0091] Then, in the multiplication step (the step S13), the secure computation server apparatus 210.sub.i obtains the secret shares of the product of the first value and the second value by selecting a table element whose indices in the shuffled table match the first and the second values. This process may also be the same as the one described in the first example embodiment.

[0092] Further, in the comparative verification step (the step S14), the secure computation server apparatus 210.sub.i accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses. As is evident from the description of the building blocks above, the comparative verification step is also incorporated as internal processing into the shuffle and the reconstruction.

[0093] As described, the secure computation method relating to the second example embodiment has the table storage step (the step 11), the table shuffle step (the step 12), the multiplication step (the step 13), and the comparative verification step (the step 14) to perform secure computation of secret shares of the product of the secret-shared first value and the secret-shared second value from shares of the first value and shares of the second value. Further, in the secure computation method relating to the second example embodiment, by executing the processes described above, it is possible to continue to perform correct secure computation without interrupting the process even if some of the secure computation server apparatuses 210.sub.i are operated by adversaries. Moreover, a number of the secure computation server apparatuses 210, that satisfies t(3t+1)<N can be employed. In other words, the secure computation method relating to the second example embodiment can contribute to improving the security and flexibility of secure computation technology.

Hardware Configuration

[0094] 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 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1). An information processing apparatus (computer) employing the hardware configuration shown in FIG. 6 can achieve the functions of the secure computation server apparatuses 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1) by executing the secure computation method described above as a program.

[0095] 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 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1), and is not intended to limit the hardware configuration of the secure computation server apparatuses 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1). The secure computation server apparatuses 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1) may include hardware not shown in FIG. 6.

[0096] As shown in FIG. 6, the hardware configuration 10 that may be employed by the secure computation server apparatuses 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1) 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.

[0097] The CPU 11 executes each instruction included in the secure computation program executed by the secure computation server apparatuses 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1). 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 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1) so that the CPU 11 can process the programs.

[0098] 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 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1), 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 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1).

[0099] The information processing apparatus employing the hardware configuration 10 described above can achieve the functions of the secure computation server apparatuses 110.sub.i and 210.sub.i (i=0, 1, . . . , N?1) by executing the secure computation method described above as a program.

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

Supplementary Note 1

[0101] A secure computation system comprising a plurality of secure computation server apparatuses connected to each other via a network and performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein [0102] each of the secure computation server apparatuses includes: [0103] a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; [0104] a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; [0105] a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and [0106] a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

Supplementary Note 2

[0107] The secure computation system according to Supplementary Note 1, wherein [0108] the secret sharing is achieved by using an (N-3t)-out-of-N replicated secret sharing scheme, and [0109] the shuffling is a composition of mini-shuffles in which the permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses.

Supplementary Note 3

[0110] The secure computation system according to Supplementary Note 2, wherein the comparative verification part accepts as a correct value a share permutation that at least t+1 apparatuses agree on out of share permutations received from the other secure computation server apparatuses.

Supplementary Note 4

[0111] The secure computation system according to Supplementary Note 2 or 3, wherein the mini-shuffle locally computed by the other secure computation server apparatuses is configured by using a pseudorandom number generated from a seed not held by the t secure computation server apparatuses but shared by the other secure computation server apparatuses.

Supplementary Note 5

[0112] The secure computation system according to any one of Supplementary Notes 2 to 4, wherein the shuffling is a composition of .sub.NC.sub.t sequences of the mini-shuffles with .sub.NC.sub.t being the number of sets of the t secure computation server apparatuses selected from N secure computation server apparatuses.

Supplementary Note 6

[0113] The secure computation system according to any one of Supplementary Notes 1 to 4, wherein the comparative verification part verifies that the received value is a correct value by verifying that hash values of the plurality of received data are identical.

Supplementary Note 7

[0114] A secure computation server apparatus out of a plurality of secure computation server apparatuses connected to each other via a network to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, the secure computation server apparatus including: [0115] a table storage part that stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; [0116] a table shuffle part that shuffles indices of possible values of the first value and indices of possible values of the second value in the table; [0117] a multiplication part that selects an element in the table whose indices in the shuffled table match the first and the second values; and [0118] a comparative verification part that accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

Supplementary Note 8

[0119] A secure computation method, with a plurality of secure computation server apparatuses connected to each other via a network, performing secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, wherein [0120] each of the secure computation server apparatuses: [0121] stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; [0122] shuffles indices of possible values of the first value and indices of possible values of the second value in the table; [0123] selects an element in the table whose indices in the shuffled table match the first and the second values; and [0124] accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

Supplementary Note 9

[0125] The secure computation method according to Supplementary Note 8, wherein [0126] the secret sharing is achieved by using an (N?3t)-out-of-N replicated secret sharing scheme, and [0127] the shuffling is a composition of mini-shuffles in which the permutation of shares for t apparatuses out of the secure computation server apparatuses is computed locally by other secure computation server apparatuses out of the secure computation server apparatuses.

Supplementary Note 10

[0128] A secure computation program causing a plurality of secure computation server apparatuses connected to each other via a network to execute processing to perform secure computation of secret shares of the product of a secret-shared first value and a secret-shared second value from shares of the first value and shares of the second value, the secure computation program: [0129] stores a table of secret shares of the product of the first value and the second value for combinations of shares of possible values of the first value and shares of possible values of the second value; [0130] shuffles indices of possible values of the first value and indices of possible values of the second value in the table; [0131] selects an element in the table whose indices in the shuffled table match the first and the second values; and [0132] accepts data that a majority of other secure computation server apparatuses agrees on as a correct value out of a plurality of data received from the other secure computation server apparatuses.

[0133] 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

[0134] 100, 200: secure computation system [0135] 110.sub.i, 210.sub.i: secure computation server apparatus [0136] 111: table storage part [0137] 112: table shuffle part [0138] 113: multiplication part [0139] 114: comparative verification part [0140] 10: hardware configuration [0141] 11: CPU (Central Processing Unit) [0142] 12: primary storage device [0143] 13: auxiliary storage device [0144] 14: IF (interface) part