SHUFFLE SYSTEM, SHUFFLE METHOD, AND PROGRAM

Abstract

Among four secure computation nodes, one secure computation node is selected as a receiving node. Two of three remaining secure computation nodes among the four secure computation nodes are operated as resharing nodes, and a remaining secure computation node is operated as a verifying node. The resharing node(s) performs a mini-shuffle for resharing share(s) held therein by using a permutation that the receiving node does not know and transmits a result(s) of the mini-shuffle to the receiving node. The verifying node computes data to verify the result(s) of the mini-shuffle performed by the resharing node(s) by using a permutation that the receiving node does not know and transmits the data to the receiving node. Shuffling of shares is achieved by repeatedly performing a round as described above so that each of the four secure computation nodes is selected as the receiving node at least once.

Claims

1. A shuffle system for shuffling shares, that is configured to perform a round including processes of: selecting one of four secure computation nodes as a receiving node, and causing two of three remaining secure computation nodes among the four secure computation nodes to operate as resharing nodes and a remaining secure computation node to operate as a verifying node, and repeat the round so that each of the four computation nodes is selected as the receiving node at least once, wherein, in the round, the resharing node(s) performs a mini-shuffle for resharing share(s) held therein by using a permutation that the receiving node does not know and transmits a result(s) of the mini-shuffle to the receiving node, and wherein, in the round, the verifying node computes data to verify the result(s) of the mini-shuffle performed by the resharing node(s) by using a permutation that the receiving node does not know and transmits the data to the receiving node.

2. The shuffle system according to claim 1; wherein the receiving node determines whether the mini-shuffle is valid by using the data received from the verifying node; and wherein, if the receiving node determines that the mini-shuffle is not valid, the receiving node aborts performing the processes.

3. The shuffle system according to claim 1; wherein the four secure computation nodes include: a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form; a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form; a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form; wherein the resharing nodes and the verifying node generate two random values by using a seed(s) that the receiving node does not know; wherein the resharing node(s) transmits a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node; and wherein the verifying node computes a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmits a computed result to the receiving node.

4. The shuffle system according to claim 3; wherein a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node are performed in parallel, and wherein a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node are performed in parallel.

5. A shuffle method for shuffling shares, comprising: repeatedly performing a round so that each of four secure computation nodes is selected as a receiving node at least once; wherein the round includes: selecting one of the four secure computation nodes as a receiving node, and causing two of three remaining secure computation nodes among the four secure computation nodes to operate as resharing nodes and a remaining secure computation node to operate as a verifying node, wherein, in the round, the resharing node(s) performs a mini-shuffle for resharing share(s) held therein by using a permutation that the receiving node does not know and transmits a result(s) of the mini-shuffle to the receiving node, and wherein, in the round, the verifying node computes data to verify the result(s) of the mini-shuffle performed by the resharing node(s) by using a permutation that the receiving node does not know and transmits the data to the receiving node.

6. A non-transitory computer-readable medium storing therein a program causing each of four secure computation nodes to execute a process of repeatedly performing a round so that each of the four secure computation nodes is selected as a receiving node at least once; wherein the round includes: selecting one of the four secure computation nodes as a receiving node, and causing two of three remaining secure computation nodes among the four secure computation nodes to operate as resharing nodes and a remaining secure computation node to operate as a verifying node, wherein, in the round, the resharing node(s) performs a mini-shuffle for resharing share(s) held therein by using a permutation that the receiving node does not know and transmits results of the mini-shuffle to the receiving node, and wherein, in the round, the verifying node computes data to verify the result(s) of the mini-shuffle performed by the resharing node(s) by using a permutation that the receiving node does not know and transmits the data to the receiving node.

7. The shuffle system according to claim 2; wherein the four secure computation nodes include: a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form; a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form; a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form; wherein the resharing nodes and the verifying node generate two random values by using a seed(s) that the receiving node does not know; wherein the resharing node(s) transmits a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node; and wherein the verifying node computes a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmits a computed result to the receiving node.

8. The shuffle system according to claim 7; wherein a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node are performed in parallel, and wherein a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node are performed in parallel.

9. The shuffle method according to claim 5; wherein the receiving node determines whether the mini-shuffle is valid by using the data received from the verifying node; and wherein, if the receiving node determines that the mini-shuffle is not valid, the receiving node aborts processing.

10. The shuffle method according to claim 5; wherein the four secure computation nodes include: a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form; a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form; a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form; wherein the resharing nodes and the verifying node generate two random values by using a seed(s) that the receiving node does not know; wherein the resharing node(s) transmits a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node; and wherein the verifying node computes a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmits a computed result to the receiving node.

11. The shuffle method according to claim 10; wherein a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node are performed in parallel, and wherein a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node are performed in parallel.

12. The shuffle method according to claim 9; wherein the four secure computation nodes include: a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form; a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form; a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form; wherein the resharing nodes and the verifying node generate two random values by using a seed(s) that the receiving node does not know; wherein the resharing node(s) transmits a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node; and wherein the verifying node computes a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmits a computed result to the receiving node.

13. The shuffle method according to claim 12; wherein a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node are performed in parallel, and wherein a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node are performed in parallel.

14. The non-transitory computer-readable medium according to claim 6; wherein the receiving node determines whether the mini-shuffle is valid by using the data received from the verifying node; and wherein, if the receiving node determines that the mini-shuffle is not valid, the receiving node aborts processing.

15. The non-transitory computer-readable medium according to claim 6; wherein the four secure computation nodes include: a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form; a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form; a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form; wherein the resharing nodes and the verifying node generate two random values by using a seed(s) that the receiving node does not know; wherein the resharing node(s) transmits a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node; and wherein the verifying node computes a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmits a computed result to the receiving node.

16. The non-transitory computer-readable medium according to claim 15; wherein a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node are performed in parallel, and wherein a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node are performed in parallel.

17. The non-transitory computer-readable medium according to claim 14; wherein the four secure computation nodes include: a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form; a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form; a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form; wherein the resharing nodes and the verifying node generate two random values by using a seed(s) that the receiving node does not know; wherein the resharing node(s) transmits a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node; and wherein the verifying node computes a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmits a computed result to the receiving node.

18. The non-transitory computer-readable medium according to claim 17; wherein a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node are performed in parallel, and wherein a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node are performed in parallel.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0016] FIG. 1 is a diagram illustrating a configuration according to an example embodiment of the present invention.

[0017] FIG. 2 is a diagram illustrating an operation according to the example embodiment of the present invention.

[0018] FIG. 3 is a diagram illustrating an operation according to the example embodiment of the present invention.

[0019] FIG. 4 is a diagram illustrating a configuration of a shuffle system according to a first example embodiment of the present invention.

[0020] FIG. 5 is a diagram illustrating a configuration of a secure computation server according to the first example embodiment of the present invention.

[0021] FIG. 6 is a diagram illustrating an example of a mini-shuffle execution order according to the first example embodiment of the present invention.

[0022] FIG. 7 is a diagram illustrating an operation in a round (i=1) according to the first example embodiment of the present invention.

[0023] FIG. 8 is a diagram illustrating an operation in a round (i=2) according to the first example embodiment of the present invention.

[0024] FIG. 9 is a diagram illustrating an operation in a round (i=3) according to the first example embodiment of the present invention.

[0025] FIG. 10 is a diagram illustrating an operation in a round (i=4) according to the first example embodiment of the present invention.

[0026] FIG. 11 is a diagram illustrating an operation in a round (i=1 and 2) according to a second example embodiment of the present invention.

[0027] FIG. 12 is a diagram illustrating an operation in a round (i=3 and 4) according to the second example embodiment of the present invention.

[0028] FIG. 13 is a diagram illustrating an operation in a round (i=1) according to a third example embodiment of the present invention.

[0029] FIG. 14 is a diagram illustrating an operation in a round (i=2) according to the third example embodiment of the present invention.

[0030] FIG. 15 is a diagram illustrating an operation in a round (i=3) according to the third example embodiment of the present invention.

[0031] FIG. 16 is a diagram illustrating an operation in a round (i=4) according to the third example embodiment of the present invention.

[0032] FIG. 17 is a diagram illustrating a configuration of a computer that constitutes a secure computation server according to the present invention.

PREFERRED MODES

[0033] First, an outline of an example embodiment of the present invention will be described with reference to drawings. In the following outline, various components are denoted by reference characters for the sake of convenience. That is, the following reference characters are merely used as examples to facilitate understanding of the present invention. Thus, the description of the outline is not meant to limit the present invention to the illustrated modes. An individual connection line between blocks in the drawings, etc. referred to in the following description signifies both one-way and two-way directions. An arrow schematically illustrates a principal signal (data) flow and does not exclude bidirectionality. A program is executed on a computer apparatus, and the computer apparatus includes, for example, a processor, a storage device, an input device, a communication interface, and as needed, a display device. In addition, this computer apparatus is configured such that the computer apparatus can communicate with its internal device or an external device (including a computer) via the communication interface in a wired or wireless manner. In addition, while a port or an interface is present at an input/output connection point of an individual block in the relevant drawings, illustration of the port or the interface is omitted. In addition, in the following description, “A and/or B” signifies A or B, or A and B.

[0034] An example embodiment of the present invention can be realized by a shuffle system including four secure computation nodes 10-1 to 10-4, as illustrated in FIG. 1. More concretely, one of the four secure computation nodes 10-1 to 10-4 is selected as a receiving node, and two of the three remaining secure computation nodes are operated as resharing nodes. The remaining secure computation node is operated as a verifying node.

[0035] For example, as illustrated in FIG. 2, if the secure computation node 10-4 is selected as a receiving node (R), the secure computation nodes 10-1 and 10-2 may operate as resharing nodes (RS1) and (RS2) and the secure computation node 10-3 may operate as a verifying node (V).

[0036] Each of the secure computation nodes 10-1 and 10-2 operating as the resharing nodes (RS1) performs a mini-shuffle for resharing its shares held therein by using a permutation that the secure computation node 10-4 operating as the receiving node does not know. Next, the secure computation nodes 10-1 and 10-2 transmit their respective results M1 and M2 of the mini-shuffle to the secure computation node 10-4 operating as the receiving node. The secure computation node 10-3 operating as the verifying node (V) computes data V for verifying the results M1 and M2 of the mini-shuffle performed by the secure computation nodes 10-1 and 10-2 by using the permutation that the secure computation node 10-4 operating as the receiving node does not know. The secure computation node 10-3 transmits the data V for verifying the results M1 and M2 of the mini-shuffle performed by the secure computation nodes 10-1 and 10-2 to the secure computation node 10-4. Next, the secure computation node 10-4 determines whether or not the secure computation nodes 10-1 and 10-2 have performed the mini-shuffle correctly by using the data V for verifying the results M1 and M2 of the mini-shuffle.

[0037] The above procedure is considered as 1 round. FIG. 3 illustrates a round in which the secure computation node 10-1 is selected as the receiving node (R), the secure computation nodes 10-2 and 10-3 operate as the resharing nodes (RS1) and (RS2), and the secure computation node 10-4 operates as the verifying node (V). In this case as well, the secure computation nodes 10-2 and 10-3 perform a mini-shuffle and transmit results M1 and M2 of the mini-shuffle to the secure computation node 10-1. The secure computation node 10-4 transmits data V for verifying the results M1 and M2 of the mini-shuffle to the secure computation node 10-1. Next, the secure computation node 10-1 determines whether or not the secure computation nodes 10-2 and 10-3 have performed the mini-shuffle correctly by using the data V.

[0038] As described above, the shares can be shuffled by repeatedly performing rounds such that the individual secure computation node is selected as the receiving node at least once. In addition, as described above, in an individual round, the receiving node (R) determines whether or not the corresponding mini-shuffle has correctly been performed by using the data created by the verifying node (V), and in this way, the receiving node (R) can determinately detect a incorrectness or fraud (hereinafter, “incorrectness or fraud” is represented by “fraud”).

First Example Embodiment

[0039] Next, a first example embodiment of the present invention will be described in detail with reference to drawings. FIG. 4 is a diagram illustrating a configuration of a shuffle system according to the first example embodiment of the present invention. FIG. 4 illustrates a configuration in which four secure computation servers P.sub.1 to P.sub.4, which function as the above secure computation nodes, are connected to each other. Unless a particular secure computation server is specified, any one of the secure computation servers will also be referred to as a secure computation server P.sub.i.

[0040] Hereinafter, the notation used in the following description will be defined. The fourth line in the following [Math. 1] describes a finite ring, and the fifth line in the following [Math. 1] describes a pseudorandom function. S.sub.m represents a set of permutations with m elements, and π represents an arbitrary permutation belonging to S.sub.m. Among the permutation set S.sub.m with the m elements, [π].sub.i represents a permutation that only P.sub.i, P.sub.i+1, and P.sub.i+2 know.

[Math. 1]

[0041] The i-th party; P.sub.i (i=1, 2, 3, 4)

[0042] Security parameter: κ

[0043] The i-th seed: seed.sub.i∈{0, 1}.sup.κ

[0044] A finite ring: s.t. || is k-bits and its order is R.

[0045] A pseudorandom function: H:{0,2}.sup.κ×{0,1}.sup.κ.fwdarw.{0,1}.sup.k

[0046] The vector of shares: [{right arrow over (x)}].sup.m=[x.sub.1], . . . , [x.sub.m])

[0047] All permutations of a set with m elements: S.sub.m

[0048] A permutation of a set with m elements: π∈S.sub.m

[0049] Only P.sub.i, P.sub.i+1 and P.sub.i+2 know a permutation π: [π].sub.i

[0050] Hereinafter, the vector of an arbitrary element x will be expressed not only by an arrow over the element x but also by [vec{x}]. For example, an m dimensional vector of the shares of x in the above [Math. 1] will also be expressed by [vec{x}].sup.m.

[0051] FIG. 5 is a diagram illustrating a configuration of the secure computation server according to the first example embodiment of the present invention. FIG. 5 illustrates a configuration including a permutation generation part 101, a permutation application part 102, an arithmetic operation part 103, a fraud detection part 104, a random value computation part 105, a hash value computation part 106, a seed storage part 107, and a share value storage part 108.

[0052] The permutation generation part 101 generates a permutation [π].sub.i that only P.sub.i, P.sub.i+1, and P.sub.i+2 know, in coordination with other secure computation servers P.sub.i. For example, the following description assumes that the secure computation server P.sub.1 does not hold information about [π].sub.2 while the secure computation server P.sub.1 holds [π].sub.1, [π].sub.3, and [π].sub.4.

[0053] The permutation application part 102 receives the m dimensional vector [vec{x}].sup.m of the shares of the above x and the permutation [π].sub.i and outputs [vec{y}].sup.m by permutating [vec{x}].sup.m. A concrete example of processing of the permutation application part 102 will be described below along with an operation according to the present example embodiment.

[0054] The arithmetic operation part 103 performs computation of the m dimensional vector [vec{x}].sup.m of the shares of the above x and random values computed by the random value computation part 105, for example. A concrete example of processing of the arithmetic operation part 103 will be described below along with an operation according to the present example embodiment.

[0055] When the secure computation server P.sub.i operates as a receiving node, the fraud detection part 104 determines whether or not other secure computation servers have performed a permutation correctly by using verification data transmitted from a verifying node. If the fraud detection part 104 determines that these secure computation servers have not performed a permutation correctly, the fraud detection part 104 determines to abort the processing.

[0056] The random value computation part 105 generates two random values by using a seed held in the seed storage part 107 and transmits the random values to the hash value computation part 106.

[0057] The hash value computation part 106 computes hash values of the random values computed by the random value computation part 105. According to the present example embodiment, these hash values are used as random values.

[0058] The seed storage part 107 stores the seeds used for generating random values as describe above. The present example embodiment assumes that the seeds have previously been distributed to the secure computation servers P.sub.1 to P.sub.4 as follows.

P.sub.1: (seed.sub.1, seed.sub.2, seed.sub.4)
P.sub.2: (seed.sub.2, seed.sub.3, seed.sub.4)
P.sub.3: (seed.sub.3, seed.sub.1, seed.sub.4)
P.sub.4: (seed.sub.1, seed.sub.2, seed.sub.3)

[0059] The share value storage part 108 holds the m dimensional vector of shares as the permutation target. The following description will be made assuming that the individual secure computation servers P.sub.1 to P.sub.4 hold shares of x, based on a 2-out-of-4 secret sharing scheme, as will be described below. Herein, x represents the elements of a finite ring R, and x.sub.1, x.sub.2, and x.sub.3 are randomly generated such that x.sub.1+x.sub.2+x.sub.3 satisfies x(mod R). Hereinafter, the shares of x will be denoted by [x], and the shares held by the secure computation server P.sub.i will be denoted by [x]i.

P.sub.1: [x].sub.1=(x.sub.1,x.sub.2)

P.sub.2: [x].sub.2=(x.sub.2,x.sub.3)

P.sub.3: [x].sub.3=(x.sub.3,x.sub.1)

P.sub.4: [x].sub.4=(x.sub.1−x.sub.2,x.sub.2−x.sub.3)

[0060] Next, an operation according to the present example embodiment will be described in detail with reference to drawings. According to the present example embodiment, a mini-shuffle round in which one of the secure computation servers P.sub.1 to P.sub.4 operates as the receiving node, two of the three remaining secure computation servers operate as resharing nodes, and the remaining secure computation server operates as the verifying node is repeated at least four times, to shuffle the m dimensional vector [vec{x}].sup.m of the shares of x. In each round, if the fraud detection part 104 does not detect a fraud, the shuffle is deemed to be successful. If the fraud detection part 104 detects a fraud in any one of the rounds, the processing is aborted.

[0061] FIG. 6 is a diagram illustrating an example of a mini-shuffle execution order according to the first example embodiment of the present invention. As illustrated in FIG. 6, first, in case of i=1, P.sub.4, which is P.sub.i+3, is selected to operate as the receiving node. Next, a mini-shuffle is performed by causing P.sub.1 to P.sub.3, which are P.sub.i, P.sub.i+1, and P.sub.i+2, to operate as the resharing nodes and the verifying node. Next, i is incremented, the round is performed in the same manner until i=4. A shuffle is consequently completed.

[0062] Next, details of the processing performed in the individual round will be described in order.

[Round 1 i=1]
FIG. 7 is a diagram illustrating an operation in a round (i=1). In round 1, the secure computation server P.sub.4 operates as the receiving node. In addition, the secure computation servers P.sub.1 and P.sub.2 operate as the resharing nodes, and the secure computation server P.sub.3 operates as the verifying node. The mini-shuffle in round 1 is expressed by the following expression [Math. 2].

[{right arrow over (y)}].sup.m←MiniShuffle(1,[{right arrow over (x)}].sup.m,[π.sub.1].sub.1)  [Math. 2]

[vec{x}].sup.m on the right-hand side represents the m dimensional vector in which the shares of x are secret-shared and is expressed by [x.sub.1], . . . , [x.sub.m]. In practice, as described above, x.sub.j is secret-shared in the secure computation server P.sub.i such that x.sub.j=x.sub.j,1+x.sub.j,2+x.sub.j,3 (j=1, . . . , m) is satisfied. [π].sub.1 on the right-hand side is a permutation [π].sub.i that only the secure computation servers P.sub.1, P.sub.2, P.sub.3 know.

[0063] An output [vec{y}].sup.m obtained from the above right-hand side content as the input is a result of a single mini-shuffle using the permutation [π].sub.1 and is expressed by [y.sub.π1(1)], . . . , [y.sub.π1(m)]. y.sub.π1(j) in this output is also shared and held in the secure computation server P.sub.i such that y.sub.π1(j)=y.sub.π1(j),1+y.sub.π1(j),2+y.sub.π1(j),3 (j=1, . . . , m) is satisfied, as described above.

[0064] The following expression [Math. 3] illustrates the above mini-shuffle procedure.

[Math. 3]

[0065] 1. P.sub.1, P.sub.2, and P.sub.3 generate the random values r.sub.j,1 and r.sub.j,2.

r.sub.j,1=H(vid.sub.1∥1∥j,seed.sub.4)

r.sub.j,2=H(vid.sub.1∥2∥j,seed.sub.4)

[0066] 2. We set y.sub.π.sub.1.sub.(j)=y.sub.π.sub.1.sub.(j),1+y.sub.π.sub.1.sub.(j),2+y.sub.π.sub.1.sub.(j),3. [0067] 2-1. P.sub.1 computes y.sub.π.sub.1.sub.(j),1 and y.sub.π.sub.1.sub.(j),2 as follows.

y.sub.π.sub.1.sub.(j),1=x.sub.π.sub.1.sub.(j),1−r.sub.j,1

y.sub.π.sub.1.sub.(j),2=x.sub.π.sub.1.sub.(j),2+r.sub.j,1+r.sub.j,2 [0068] 2.2. P.sub.2 computes y.sub.π.sub.1.sub.(j),2 and y.sub.π.sub.1.sub.(j),3 as follows.

y.sub.π.sub.1.sub.(j),2=x.sub.π.sub.1.sub.(j),2+r.sub.j,1+r.sub.j,2

y.sub.π.sub.1.sub.(j),3=x.sub.π.sub.1.sub.(j),3−r.sub.j,2 [0069] 2-3. P.sub.3 computes y.sub.π.sub.1.sub.(j),3 and y.sub.π.sub.1.sub.(j),1 as follows.

y.sub.π.sub.1.sub.(j),3=x.sub.π.sub.1.sub.(j),3−r.sub.j,2

y.sub.π.sub.1.sub.(j),1=x.sub.π.sub.1.sub.(j),1−r.sub.j,1

[0070] 3. P.sub.1 sends {right arrow over (m.sub.1,1)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.2)} to P.sub.3. [0071] P.sub.2 sends {right arrow over (m.sub.2,2)}={right arrow over (y.sub.2)}−{right arrow over (y.sub.3)} to P.sub.3. [0072] P.sub.3 sends {right arrow over (m.sub.3)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.3)} to P.sub.4.

{right arrow over (y.sub.l)}=(y.sub.π.sub.1.sub.(1),l, . . . ,y.sub.π.sub.1.sub.(m),l)

[0073] 4. P.sub.4 checks whether {right arrow over (m.sub.3)}={right arrow over (m.sub.1,1)}+{right arrow over (m.sub.2,2)} or not. [0074] If it holds, then P.sub.4 outputs continue. [0075] If it does not hold, then P.sub.4 outputs abort.

[0076] (Step 1-1) First, the secure computation servers P.sub.1, P.sub.2, and P.sub.3 generate two random values r.sub.j, 1 and r.sub.j, 2 by using the seed, seed.sub.4 that the secure computation server P.sub.4 operating as the receiving node does not know.

[0077] (Steps 1-2-1 to 1-2-3) Next, the secure computation servers P.sub.1, P.sub.2, and P.sub.3 compute y.sub.π1(j), 1, y.sub.π1(j), 2, and y.sub.π1(j), 3, respectively, such that y.sub.π1(j)=y.sub.π1(j), 1+y.sub.π1(j), 2+y.sub.π1(j), 3 is satisfied by using the random values r.sub.j, 1 and r.sub.j, 2 in coordination with each other. Concretely, y.sub.π1(j), 1, y.sub.π1(j), 2, and y.sub.π1(j), 3 are computed as follows.

y.sub.π1(j),1=x.sub.π1(j),1−r.sub.j,1

y.sub.π1(j),2=x.sub.π1(j),2+r.sub.j,1+r.sub.j,2

y.sub.π1(j),3=x.sub.π1(j),3−r.sub.j,2

[0078] (Step 1-3) Next, the secure computation servers P.sub.1, P.sub.2, and P.sub.3 transmit their computation results to the secure computation server P.sub.4 operating as the receiving node. Concretely, the secure computation server P.sub.1 transmits vec{y.sub.1}−vec{y.sub.2} as vec{m.sub.1, 1} to the secure computation server P.sub.4. The secure computation server P.sub.2 transmits vec{y.sub.2}−vec{y.sub.3} as vec{m.sub.2, 2} to the secure computation server P.sub.4. In addition, the secure computation server P.sub.3 transmits vec{y.sub.1}−vec{y.sub.3} as verification data vec{m.sub.3} to the secure computation server P.sub.4. As expressed by [Math. 3], vec{y.sub.i} is the m dimensional vector, for example, expressed by ([y.sub.π1, 1 (1), i], . . . , [y.sub.π1 (m), i]).

[0079] (Step 1-4) Next, the secure computation server P.sub.4 performs fraud detection based on whether or not vec{m.sub.3}=vec{m.sub.1, 1}+vec{m.sub.2, 2} is established. If vec{m.sub.3}=vec{m.sub.1, 1}+vec{m.sub.2, 2} is established, the secure computation server P.sub.4 determines that the mini-shuffle has been performed correctly and proceeds to the next round. However, if vec{m.sub.3}=vec{m.sub.1, 1}+vec{m.sub.2, 2} is not established, the secure computation server P.sub.4 determines that a fraudulent shuffle has been performed and aborts the subsequent processing.

[0080] As a result of the above mini-shuffle, the secure computation servers P.sub.1 to P.sub.4 each hold a mini-shuffled m dimensional vector, as expressed by the following expression [Math. 4].

[00001]$\begin{array}{cc}\text{?}& \left[\mathrm{Math}.4\right]\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[Round 2 i=2]
FIG. 8 is a diagram illustrating an operation in a round (i=2). In round 2, the secure computation server P.sub.1 operates as the receiving node. In addition, the secure computation servers P.sub.2 and P.sub.3 operate as the resharing nodes, and the secure computation server P.sub.4 operates as the verifying node. The mini-shuffle in round 2 is expressed by the following expression [Math. 5].

[{right arrow over (y)}].sup.m←MiniShuffle(2,[{right arrow over (x)}].sup.m,[π.sub.2].sub.2)  [Math. 5]

[π].sub.2 on the right-hand side is a permutation [π].sub.i that only the secure computation servers P.sub.2, P.sub.3, and P.sub.4 know.

[0081] An output [vec{y}].sup.m obtained from the above right-hand side content as the input is a result of a single mini-shuffle using the permutation [π].sub.2 and is expressed by [y.sub.π2(1)], . . . , [y.sub.π2(m)]. y.sub.π2(j) in this output is also shared and held in the secure computation server P.sub.i such that y.sub.π2(j)=y.sub.π2(j), 1+y.sub.π2(j), 2+y.sub.π2(j), 3 (j=1, . . . , m) is satisfied, as described above.

[0082] The following expression [Math. 6] illustrates the above mini-shuffle procedure.

[Math. 6]

[0083] 1. P.sub.2, P.sub.3, and P.sub.4 generate the random values r.sub.j,1 and r.sub.j,2.

r.sub.j,1=H(vid.sub.1∥1∥j,seed.sub.3)

r.sub.j,2=H(vid.sub.1∥2∥j,seed.sub.3)

[0084] 2. We set y.sub.π.sub.2.sub.(j)=y.sub.π.sub.2.sub.(j),1+y.sub.π.sub.2.sub.(j),2+y.sub.π.sub.2.sub.(j),3. [0085] 2-1. P.sub.2 computes y.sub.π.sub.2.sub.(j),2 and y.sub.π.sub.2.sub.(j),3 as follows.

y.sub.π.sub.2.sub.(j),2=x.sub.π.sub.2.sub.(j),2+r.sub.j,1+r.sub.j,2

y.sub.π.sub.2.sub.(j),3=x.sub.π.sub.2.sub.(j),3−r.sub.j,2 [0086] 2.2. P.sub.3 computes y.sub.π.sub.2.sub.(j),1 and y.sub.π.sub.2.sub.(j),3 as follows.

y.sub.π.sub.2.sub.(j),1=x.sub.π.sub.2.sub.(j),1−r.sub.j,1

y.sub.π.sub.2.sub.(j),3=x.sub.π.sub.2.sub.(j),3−r.sub.j,2 [0087] 2-3. P.sub.4 computes y.sub.π.sub.2.sub.(j),1−y.sub.π.sub.2.sub.(j),2 and y.sub.π.sub.2.sub.(j),2−y.sub.π.sub.2.sub.(j),3 as follows.

y.sub.π.sub.2.sub.(j),1−y.sub.π.sub.2.sub.(j),2=(x.sub.π.sub.2.sub.(j),1−x.sub.π.sub.2.sub.(j),2)−2r.sub.j,1−r.sub.j,2

y.sub.π.sub.2.sub.(j),2−y.sub.π.sub.2.sub.(j),3=(x.sub.π.sub.2.sub.(j),2−x.sub.π.sub.2.sub.(j),3)+2r.sub.j,1+r.sub.j,2

[0088] 3. P.sub.2 sends {right arrow over (m.sub.2,2)}={right arrow over (y.sub.2)} to P.sub.1. [0089] P.sub.3 sends {right arrow over (m.sub.1,3)}={right arrow over (y.sub.1)} to P.sub.1. [0090] P.sub.4 sends {right arrow over (m.sub.4)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.2)} to P.sub.1.

{right arrow over (y.sub.l)}=(y.sub.π.sub.2.sub.(1),l, . . . ,y.sub.π.sub.2.sub.(m),l)

[0091] 4. P.sub.1 checks whether {right arrow over (m.sub.4)}={right arrow over (m.sub.1,3)}−{right arrow over (m.sub.2,2)} or not. [0092] If it holds, then P.sub.1 outputs continue. [0093] If it does not hold, then P.sub.1 outputs abort.

[0094] (Step 2-1) First, the secure computation servers P.sub.2, P.sub.3, and P.sub.4 generate two random values r.sub.j, 1 and r.sub.j, 2 by using the seed, seed.sub.3 that the secure computation server P.sub.1 operating as the receiving node does not know.

[0095] (Steps 2-2-1 to 2-2-3) Next, the secure computation servers P.sub.2, P.sub.3, and P.sub.4 compute y.sub.π2(j), 1, y.sub.π2(j), 2, and y.sub.π2(j), 3 such that y.sub.π2(j)=y.sub.π2(j), 1+y.sub.π2(j), 2+y.sub.π2(j), 3 (mod R) is satisfied by using the random values r.sub.j, 1 and r.sub.j, 2 in coordination with each other. Concretely, y.sub.π2(j),1, y.sub.π2(j), 2, and y.sub.π2(j), 3 are computed as follows.

y.sub.π2(j),1=x.sub.π2(j),1|r.sub.j,1

y.sub.π2(j),2=x.sub.π2(j),2+r.sub.j,1+r.sub.j,2

y.sub.π2(j),3=x.sub.π2(j),3−r.sub.j,2

[0096] In addition, the secure computation server P.sub.4 computes y.sub.π2(j), 1−y.sub.π2(j), 2 and y.sub.π2(j), 2−y.sub.π2(j), 3, as illustrated in [Math. 6].

[0097] (Step 2-3) Next, the secure computation servers P.sub.2, P.sub.3 and P.sub.4 transmit their computation results to the secure computation server P.sub.1 operating as the receiving node. Concretely, the secure computation server P.sub.2 transmits vec{y.sub.2} as vec{m.sub.2, 2} to the secure computation server P.sub.1. The secure computation server P.sub.3 transmits vec{y.sub.1} as vec{m.sub.1, 3} to the secure computation server P.sub.1. In addition, the secure computation server P.sub.4 transmits vec{y.sub.1}−vec{y.sub.2} as verification data vec{m.sub.4} to the secure computation server P.sub.1. As expressed by [Math. 6], vec{y.sub.i} is the m dimensional vector, for example, expressed by ([y.sub.π2 (1), i], . . . , [y.sub.π2 (m), i]).

[0098] (Step 2-4) Next, the secure computation server P.sub.1 performs fraud detection based on whether or not vec{m.sub.4}=vec{m.sub.1, 3} vec{m.sub.2, 2} is established. If vec{m.sub.4}=vec{m.sub.1, 3} vec{m.sub.2, 2} is established, the secure computation server P.sub.1 determines that the mini-shuffle has been performed correctly and proceeds to the next round. However, if vec{m.sub.4}=vec{m.sub.1, 3}+vec{m.sub.2, 2} is not established, the secure computation server P.sub.1 determines that a fraudulent shuffle has been performed and aborts the subsequent processing.

[0099] As a result of the above mini-shuffle, the secure computation servers P.sub.1 to P.sub.4 each hold a mini-shuffled m dimensional vector, as expressed by the following expression [Math. 7].

[00002]$\begin{array}{cc}\text{?}& \left[\mathrm{Math}.7\right]\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[Round 3 i=3]
FIG. 9 is a diagram illustrating an operation in a round (i=3). In round 3, the secure computation server P.sub.2 operates as the receiving node. In addition, the secure computation servers P.sub.3 and P.sub.1 operate as the resharing nodes, and the secure computation server P.sub.4 operates as the verifying node. The mini-shuffle in round 3 is expressed by the following expression [Math. 8].

[{right arrow over (y)}].sup.m←MiniShuffle(3,[{right arrow over (x)}].sup.m,[π.sub.3].sub.3)  [Math. 8]

[π].sub.3 on the right-hand side is a permutation [π].sub.i that only the secure computation servers P.sub.1, P.sub.3, and P.sub.4 know.

[0100] An output [vec{y}].sup.m obtained from the above right-hand side content as the input is a result of a single mini-shuffle using the permutation [π].sub.3 and is expressed by [y.sub.π3 (1)], . . . , [y.sub.π3(m)]. y.sub.π3(j) in this output is also shared and held in the secure computation server P.sub.i such that y.sub.π3 (j)=y.sub.π3 (j), 1+y.sub.π3 (j), 2+y.sub.π3 (j), 3 (j=1, . . . , m) is satisfied, as described above.

[0101] The following expression [Math. 9] illustrates the above mini-shuffle procedure.

[Math. 9]

[0102] 1. P.sub.3, P.sub.4, and P.sub.1 generate the random values r.sub.j,1 and r.sub.j,2.

r.sub.j,1=H(vid.sub.1∥1∥j,seed.sub.1)

r.sub.j,2=H(vid.sub.1∥2∥j,seed.sub.1)

[0103] 2. We set y.sub.π.sub.3.sub.(j)=y.sub.π.sub.3.sub.(j),1+y.sub.π.sub.3.sub.(j),2+y.sub.π.sub.3.sub.(j),3. [0104] 2-1. P.sub.3 computes y.sub.π.sub.3.sub.(j),1 and y.sub.π.sub.3.sub.(j),3 as follows.

y.sub.π.sub.3.sub.(j),1=x.sub.π.sub.3.sub.(j),2−r.sub.j,1

y.sub.π.sub.3.sub.(j),3=x.sub.π.sub.3.sub.(j),3−r.sub.j,2 [0105] 2.2. P.sub.1 computes y.sub.π.sub.3.sub.(j),1 and y.sub.π.sub.3.sub.(j),2 as follows.

y.sub.π.sub.3.sub.(j),1=x.sub.π.sub.3.sub.(j),1−r.sub.j,1

y.sub.π.sub.3.sub.(j),2=x.sub.π.sub.3.sub.(j),2+r.sub.j,1+r.sub.j,2 [0106] 2-3. P.sub.4 computes y.sub.π.sub.3.sub.(j),1−y.sub.π.sub.3.sub.(j),2 and y.sub.π.sub.3.sub.(j),2−y.sub.π.sub.3.sub.(j),3 as follows:

y.sub.π.sub.3.sub.(j),1−y.sub.π.sub.3.sub.(j),2=(x.sub.π.sub.3.sub.(j),1−x.sub.π.sub.3.sub.(j),2)−2r.sub.j,1−r.sub.j,2

y.sub.π.sub.3.sub.(j),2−y.sub.π.sub.3.sub.(j),3=(x.sub.π.sub.3.sub.(j),2−x.sub.π.sub.3.sub.(j),3)+r.sub.j,1+2r.sub.j,2

[0107] 3. P.sub.1 sends {right arrow over (m.sub.2,1)}={right arrow over (y.sub.2)} to P.sub.2. [0108] P.sub.3 sends {right arrow over (m.sub.3,3)}={right arrow over (y.sub.3)} to P.sub.2. [0109] P.sub.4 sends {right arrow over (m.sub.4)}={right arrow over (y.sub.2)}−{right arrow over (y.sub.3)} to P.sub.2.

{right arrow over (y.sub.l)}=(y.sub.π.sub.3.sub.(1),l, . . . ,y.sub.π.sub.3.sub.(m),l)

[0110] 4. P.sub.2 checks whether {right arrow over (m.sub.4)}={right arrow over (m.sub.2,1)}−{right arrow over (m.sub.3,3)} or not. [0111] If it holds, then P.sub.2 outputs continue. [0112] If it does not hold, then P.sub.2 outputs abort.

[0113] (Step 3-1) First, the secure computation servers P.sub.3, P.sub.4, and P.sub.1 generate two random values r.sub.j, 1 and r.sub.j, 2 by using the seed seeds that the secure computation server P.sub.2 operating as the receiving node does not know.

[0114] (Steps 3-2-1 to 3-2-3) Next, the secure computation servers P.sub.3, P.sub.4, and P.sub.1 compute y.sub.π3 (j),1, y.sub.π3 (j), 2, and y.sub.π3 (j), 3 such that y.sub.π3 (j)=y.sub.π3 (j), 1+y.sub.π3 (j), 2+y.sub.π3 (j), 3 (mod R) is satisfied by using the random values r.sub.j, 1 and r.sub.j, 2 in coordination with each other. Concretely, y.sub.π3 (j), 1, y.sub.π3 (j), 2, and y.sub.π3 (j), 3 are computed as follows.

y.sub.π3(j),1=x.sub.π3(j),1−r.sub.j,1

y.sub.π3(j),2=x.sub.π3(j),2+r.sub.j,1+r.sub.j,2

y.sub.π3(j),3=x.sub.π3(j),3−r.sub.j,2

[0115] In addition, the secure computation server P.sub.4 computes y.sub.π3 (j),1−y.sub.π3 (j), 2 and y.sub.π3(j), 2−y.sub.π3(j),3, as illustrated in [Math. 9].

[0116] (Step 3-3) Next, the secure computation servers P.sub.3, P.sub.4, and P.sub.1 transmit their computation results to the secure computation server P.sub.2 operating as the receiving node. Concretely, the secure computation server P.sub.3 transmits vec{y.sub.3} as vec{m.sub.3, 3} to the secure computation server P.sub.2. The secure computation server P.sub.1 transmits vec{y.sub.2} as vec{m.sub.2, 1} to the secure computation server P.sub.2. In addition, the secure computation server P.sub.4 transmits vec{y.sub.2}−vec{y.sub.3} as verification data vec{m.sub.4} to the secure computation server P.sub.2. As expressed by [Math. 9], vec{y.sub.i} is the m dimensional vector, for example, expressed by ([y.sub.π3 (1), i], . . . , [y.sub.π3 (m), i]).

[0117] (Step 3-4) Next, the secure computation server P.sub.2 performs fraud detection based on whether or not vec{m.sub.4}=vec{m.sub.2, 1}−vec{m.sub.3, 3} is established. If vec{m.sub.4}=vec{m.sub.2, 1}−vec{m.sub.3, 3} is established, the secure computation server P.sub.2 determines that the mini-shuffle has been performed correctly and proceeds to the next round. However, if vec{m.sub.4}=vec{m.sub.2, 1}−vec{m.sub.3, 3} is not established, the secure computation server P.sub.2 determines that a fraudulent shuffle has been performed and aborts the subsequent processing.

[0118] As a result of the above mini-shuffle, the secure computation servers P.sub.1 to P.sub.4 each hold a mini-shuffled m dimensional vector, as expressed by the following expression [Math. 10].

[00003]$\begin{array}{cc}\text{?}& \left[\mathrm{Math}.10\right]\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[Round 4 i=4]

[0119] FIG. 10 is a diagram illustrating an operation in a round (i=4). In round 4, the secure computation server P.sub.3 operates as the receiving node. In addition, the secure computation servers P.sub.1 and P.sub.2 operate as the resharing nodes, and the secure computation server P.sub.4 operates as the verifying node. The mini-shuffle in round 4 is expressed by the following expression [Math. 11].

[{right arrow over (y)}].sup.m←MiniShuffle(4,[{right arrow over (x)}].sup.m,[π.sub.4].sub.4)  [Math. 11]

[π].sub.4 on the right-hand side is a permutation [π].sub.i that only the secure computation servers P.sub.1, P.sub.2, and P.sub.4 know.

[0120] An output [vec{y}].sup.m obtained from the above right-hand side content as the input is a result of a single mini-shuffle using the permutation [π].sub.4 and is expressed by [y.sub.π4(1)], . . . , [y.sub.π4(m)]. y.sub.π4(j) in this output is also shared and held in the secure computation server P.sub.i such that y.sub.π4 (j)=y.sub.π4 (j),1+y.sub.π4 (j),2+y.sub.π4 (j),3 (j=1, . . . , m) is satisfied, as described above.

[0121] The following expression [Math. 12] illustrates the above mini-shuffle procedure.

[Math. 12]

[0122] 1. P.sub.4, P.sub.1, and P.sub.2 generate the random values r.sub.j,1 and r.sub.j,2.

r.sub.j,1=H(vid.sub.1∥1∥j,seed.sub.2)

r.sub.j,2=H(vid.sub.1∥2∥j,seed.sub.2)

[0123] 2. We set y.sub.π.sub.4.sub.(j)=y.sub.π.sub.4.sub.(j),1+y.sub.π.sub.4.sub.(j),2+y.sub.π.sub.4.sub.(j),3. [0124] 2-1. P.sub.1 computes y.sub.π.sub.4.sub.(j),1 and y.sub.π.sub.4.sub.(j),2 as follows.

y.sub.π.sub.4.sub.(j),1=x.sub.π.sub.4.sub.(j),1−r.sub.j,1

y.sub.π.sub.4.sub.(j),2=x.sub.π.sub.4.sub.(j),2+r.sub.j,1+r.sub.j,2 [0125] 2.2. P.sub.2 computes y.sub.π.sub.4.sub.(j),2 and y.sub.π.sub.4.sub.(j),3 as follows.

y.sub.π.sub.4.sub.(j),2=x.sub.π.sub.4.sub.(j),2+r.sub.j,1+r.sub.j,2

y.sub.π.sub.4.sub.(j),3=x.sub.π.sub.4.sub.(j),3−r.sub.j,2 [0126] 2-3. P.sub.4 computes y.sub.π.sub.4.sub.(j),1−y.sub.π.sub.4.sub.(j),2 and y.sub.π.sub.4.sub.(j),2−y.sub.π.sub.4.sub.(j),3 as follows.

y.sub.π.sub.4.sub.(j),1−y.sub.π.sub.4.sub.(j),2=(x.sub.π.sub.4.sub.(j),1−x.sub.π.sub.4.sub.(j),2)−2r.sub.j,1−r.sub.j,2

y.sub.π.sub.4.sub.(j),2−y.sub.π.sub.4.sub.(j),3=(x.sub.π.sub.4.sub.(j),2−x.sub.π.sub.4.sub.(j),3)+r.sub.j,1+2r.sub.j,2

[0127] 3. P.sub.1 sends {right arrow over (m.sub.1,1)}={right arrow over (y.sub.1)} to P.sub.3. [0128] P.sub.2 sends {right arrow over (m.sub.3,2)}={right arrow over (y.sub.3)} to P.sub.3. [0129] P.sub.4 sends {right arrow over (m.sub.4)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.3)} to P.sub.3.

{right arrow over (y.sub.l)}=(y.sub.π.sub.4.sub.(1),l, . . . ,y.sub.π.sub.4.sub.(m),l)

[0130] 4. P.sub.3 checks whether {right arrow over (m.sub.4)}={right arrow over (m.sub.1,1)}−{right arrow over (m.sub.3,2)} or not. [0131] If it holds, then P.sub.3 outputs continue. [0132] If it does not hold, then P.sub.3 outputs abort.

[0133] (Step 4-1) First, the secure computation servers P.sub.4, P.sub.1, and P.sub.2 generate two random values r.sub.j, 1 and r.sub.j, 2 by using the seed seed.sub.2 that the secure computation server P.sub.3 operating as the receiving node does not know.

[0134] (Steps 4-2-1 to 4-2-3) Next, the secure computation servers P.sub.4, P.sub.1, and P.sub.2 compute y.sub.π4(j), 1, y.sub.π4(j), 2, and y.sub.π4(j), 3 such that y.sub.π4(j)=y.sub.π4(j), 1+y.sub.π4(j), 2+y.sub.π4(j), 3 (mod R) is satisfied by using the random values r.sub.j, 1 and r.sub.j, 2 in coordination with each other. Concretely, y.sub.π4(j), 1, y.sub.π4(j), 2, and y.sub.π4(j), 3 are computed as follows.

y.sub.π4(j),1=x.sub.π4(j),1−r.sub.j,1

y.sub.π4(j),2=x.sub.π4(j),2+r.sub.j,1+r.sub.j,2

y.sub.π4(j),3=x.sub.π4(j),3−r.sub.j,2

[0135] In addition, the secure computation server P.sub.4 computes y.sub.π4(j), 1−y.sub.π3(j), 2 and y.sub.π4(j), 2−y.sub.π4(j), 3, as illustrated in [Math. 12].

[0136] (Step 4-3) Next, the secure computation servers P.sub.4, P.sub.1, and P.sub.2 transmit their computation results to the secure computation server P.sub.3 operating as the receiving node. Concretely, the secure computation server P.sub.1 transmits vec{y.sub.1} as vec{m.sub.1, 1} to the secure computation server P.sub.3. The secure computation server P.sub.2 transmits vec{y.sub.3} as vec{m.sub.3, 2} to the secure computation server P.sub.3. In addition, the secure computation server P.sub.4 transmits vec{y.sub.1}−vec{y.sub.3} as verification data vec{m.sub.4} to the secure computation server P.sub.3. As expressed by [Math. 12], vec{y.sub.i} is the m dimensional vector, for example, expressed by ([y.sub.π4 (1), i], . . . , [y.sub.π4 (m), i]).

[0137] (Step 4-4) Next, the secure computation server P.sub.3 performs fraud detection based on whether or not vec{m.sub.4}=vec{m.sub.1, 1}−vec{m.sub.3, 2} is established. If vec{m.sub.4}=vec{m.sub.1, 1}−vec{m.sub.3, 2} is established, the secure computation server P.sub.3 determines that the mini-shuffle has been performed correctly and complete the processing. However, if vec{m.sub.4}=vec{m.sub.1, 1}−vec{m.sub.3, 2} is not established, the secure computation server P.sub.3 determines that a fraudulent shuffle has been performed and aborts the subsequent processing.

[0138] As a result of the above mini-shuffle, the secure computation servers P.sub.1 to P.sub.4 each hold a mini-shuffled m dimensional vector, as expressed by the following expression [Math. 13].

[00004]$\begin{array}{cc}\text{?}& \left[\mathrm{Math}.13\right]\end{array}$$\text{?}\text{indicates text missing or illegible when filed}$

[0139] By performing the above mini-shuffles, the permutation [π].sub.i of the inputted [vec{x}].sup.m can be performed four times. In addition, as described in the above rounds, while the permutation with [π].sub.i is performed such that the permutation content is not known by the receiving node, the receiving node can determine a fraud determinately.

[0140] The four rounds of permutations described above can be expressed by the following [Math. 14].

1. [{right arrow over (w)}].sup.m←MiniShuffle(1,[{right arrow over (ν)}].sup.m,[π.sub.1].sub.1)

2. [{right arrow over (x)}].sup.m←MiniShuffle(2,[{right arrow over (w)}].sup.m,[π.sub.2].sub.2)

3. [{right arrow over (y)}].sup.m←MiniShuffle(3,[{right arrow over (x)}].sup.m,[π.sub.3].sub.3)

4. [{right arrow over (z)}].sup.m←MiniShuffle(4,[{right arrow over (y)}].sup.m,[π.sub.4].sub.4)  [Math. 14]

[0141] In addition, since a communication of m elements whose ring size is κ bits is performed three times per round, the shuffle cost according to the present example embodiment is 12 κm bits in the total of 4 rounds.

Second Example Embodiment

[0142] In the above first example embodiment, it is described that four rounds are performed. However, by modifying the computation method, the shuffle, which is equivalent to the shuffle shown in the first example embodiment, can be achieved with only performing two rounds. Hereinafter, a second example embodiment that enables a shuffle with two rounds will be described. Since the second example embodiment can be achieved with the same configuration as that according to the first example embodiment, the second example embodiment will be described with a focus on the difference.

[Round 1 i=1, 2]

[0143] FIG. 11 is a diagram illustrating an operation in round 1 (i=1 and 2) according to the second example embodiment. As illustrated in FIG. 11, according to the second example embodiment, computation and data transmission in round 1 and round 2 according to the first example embodiment are performed in parallel. Concretely, the secure computation server P.sub.1 transmits vec{y.sub.1}−vec{y.sub.2} as vec{m.sub.1, 1} to the secure computation server P.sub.4. The secure computation server P.sub.2 transmits vec{y.sub.2}−vec{y.sub.3} as vec{m.sub.2,2} to the secure computation server P.sub.4. In addition, the secure computation server P.sub.3 transmits vec{y.sub.1}−vec{y.sub.3} as verification data vec{m.sub.3} to the secure computation server P.sub.4. In parallel with this, the secure computation server P.sub.2 transmits vec{y.sub.2} as vec{m.sub.2, 2} to the secure computation server P.sub.1. The secure computation server P.sub.3 transmits vec{y.sub.1} as vec{m.sub.1, 3} to the secure computation server P.sub.1. In addition, the secure computation server P.sub.4 transmits vec{y.sub.1}−vec{y.sub.2} as verification data vec{m.sub.4} to the secure computation server P.sub.1.

[0144] In this round, the secure computation server P.sub.2 transmits vec{m.sub.2, 2} and vec{m.sub.2, 2}. Since the former is vec{y.sub.2}−vec{y.sub.3} as expressed by [Math. 3] and the latter is vec{y.sub.2} as expressed by [Math. 6], these can be computed in parallel. Likewise, the secure computation server P.sub.3 transmits vec{m.sub.3} and vec{m.sub.1,3}. Since the former is vec{y.sub.1}−vec{y.sub.2} as expressed by [Math. 3] and the latter is vec{y.sub.1}, these can be computed in parallel.

[0145] FIG. 12 is a diagram illustrating an operation in round 2 (i=3 and 4) according to the second example embodiment. As illustrated in FIG. 12, according to the second example embodiment, computation and data transmission in round 3 and round 4 according to the first example embodiment are performed in parallel. Concretely, the secure computation server P.sub.1 transmits vec{y.sub.2} as vec{m.sub.2, 1} to the secure computation server P.sub.2. The secure computation server P.sub.3 transmits vec{y.sub.3} as vec{m.sub.3, 3} to the secure computation server P.sub.2. In addition, the secure computation server P.sub.4 transmits vec{y.sub.2}−vec{y.sub.3} as verification data vec{m.sub.4} to the secure computation server P.sub.2. In parallel with this, the secure computation server P.sub.1 transmits vec{y.sub.1} as vec{m.sub.1, 1} to the secure computation server P.sub.3. The secure computation server P.sub.2 transmits vec{y.sub.3} as vec{m.sub.3, 2} to the secure computation server P.sub.3. In addition, the secure computation server P.sub.4 transmits vec{y.sub.1}−vec{y.sub.3} as verification data vec{m.sub.4} to the secure computation server P.sub.3.

[0146] In this round, the secure computation server P.sub.1 transmits vec{m.sub.2, 1} and vec{m.sub.1, 1}. Since the former is vec{y.sub.2} as expressed by [Math. 9] and the latter is vec{y.sub.1} as expressed by [Math. 12], these can be computed in parallel. Likewise, the secure computation server P.sub.4 transmits vec{m.sub.4} and vec{m.sub.4}. Since the former is vec{y.sub.2}−vec{y.sub.3} as expressed by [Math. 9] and the latter is vec{y.sub.1}−vec{y.sub.3}, these can be computed in parallel. Of course, the receiving node can perform fraud detection by using the verification data in the present example embodiment as well.

[0147] In addition, as described above, according to the present example embodiment, the number of rounds can be reduced to 2. According to the present example embodiment, if the communication cost of the hash values is ignored, the communication cost can be reduced to 8 κm.

Third Example Embodiment

[0148] Next, a third example embodiment will be described. The third example embodiment is obtained by changing the verification method in the receiving node and the verifying node according to the above first example embodiment. Since the third example embodiment can be realized by the same configuration as that according to the first example embodiment, the following description will be made with a focus on the difference.

[0149] In the third example embodiment, steps 3 and 4 in the second half of the mini-shuffle are replaced by the steps in the following expression [Math. 15].

[Math. 15]

[0150] 3. P.sub.1 sends {right arrow over (m.sub.1,1)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.2)} to P.sub.4. [0151] P.sub.2 sends {right arrow over (m.sub.2,2)}={right arrow over (y.sub.2)}−{right arrow over (y.sub.3)} to P.sub.4. [0152] P.sub.3 sends ν.sub.3 to P.sub.4. [0153] P.sub.4 computes ν′.

{right arrow over (y.sub.i)}=(y.sub.π.sub.1.sub.(1),i, . . . ,y.sub.π.sub.1.sub.(m),i)

When {right arrow over (m.sub.1,1)}−{right arrow over (m.sub.2,2)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.3)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.3)}=(m.sub.3,1, . . . ,m.sub.3,m).

α.sub.j=H(vid.sub.1∥j,seed.sub.3),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.3=Σ.sub.j=1.sup.mα.sub.jm.sub.3,j.

[0154] 4. P.sub.4 checks whether ν3=ν′ or not. [0155] If it holds, then P.sub.4 outputs continue. [0156] If it does not hold, then P.sub.4 outputs abort.

[0157] Concretely, the secure computation server P.sub.1 transmits vec{y.sub.1}−vec{y.sub.2} as vec{m.sub.1, 1} to the secure computation server P.sub.4. The secure computation server P.sub.2 transmits vec{y.sub.2}−vec{y.sub.3} as vec{m.sub.2, 2} to the secure computation server P.sub.4. The operation so far is the same as that according to the first example embodiment. According to the third example embodiment, the secure computation server P.sub.3 computes verification data ν.sub.3 and transmits the verification data ν.sub.3 to the secure computation server P.sub.4 (see FIG. 13). The secure computation server P.sub.4 computes a verification data ν′.

[0158] The verification data ν.sub.3 and ν′ are defined by the following expression [Math. 16].

When {right arrow over (m.sub.1,1)}−{right arrow over (m.sub.2,2)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.3)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.3)}=(m.sub.3,1, . . . ,m.sub.3,m),

α.sub.j=H(vid.sub.1∥j,seed.sub.3),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.3=Σ.sub.j=1.sup.mα.sub.jm.sub.3,j  [Math. 16]

[0159] Next, the secure computation server P.sub.4 performs fraud detection by determining whether or not ν.sub.3=ν′ is established. If ν.sub.3=ν′ is established, the secure computation server P.sub.4 determines that the mini-shuffle has been performed correctly and proceeds the next round. In contrast, if ν.sub.3=ν′ is not established, the secure computation server P.sub.4 determines that a fraudulent shuffle has been performed and aborts the subsequent processing. Since the above verification can only be performed stochastically, it is preferable that the generation of ν′ and the generation and transmission of ν.sub.3 be repeated by the number κ of security parameters (note that the transmission of ν.sub.3 may be performed together in one round).

[0160] In round 2 and thereafter, step 3 and the subsequent steps in [Math. 6], [Math. 9], and [Math. 12] are replaced by the corresponding steps in the following [Math. 17], [Math. 18], and [Math. 19].

[Math. 17]

[0161] 3. P.sub.2 sends {right arrow over (m.sub.2,2)}={right arrow over (y.sub.2)} to P.sub.1. [0162] P.sub.3 sends {right arrow over (m.sub.1,3)}={right arrow over (y.sub.1)} to P.sub.1. [0163] P.sub.1 sends ν.sub.4 to P.sub.1. [0164] P.sub.1 computes ν′.

{right arrow over (y.sub.i)}=(y.sub.π.sub.1.sub.(1),i, . . . ,y.sub.π.sub.1.sub.(m),i)

When {right arrow over (m.sub.2,2)}−{right arrow over (m.sub.1,3)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.4)}=(m.sub.4,1, . . . ,m.sub.4,m).

α.sub.j=H(vid.sub.1∥j,seed.sub.1),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.3=Σ.sub.j=1.sup.mα.sub.jm.sub.4,j.

[0165] 4. P.sub.1 checks whether ν.sub.4=ν′ or not. [0166] If it holds, then P.sub.1 outputs continue. [0167] If it does not hold, then P.sub.1 outputs abort.

[Math. 18]

[0168] 3. P.sub.1 sends {right arrow over (m.sub.2,1)}={right arrow over (y.sub.2)} to P.sub.2. [0169] P.sub.3 sends {right arrow over (m.sub.3,3)}={right arrow over (y.sub.3)} to P.sub.2. [0170] P.sub.4 sends ν.sub.3 to P.sub.2. [0171] P.sub.2 computes ν′.

{right arrow over (y.sub.i)}=(y.sub.π.sub.1.sub.(1),i, . . . ,y.sub.π.sub.1.sub.(m),i)

When {right arrow over (m.sub.2,1)}−{right arrow over (m.sub.3,3)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.4)}=(m.sub.4,1, . . . ,m.sub.4,m).

α.sub.j=H(vid.sub.1∥j,seed.sub.2),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.4=Σ.sub.j=1.sup.mα.sub.jm.sub.4,j.

[0172] 4. P.sub.2 checks whether ν.sub.4=ν′ or not. [0173] If it holds, then P.sub.2 outputs continue. [0174] If it does not hold, then P.sub.2 outputs abort.

[Math. 19]

[0175] 3. P.sub.1 sends {right arrow over (m.sub.1,1)}={right arrow over (y.sub.1)} to P.sub.3. [0176] P.sub.2 sends {right arrow over (m.sub.3,2)}={right arrow over (y.sub.3)} to P.sub.3. [0177] P.sub.4 sends ν.sub.4 to P.sub.3. [0178] P.sub.3 computes ν′.

{right arrow over (y.sub.i)}=(y.sub.π.sub.1.sub.(1),i, . . . ,y.sub.π.sub.1.sub.(m),i)

When {right arrow over (m.sub.1,1)}−{right arrow over (m.sub.3,2)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.4)}=(m.sub.4,1, . . . ,m.sub.4,m).

α.sub.j=H(vid.sub.1∥j,seed.sub.3),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.4=Σ.sub.j=1.sup.mα.sub.jm.sub.4,j.

[0179] 4. P.sub.3 checks whether ν.sub.4=ν′ or not. [0180] If it holds, then P.sub.3 outputs continue. [0181] If it does not hold, then P.sub.3 outputs abort.

[0182] In round 2 and thereafter, the processing is performed in the same manner. The secure computation server P.sub.4 computes verification data ν.sub.4 and transmits the verification data ν.sub.4 to the secure computation server P operating as the receiving node (see FIG. 14 to FIG. 16). In addition, the secure computation server P.sub.4 computes verification data ν′. In round 2 and thereafter, since the verification using the above ν′ and ν.sub.4 can only be performed stochastically, it is preferable that the generation of ν′ and the generation and transmission of ν.sub.4 be repeated by the number κ of security parameters (note that the transmission of ν.sub.4 may be performed in one round).

[0183] The above verification data ν.sub.4 and ν′ are defined by the following expressions [Math. 20] to [Math. 22].

When {right arrow over (m.sub.1,1)}−{right arrow over (m.sub.2,2)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.3)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.3)}=(m.sub.3,1, . . . ,m.sub.3,m),

α.sub.j=H(vid.sub.1∥j,seed.sub.3),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.3=Σ.sub.j=1.sup.mα.sub.jm.sub.3,j  [Math. 20]

When {right arrow over (m.sub.2,2)}−{right arrow over (m.sub.1,3)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.4)}=(m.sub.4,1, . . . ,m.sub.4,m),

α.sub.j=H(vid.sub.1∥j,seed.sub.1),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.4=Σ.sub.j=1.sup.mα.sub.jm.sub.4,j  [Math. 21]

When {right arrow over (m.sub.1,1)}−{right arrow over (m.sub.2,2)}=(m.sub.1′, . . . ,m.sub.m′) and {right arrow over (m.sub.3)}={right arrow over (y.sub.1)}−{right arrow over (y.sub.3)}=(m.sub.3,1, . . . ,m.sub.3,m),

α.sub.j=H(vid.sub.1∥j,seed.sub.3),ν′=Σ.sub.j=1.sup.mα.sub.jm.sub.j′, and ν.sub.3=Σ.sub.j=1.sup.mα.sub.jm.sub.3,j  [Math. 22]

[0184] As described above, according to the third example embodiment, the verification (fraud detection) can be performed without using hash functions.

[0185] While example embodiments of the present invention have thus been described, the present invention is not limited thereto. Further variations, substitutions, or adjustments can be made without departing from the basic technical concept of the present invention. For example, the configurations of the networks, the configurations of the elements, and the representation modes of the data illustrated in the drawings have been used only as examples to facilitate understanding of the present invention. That is, the present invention is not limited to the configurations illustrated in the drawings.

[0186] Each of the procedures described in the above first to third example embodiments can be realized by a program that causes a computer (9000 in FIG. 17) which functions as a corresponding one of the secure computation nodes and the secure computation servers P to realize the function as the corresponding apparatus. This computer includes, for example, a CPU (Central Processing Unit) 9010, a communication interface 9020, a memory 9030, and an auxiliary storage device 9040 in FIG. 17. That is, the CPU 9010 in FIG. 17 performs the random number generation program and the permutation processing program and performs processing for updating various calculation parameters stored in the auxiliary storage device 9040, etc.

[0187] That is, the individual parts (processing means, functions) of the secure computation servers P.sub.i according to the above first to third example embodiments can each be realized by a computer program that causes a processor mounted on the corresponding apparatus to use corresponding hardware and execute the corresponding processing as described above.

[0188] Finally, suitable modes of the present invention will be summarized.

[Mode 1]

[0189] (See the shuffle system according to the above first aspect)

[Mode 2]

[0190] In the above shuffle system, the receiving node may determine whether the mini-shuffle is valid by using the data received from the verifying node. If the receiving node determines that the mini-shuffle is not valid, the receiving node may be configured to abort performing the processes.

[Mode 3]

[0191] In the above shuffle system, the four secure computation nodes may be configured to include:

[0192] a first secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.4) and shares (x.sub.1 and x.sub.2) of secret information x in a secret-shared form;

[0193] a second secure computation node that holds three seeds (seed.sub.2, seed.sub.3, and seed.sub.4) and shares (x.sub.2 and x.sub.3) of the secret information x in a secret-shared form;

[0194] a third secure computation node that holds three seeds (seed.sub.3, seed.sub.1, and seed.sub.4) and shares (x.sub.3 and x.sub.1) of the secret information x in a secret-shared form; and

[0195] a fourth secure computation node that holds three seeds (seed.sub.1, seed.sub.2, and seed.sub.3) and shares (x.sub.1-x.sub.2 and x.sub.2-x.sub.3) of the secret information x in a secret-share form.

[0196] The resharing nodes and the verifying node may be configured to generate two random values by using a seed(s) that the receiving node does not know.

[0197] the resharing nodes may be configured to transmit a result, which is obtained by applying a combination of the random values to the share(s) held therein, as the result(s) of the mini-shuffle, to the receiving node.

[0198] The verifying node may be configured to compute a sum or a difference of the results transmitted from the two resharing nodes to the receiving node and transmit the computed result to the receiving node.

[Mode 4]

[0199] In the above shuffle system, a mini-shuffle in which the fourth secure computation node operates as a receiving node and a mini-shuffle in which the first secure computation node operates as a receiving node may be configured to be performed in parallel, and a mini-shuffle in which the second secure computation node operates as a receiving node and a mini-shuffle in which the third secure computation node operates as a receiving node may be configured to be performed in parallel.

[Mode 5]

[0200] (See the shuffle method according to the above second aspect)

[Mode 6]

[0201] (See the program according to the above third aspect)

[0202] The above modes 5 and 6 can be expanded in the same manner as mode 1 is expanded to modes 2 to 4.

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

INDUSTRIAL APPLICABILITY

[0204] The present invention is applicable not only to a shuffle system but also to a secret-sharing system in which sorting processing using a shuffle function of a shuffle system is performed.

REFERENCE SIGNS LIST

[0205] 10-1 to 10-4 secure computation node [0206] 101 permutation generation part [0207] 102 permutation application part [0208] 103 arithmetic operation part [0209] 104 fraud detection part [0210] 105 random value computation part [0211] 106 hash value computation part [0212] 107 seed storage part [0213] 108 share value storage part [0214] 9000 computer [0215] 9010 CPU [0216] 9020 communication interface [0217] 9030 memory [0218] 9040 auxiliary storage device [0219] P.sub.1 to P.sub.4 secure computation server