TECHNICAL FIELD

The present invention generally relates to an encryption application. In particular, it relates to a secret sharing system, a secret sharing apparatus, a secret sharing method, a secret sorting method and a secret sharing program for performing a functional calculation without disclosing input data.

BACKGROUND ART

As a method of yielding a particular calculation result without reconstructing an encrypted numeric value, there is a method referred to as secure computation (such as the method described in Non-patent literature 1). According to the method described in Non-patent literature 1, fragments of a numerical value are distributed among three secure computation apparatuses, which can hold the results of calculations such as addition, subtraction, constant sum, multiplication, constant multiplication, logical operations (NOT, AND, OR and exclusive-OR) and data format conversion (integer-to-binary) without reconstructing the original numeric value.

PRIOR ART LITERATURENon-Patent Literature

Non-patent literature 1: Koji Chida, Dai Ikarashi, Katsumi Takahashi, â€œEfficient 3-Party Secure Function Evaluation and Its Applicationâ€ , 48-th IPSJ SIG Technical Report, CSEC, pp. 1-7, Mar. 4, 2010.

SUMMARY OF THE INVENTIONProblems to be Solved by the Invention

However, the conventional technique has a problem that a plurality of pieces of data cannot be randomly replaced while concealing the association of the pieces of data. An object of the present invention is to provide a secure computation technique of outputting data that cannot be associated with a plurality of pieces of input data.

Means to Solve the Problems

The present invention relates to a secret sharing. In general, in a (k, n) secret sharing, a secret sharing system has two parameters k and n and divides a value to be concealed into n fragments in such a manner that gathering less than k of the n fragments does not lead to leakage of information concerning the original value but gathering k or more of the n fragments permits reconstruction of the original value. A secret sharing system according to the present invention comprises N secret sharing apparatuses R₁, . . . , and R_N. It is assumed that N represents an integer equal to or greater than 3, n represents an integer equal to or greater than 1 and equal to or smaller than N, M represents an integer equal to or greater than 1, m represents an integer equal to or greater than 1 and equal to or smaller than M, K represents an integer equal to or greater than 2, k represents an integer equal to or greater than 1 and equal to or smaller than K, numeric values A₁⁽¹⁾, . . . , A_K⁽¹⁾, . . . , A₁^(M), . . . , and A_K^(M)are KÃ—M numeric values whose fragments are recorded in the secret sharing apparatuses in a distributed manner, numeric values A_K⁽¹⁾, . . . , and A_K^(M)are a group of k-th numeric values associated with each other, and a_kn^(m)is a fragment of the numeric value A_k^(m)recorded in an n-th secret sharing apparatus. The secret sharing system according to the present invention comprises selection means, fragment replacement means and reshare means. The selection means selects a number, equal to or greater than 2 and smaller than N, of secret sharing apparatuses. The fragment replacement means generates a bijection Ï€ of {1, . . . , K}â†’{1, . . . , K} among the selected secret sharing apparatuses and designates fragments a_Ï€(k)i⁽¹⁾, . . . , and a_Ï€(k)i^(M)of a group of Ï€(k)-th numeric values associated with each other recorded in a selected secret sharing apparatus R_i(i represents an identification number that indicates a selected secret sharing apparatus) as fragments of a group of k-th numeric values associated with each other. The reshare means performs reshare of the fragments a_Ï€(k)i⁽¹⁾, . . . , and a_Ï€(k)i^(M)of numeric values A_Ï€(k)⁽¹⁾, . . . , and A_Ï€(k)^(M)that are used as replacements by said fragment replacement means to determine new fragments b_k1⁽¹⁾, . . . , b_kN⁽¹⁾, . . . , b_k1^(M), . . . , and b_kN^(M)(this process will be referred to as a reshare, hereinafter). In the case where reshare of a group of numeric values is performed while maintaining the association of the numeric values associated with each other, the same bijection Ï€ can be used to replace the fragments of the numeric values of the group of numeric values associated with each other.

The secret sharing system according to the present invention can further comprise initial information distribution means, initial multiplication means, checking distribution means, checking multiplication means and tamper detection means. The initial information distribution means determines fragments p_1n, . . . , and p_Knof each of K numeric values P₁, . . . , and P_Kthat are not known to any of the secret sharing apparatuses R₁, . . . , and R_Nby a secure computation and records the fragments p_1n, . . . , and p_Knin a secret sharing apparatus R_n. The initial multiplication means determines fragments s_k1, . . . , and s_kNof a numeric value S_kthat satisfies a relation that S_k=P_kÃ—A_k⁽¹⁾for the secret sharing apparatuses R₁, . . . , and R_Nby a secure computation and records the fragments s_k1, . . . , and s_kNin the secret sharing apparatuses R₁, . . . , and R_Nin a distributed manner. The checking distribution means generates fragments q_k1, . . . , and q_kNof a numeric value Q_kthat satisfies a relation that Q_k=P_Ï€(k)for k=1 to K by a secure computation and records the fragments q_k1, . . . , and q_kNin the secret sharing apparatuses R₁, . . . , and R_Nin a distributed manner. The checking multiplication means determines fragments t_k1, . . . , and t_kNof a numeric value T_kthat satisfies a relation that T_k=Q_kÃ—B_k⁽¹⁾for the secret sharing apparatuses R₁, . . . , and R_Nby a secure computation and records the fragments t_k1, . . . , and t_kNin the secret sharing apparatuses R₁, . . . , and R_Nin a distributed manner. The tamper detection means checks whether a relation that T_k=S_Ï€(k)holds or not for k=1 to K.

For example, in a case where the secret sharing system comprises three secret sharing apparatuses, it is assumed that three fragments of an m-th numeric value A_k^(m)=a_kÎ±Î²^(m)+a_kÎ²Î³^(m)+a_Î³Î±^(m)of a group of k-th numeric values associated with each other are (a_kÎ³Î±^(m), a_kÎ±Î²^(m)), (a_kÎ±Î²^(m), a_kÎ²Î³^(m)) and (a_kÎ²Î³^(m), a_kÎ³Î±^(m)) (a combination (Î±, Î², Î³) is any of combinations (1, 2, 3), (2, 3, 1) and (3, 1, 2)). It is further assumed that a fragment recorded in a secret sharing apparatus selected as a first secret sharing apparatus is a_k1^(m)=(a_k31^(m), a_k12^(m)), a fragment recorded in a secret sharing apparatus selected as a second secret sharing apparatus is a_k2^(m)=(a_k12^(m), a_k23^(m)), and a fragment recorded in a secret sharing apparatus selected as a third secret sharing apparatus is a_k3^(m)=(a_k23^(m), a_k31^(m)). Each secret sharing apparatus can comprise a fragment replacement part, a first random number generation part, a second random number generation part, a first calculation part, a second calculation part, a third calculation part and a fragment update part. If the secret sharing apparatus is selected as the first secret sharing apparatus or the second secret sharing apparatus, the fragment replacement part generates a bijection Ï€ of {1, . . . , K}â†’{1, . . . , K} and designates fragments of the numeric values of a group of Ï€(k)-th numeric values associated with each other as fragments of the numeric values of the group of k-th numeric values associated with each other. If the secret sharing apparatus is the first secret sharing apparatus, the first random number generation part generates random numbers b_k31⁽¹⁾, . . . , and b_k31^(M)for reshare of the fragments of the numeric values of the group of k-th numeric values associated with each other resulting from the designation and transmits the random numbers b_k31⁽¹⁾, . . . , and b_k31^(M)to the third secret sharing apparatus. If the secret sharing apparatus is the second secret sharing apparatus, the second random number generation part generates random numbers b_k23⁽¹⁾, . . . , and b_k23^(M)for reshare of the fragments of the numeric values of the group of k-th numeric values associated with each other and transmits the random numbers b_k23⁽¹⁾, . . . , and b_k23^(M)to the third secret sharing apparatus. If the secret sharing apparatus is the first secret sharing apparatus, the first calculation part calculates a value x_k^(m)according to x_k^(m)=b_k31^(m)âˆ’a_Ï€(k)31^(m)for m=1 to M for reshare of the fragments of the numeric values x_k⁽¹⁾, . . . , and x_k^(M)of the group of k-th numeric values associated with each other and transmits the value to the second secret sharing apparatus. If the secret sharing apparatus is the second secret sharing apparatus, the second calculation part calculates a value y_k^(m)according to y_k^(m)=b_k23^(m)âˆ’a_Ï€(k)23^(m)for m=1 to M for reshare of the fragments of the numeric values of the group of k-th numeric values associated with each other and transmits the value y_k⁽¹⁾, . . . , and y_k^(M)to the first secret sharing apparatus. If the secret sharing apparatus is the first or second secret sharing apparatus, the third calculation part calculates a value b_k12^(m)according to b_k12^(m)=a_Ï€(k)12^(m)âˆ’x_k^(m)âˆ’y_k^(m)for m=1 to M for reshare of the fragments of the numeric values of the group of k-th numeric values associated with each other. The fragment update part designates (b_k31^(m), b_k12^(m)) as a fragment b_k1^(m)if the secret sharing apparatus is the first secret sharing apparatus, designates (b_k12^(m), b_k23^(m)) as a fragment b_k2^(m)if the secret sharing apparatus is the second secret sharing apparatus, and designates (b_k23^(m), b_k31^(m)) as a fragment b_k3^(m)if the secret sharing apparatus is the third secret sharing apparatus. The fragment replacement parts of all the secret sharing apparatuses form the fragment replacement means of the secret sharing system. The first random number generation part, the second random number generation part, the first calculation part, the second calculation part, the third calculation part and the fragment update part form the reshare means of the secret sharing system.

Effects of the Invention

With the secret sharing system according to the present invention, any secret sharing apparatus that is not selected by the fragment replacement part does not know the bijection Ï€ and therefore cannot know the association between the numeric values A₁⁽¹⁾, . . . , A_K⁽¹⁾, . . . , A₁^(M), . . . , and A_K^(M)and the numeric values B₁⁽¹⁾, . . . , B_K⁽¹⁾, . . . , B₁^(M), . . . , and B_K^(M). According to the present invention, a sorting algorithm based on comparison, such as quick sort, can be achieved by a secure computation without increasing the number of comparisons.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram showing an example of a functional configuration of secret sharing systems according to first and second embodiments;

FIG. 2 is a diagram showing a flow of a secret sharing process performed by the secret sharing system according to the first embodiment;

FIG. 3 is a diagram showing a flow of a process of sorting numeric values in the secret sharing systems according to the present invention;

FIG. 4 is a diagram showing a quick sort algorithm;

FIG. 5 is a diagram showing a flow of a secret sharing process performed by the secret sharing system according to the second embodiment;

FIG. 6 is a diagram showing an example of a functional configuration of secret sharing systems according to third and fourth embodiments;

FIG. 7 is a diagram showing an example of a specific configuration of reshare parts according to the third and fourth embodiments;

FIG. 8 is a diagram showing a flow of a secret sharing process performed by the secret sharing system according to the third embodiment;

FIG. 9 is a diagram showing a specific structure of a tamper detection part according to the fourth embodiment; and

FIG. 10 is a diagram showing a flow of a secret sharing process performed by the secret sharing system according to the fourth embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

In the following, embodiments of the present invention will be described in detail. Components having the same functions will be denoted by the same reference numerals, and redundancy of the description thereof will be avoided.

First Embodiment

In the description of MEANS TO SOLVE THE PROBLEMS, it has been assumed that numeric values A₁⁽¹⁾, . . . , A_K⁽¹⁾, . . . , A₁^(M), . . . , A_K^(M)are KÃ—M numeric values whose fragments are to be distributed among and recorded in secret sharing apparatuses, the numeric values A_k⁽¹⁾, . . . , and A_k^(M)are associated to form a k-th numeric value group, and a fragment of a numeric value A_k^(m)to be recorded in an n-th secret sharing apparatus is denoted by a_kn^(m). In the description of DETAILED DESCRIPTION OF THE EMBODIMENTS, to facilitate understanding of the present invention, a case where M=1 will be first described, and then a case where M is not limited to 1 will be described. In the description of the case where M=1, A_k⁽¹⁾is expressed as A_k, and a_kn⁽¹⁾is expressed as a_kn.

[Limited Shuffling]

FIG. 1 shows an example of a functional configuration of a secret sharing system according to the first embodiment. FIG. 2 shows a flow of a secret sharing process performed by the secret sharing system according to the first embodiment. The secret sharing system according to this embodiment comprises N secret sharing apparatuses 100₁, . . . , and 100_Nand selection means 105 connected to a network 1000 (N represents an integer equal to or greater than 3, and n represents an integer equal to or greater than 1 and equal to or smaller than N). A₁, . . . , and A_Kare K numeric values whose fragments are to be distributed among and recorded in the secret sharing apparatuses 100_n(K represents an integer equal to or greater than 2), a numeric value A_kis a k-th numeric value (k represents an integer equal to or greater than 1 and equal to or smaller than K), and a_knrepresents a k-th fragment to be recorded in the secret sharing apparatus 100_n. The numeric values A₁, . . . , and A_Kare a group of numeric values to be concealed, for example, a group of numeric values to be sorted. The group of numeric values to be sorted can be a group of numeric values A_keach representing the annual income of a particular person. The selection means 105 may be provided in any of the secret sharing apparatuses or provided as a separate apparatus.

The secret sharing system according to this embodiment comprises the selection means, fragment replacement means and reshare means. The secret sharing apparatus 100_ncomprises at least a fragment replacement part 110_n, a reshare part 120_nand a recording part 190_n. The recording part 190_nrecords fragments a_1n, . . . , and a_Kn, for example. The recording part 190_nalso records information concerning what number fragment of the numeric value A_kis the fragment a_knrecorded in itself.

The selection means 105 selects a number, smaller than N, of secret sharing apparatuses (S105). For example, if the secret sharing requires Nâ€² of the N fragments to reconstruct the numeric value, it is enough that the fragment replacement means selects a number, equal to or greater than Nâ€² and smaller than N, secret sharing apparatuses.

The fragment replacement means comprises at least fragment replacement parts 110₁, . . . , and 110_N. A bijection Ï€ of {1, . . . , K}â†’{1, . . . , K} is generated among fragment replacement parts 110_iof secret sharing apparatuses 100_i(i represents the identification number of the selected secret sharing apparatus) selected by the selection means 105, and a fragment a_Ï€(k)irecorded in a recording part 190_iof the selected secret sharing apparatus 100_iis designated as the k-th fragment (S110). The bijection Ï€ may be a mapping of numbers 1 to K randomly rearranged. The bijection Ï€ is desirably a uniformly randomly rearranged mapping and can be generated by Fisher-Yates shuffle (Reference Literature 1: Richard Durstenfeld, â€œAlgorithm 235: Random permutationâ€ , Communications of the ACM archive, Volume 7, Issue 7, 1964), for example. The bijection Ï€ may be generated among the selected secret sharing apparatuses 100_ior may be generated by one of the selected secret sharing apparatuses 100_iand shared among the selected secret sharing apparatuses 100_i.

The reshare means comprises at least reshare parts 120₁, . . . , 120_N. The reshare means performs reshare of the fragments a_Ï€(k)i(a fragment a_Ï€(k)iis the k-th replaced fragment) of the numeric value A_Ï€(k)that are replacements used by the fragment replacement means to determine new fragments b_k1, . . . , and b_kN, and assumes the fragments b_k1, . . . , b_kNas fragments of a numeric value B_k(S120). That is, a relation that A_Ï€(k)=B_kholds. However, the secret sharing apparatuses that are not selected do not know the bijection Ï€ and therefore the relation that A_Ï€(k)=B(k). The recording part 190_nof each secret sharing apparatus 100_nrecords not only the fragment b_knbut also information that the k-th fragment b_knrecorded in itself is a fragment of the numeric value B_k. Furthermore, if the numeric values B₁, . . . , and B_Kare regarded as new numeric values A₁, . . . , and A_K, and the combination of the secret sharing apparatuses selected by the fragment replacement means is modified, the process described above can be repeated (S111 and S112).

The secret sharing system according to the present invention shuffles the fragments among a limited number of secret sharing apparatuses. Therefore, the secret sharing apparatus that are not selected by the fragment replacement part do not know the bijection Ï€ and therefore the association between the numeric values A₁, . . . , and A_kand the numeric values B₁, . . . , B_k. In other words, if one wants to conceal the association between the numeric values A₁, . . . , and A_Kand the numeric values B₁, . . . , and B_Kfrom a particular secret sharing apparatus, the secret sharing apparatuses to be selected can determined so that the fragment replacement part does not select that secret sharing apparatus. Furthermore, if the above process is repeated by modifying the combination of the secret sharing apparatuses selected by the fragment replacement part so that every secret sharing apparatus has experience of not being selected at least once, the numeric values B₁, . . . , and B_Kthat cannot be associated with the numeric values A₁, . . . , and A_Kby all the secret sharing apparatuses can be obtained.

[Redistribution]

In the above description of limited shuffling, reshare has not been described in detail. In this section, a reshare method will be described. The reshare method involves the update method disclosed in Section 3.3 of Reference Literature 2 (Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung, â€œProactive secret sharing or: How to cope with perpetual leakageâ€ , In Don Coppersmith, editor, CRYPTO 1995, volume 963 of LNCS, pages 339-352. Springer, 1995) and the regeneration method disclosed in Section 6.1 of Reference Literature 3 (Haiyun Luo and Songwu Lu, â€œUbiquitous and robust authentication services for ad hoc wireless networksâ€ , In UCLA-CSD-TR-200030, 2000). New fragments are generated among the secure computation apparatuses selected by the selection means 105 according to the update method disclosed in Reference Literature 2, and then, new fragments for the secure computation apparatuses that are not selected by the selection means 105 are generated according to the regeneration method disclosed in Reference Literature 3.

An algorithm, which is an application of the update method disclosed in Reference Literature 2 to the present invention, will be described below. It is assumed that the selection means 105 has selected Nâ€² secret sharing apparatuses. It is further assumed that i and j represent numbers that identify the selected secret sharing apparatuses (any of the Nâ€² numbers selected from among 1 to N) and are not equal to each other (jâ‰ i). It is further assumed that values z₁, . . . , and z_Nare predetermined values and shared among all the secret sharing apparatuses.

(1) All the secret sharing apparatuses 100_igenerate Nâ€²âˆ’1 random numbers u_i,1, u_i,2, . . . , and u_i,Nâ€²-1.
(2) All the secret sharing apparatuses 100_idetermine Z_i(z): 0=+u_i,1z+u_i,2z²+ . . . +u_i,Nâ€²-1z^Nâ€²-1.
(3) All the secret sharing apparatuses 100_itransmit the value of Z_i(z_j) to all the other selected secret sharing apparatuses 100_j(there are Nâ€²âˆ’1 secret sharing apparatuses 100_jthat are not selected).
(4) All the secret sharing apparatuses 100_idenote the sum of all the values of Z_j(z_i) received from the other selected secret sharing apparatuses 100_j(there are Nâ€²âˆ’1 secret sharing apparatuses 100_jthat are not selected) as Z(z_i), and determine new fragments b_kiusing the replacement fragments a_Ï€(k)iaccording to the following formula:

b_ki=a_Ï€(k)i+Z(z_i)

Next, an algorithm, which is an application of the regeneration method disclosed in Reference Literature 3 to the present invention, will be described. It is assumed that the â€œhâ€ represents a number that identifies a secret sharing apparatus that is not selected (any of the Nâ€²-N numbers that are not selected from among 1 to N). It is further assumed that a relation that L_ij(z)=(zâˆ’z_j)/(z_iâˆ’z_j) holds, and L_i(z) is the product of the values of L_ij(z) for all the numbers j.

(5) All the secret sharing apparatuses 100_igenerate random numbers v_i,j^(h)for all the combinations of the numbers j greater than i (i<j) and the secret sharing apparatuses 100_hthat are not selected.
(6) All the secret sharing apparatuses 100_itransmit the random numbers v_i,j^(h)to the secret sharing apparatuses 100_j.
(7) For all the secret sharing apparatuses 100_hthat are not selected, all the secret sharing apparatuses 100_idenote the sum of all the random numbers v_i,j^(h)for i and j that satisfy a relation that j<i as V^(h+)and the sum of all the random numbers v_i,j^(h)for i and j that satisfy a relation that i<j as V^(hâˆ’), determine a value w_hiaccording to the following formula:

w_hi=b_kiL_i(z_h)+V^(h+)âˆ’V^(hâˆ’)

and transmit the value w_hito the secret sharing apparatuses 100_h.
(8) All the secret sharing apparatuses 100_hregard the sum of all the received values w_hias their respective new fragments b_kh.

As described above, through the steps (1) to (4), all the selected secret sharing apparatuses record new fragments. Through the steps (5) to (8), all the secret sharing apparatus that are not selected record new fragments.

If the steps (3) and (6) are performed at the same time, the process can be sped up. More specifically, the steps (1), (2) and (5) can be first performed, then the steps (3) and (6) can be performed at the same time, and then the steps (4), (7) and (8) can be performed.

[Sorting]

FIG. 3 shows a flow of a process of sorting numeric values in the secret sharing system according to the first embodiment. Through the process described above, new numeric values A₁, . . . , and A_Kthat cannot be associated with the initial numeric values A₁, . . . , and A_Khave been obtained (S101). In the case where sorting is also to be performed, the secret sharing apparatus 100_nfurther comprises a comparison part 210_nand an exchange part 220_n. Comparison parts 210₁, . . . , and 210_Nselect two numeric values and compare the two numeric values in terms of magnitude by a secure computation (S210).

Based on the result of comparison by the comparison parts 210₁, . . . , and 210_N, exchange parts 220₁, . . . and 220_Nexchange fragments of zero sets, one set or a plurality of sets of numeric values (S220). Then, until the sorting process is completed for all the numeric values, Steps S210 and S220 (required processings such as comparison, exchange and combination modification) are repeated (S211, S212).

The result of the comparison in Step S210 is information required for all the secret sharing apparatuses to perform the subsequent processing, and therefore all the secret sharing apparatuses know the information. However, since all the secret sharing apparatuses process the new numeric values A₁, . . . , and A_Kthat cannot be associated with the initial numeric values A₁, . . . , and A_Kdue to the processing of Step S101, the information concerning the initial numeric values A₁, . . . , and A_Kdoes not leak. The comparison result is also information that is available by calculation from the output of sorting process, which is public information. Therefore, in the whole protocol according to this embodiment, disclosing the comparison result does not mean leaking more information than required.

More specifically, the quick sort algorithm shown in FIG. 4 can be applied to the operations involved in sorting (Steps S210, S220, S211 and S212). In this case also, the processing of comparing A[i] and A[j] is performed by concealing the values of A[i] and A[j], and the comparison result is public. In the case of this method, the number of comparisons is the same as in the case of the original quick sort and is O(NÂ·logN) on average. Besides, this embodiment can be applied to a sorting algorithm comprising a processing of comparing numeric values in terms of magnitude and a processing of exchanging two elements of an array.

As described above, with the secret sharing system according to this embodiment, the sorting algorithm comprising comparison and element exchange can be achieved by secure computation without increasing the number of comparisons.

[Modification of Limited Shuffling]

Next, the case where M is not limited to 1 will be described. It is assumed that M represents an integer equal to or greater than 1, and m represents an integer equal to or greater than 1 and equal to or smaller than M. It is further assumed that A⁽¹⁾, . . . , and A^(M)are vectors each having K elements, and A^(m)=(A₁^(m), . . . , A_K^(m)). It is further assumed that the elements of the vectors A⁽¹⁾, . . . , and A^(M)are associated with each other. In other words, it is assumed that A_k⁽¹⁾, . . . , and A_k^(M)are a group of k-th numeric values associated with each other. In this modification, limited shuffling of the group of numeric values is performed while maintaining the association of the group of numeric values associated with each other. It is further assumed that a_kn^(m)represents a fragment of a numeric value A_k^(m)recorded in the secret sharing apparatus 100_n. Note that the limited shuffling described above is the limited shuffling in the case where M=1, and the following description concerns more general limited shuffling.

The secret sharing system is configured as shown in FIG. 1, and the flow of the secret sharing process is as shown in FIG. 2. The secret sharing apparatus 100_ncomprises at least the fragment replacement part 110_n, the reshare part 120_nand the recording part 190_n. However, the components are configured as described below and perform the processings described below.

The recording part 190, records fragments a_1n⁽¹⁾, . . . , a_Kn⁽¹⁾, . . . , a_1n^(M), . . . , and a_Kn^(M), for example. The recording part 190_nalso records information concerning what number fragment of the numeric value A_kis the fragment a_knrecorded in itself.

The selection means 105 selects a number, smaller than N, of secret sharing apparatuses (S105). For example, if the secret sharing requires Nâ€² of the N fragments to reconstruct the numeric value, it is enough that the fragment replacement means selects a number, equal to or greater than Nâ€² and smaller than N, secret sharing apparatuses. This processing is the same as that described above.

The fragment replacement means comprises at least fragment replacement parts 110₁, . . . , and 110_N. A bijection Ï€ of {1, . . . , K}â†’{1, . . . , K} is generated among fragment replacement parts 110_iof secret sharing apparatuses 100_i(i represents the identification number of the selected secret sharing apparatus) selected by the selection means 105, and fragments a_Ï€(k)i⁽¹⁾. . . , and a_Ï€(k)i^(M)recorded in the recording part 190i of the selected secret sharing apparatus 100_iis designated as fragments of the group of k-th numeric values associated with each other (S110).

The reshare means comprises at least reshare parts 120₁, . . . , 120_N. The reshare means performs reshare of the fragments a_Ï€(k)i⁽¹⁾, . . . , and a_Ï€(k)i^(M)(fragments a_Ï€(k)i⁽¹⁾, . . . , and a_Ï€(k)i^(M)are the k-th replaced fragments) of the group of numeric values A_Ï€(k)⁽¹⁾, . . . , and A_Ï€(k)^(M)that are replacements used by the fragment replacement means to determine new fragments b_k1⁽¹⁾, . . . , b_kN⁽¹⁾, . . . , b_k1^(M), . . . , and b_kN^(M), and assumes the fragments b_k⁽¹⁾, . . . , b_kN⁽¹⁾, . . . , b_k^(M), . . . , and b_kN^(M)as fragments of numeric values B_k⁽¹⁾, . . . , and B_k^(M)(S120). That is, a relation that A_Ï€(k)^(m)=B_k^(m)holds. However, the secret sharing apparatuses that are not selected do not know the bijection Ï€ and therefore the relation that A_Ï€(k)^(m)=B_k^(m). The recording part 190_nof each secret sharing apparatus 100_nrecords not only the fragment b_kn^(m)but also information that the k-th fragment b_kn^(m)recorded in itself is a fragment of the numeric value B_k^(m). Furthermore, if the numeric values B₁⁽¹⁾, . . . , B_K⁽¹⁾, . . . , B₁^(M), . . . , and B_K^(M)are regarded as new numeric values A₁⁽¹⁾, . . . , A_K⁽¹⁾, . . . , A₁^(M), . . . , and A_K^(M), and the combination of the secret sharing apparatuses selected by the fragment replacement means is modified, the process described above can be repeated (S111 and S112).

As described above, if the limited shuffling in which the association of the elements of the vectors is maintained is used, random replacement in the column direction can be performed by regarding each row as one element (a group of numeric values associated with each other) in secret sharing of data in the form of a table, for example.

Second Embodiment[Limited Shuffling]

A secret sharing system according to a second embodiment is configured as shown in FIG. 1. A secret sharing apparatus 100_naccording to this embodiment further comprises the components shown by dotted lines. FIG. 5 shows a flow of a secret sharing process performed by the secret sharing system according to the second embodiment. The secret sharing system according to this embodiment comprises N secret sharing apparatuses 100₁, . . . , and 100_Nand selection means 105 connected to a network 1000 (N represents an integer equal to or greater than 3, and n represents an integer equal to or greater than 1 and equal to or smaller than N). A₁, . . . , and A_Kare K numeric values whose fragments are to be distributed among and recorded in the secret sharing apparatuses 100_n(K represents an integer equal to or greater than 2), a numeric value A_kis a k-th numeric value (k represents an integer equal to or greater than 1 and equal to or smaller than K), and a_knrepresents a k-th fragment to be recorded in the secret sharing apparatus 100_n.

The secret sharing system according to this embodiment comprises the selection means 105, initial information distribution means, initial multiplication means, fragment replacement means, reshare means, checking distribution means, checking multiplication means, and tamper detection means. The secret sharing apparatus 100_ncomprises an initial information distribution part 130_n, an initial multiplication part 140_n, a fragment replacement part 110_n, a reshare part 120_n, a checking distribution part 150_n, a checking multiplication part 160_n, a tamper detection part 170_n, and a recording part 190_n. The recording part 190_nrecords fragments a_1n, . . . , a_Kn, for example. The recording part 190_nalso records information concerning what number fragment of the numeric value A_kis the fragment a_knrecorded in itself.

The selection means 105 is the same as that according to the first embodiment. The initial information distribution means comprises initial information distribution parts 130₁, . . . , and 130_N. The initial information distribution part 130₁of the secure computation apparatus 100_iselected by the selection means 105 determines fragments p₁₁, . . . , p_K1, . . . , p_1n, . . . , p_Kn, . . . , p_1N, . . . , and p_KNof K numeric values P₁, . . . , and P_Kthat are not known to all the secret sharing apparatuses 100₁, . . . , and 100_N, and the fragments p_1n, . . . , and p_Knare recorded in the secret sharing apparatus 100_n(S130). Specifically, two or more secret sharing apparatuses are chosen from among the secret sharing apparatuses selected by the selection means 105. Then, based on the values generated by the chosen secret sharing apparatuses, fragments of the values that are not known to any apparatuses can be generated. For example, two secret sharing apparatuses 100_iand 100_jare chosen (iâ‰ j), and fragments of the numeric value generated by the secret sharing apparatus 100_iand fragments of the numeric value generated by the secret sharing apparatus 100_jare recorded in a distributed manner. Then, the sum of the two numeric values is determined by a secure computation, and the fragments are recorded in a distributed manner so that the result of the secure computation is concealed. Then, the fragments of the numeric values that are not known to all the secret sharing apparatuses can be recorded in a distributed manner. Although two secure computation apparatuses are chosen in this example, more than two secure computation apparatuses can also be chosen.

The initial multiplication means comprises initial multiplication parts 140₁, . . . , and 140_N. The initial multiplication parts 140_i, . . . , and 140_Ndetermine fragments s_k1, . . . , and s_kNof a numeric value S_kthat satisfies a relation that S_k=P_kÃ—A_k, and the fragments are distributed among and recorded in the secret sharing apparatuses 100₁, . . . , and 100_N.

The fragment replacement means and the reshare means are the same as those according to the first embodiment. The checking distribution means comprises checking distribution parts 150₁, . . . , and 150_N. The checking distribution parts 150₁, . . . , and 150_Ngenerate fragments q_k1, . . . , and q_kNof a numeric value Q_kthat satisfies a relation that Q_k=P_Î±(k)for k=1 to K by a secure computation, and the fragments are distributed among and recorded in the secret sharing apparatuses 100₁, . . . , and 100_N(S150). Specifically, based on the values generated by the chosen secret sharing apparatuses in Step S130, other fragments of the values that are not known to any apparatuses can be generated. For example, other fragments (new fragments) of the numeric value generated for the numeric value P_Ï€(k)by the chosen secret sharing apparatus 100_iin Step S130 and other fragments (new fragments) of the numeric value generated for the numeric value P_Ï€(k)by the chosen secret sharing apparatus 100_jin Step S130 are recorded in a distributed manner. Then, the sum of the two numeric values is determined by a secure computation, and the fragments are recorded in a distributed manner so that the result of the secure computation is concealed. Then, fragments of the numeric value Q_kthat satisfies a relation that Q_k=P_Ï€(k)and is not known to all the secret sharing apparatuses can be recorded in a distributed manner. Although two secure computation apparatuses are chosen in this example, more than two secure computation apparatuses can also be chosen as in Step S130.

The checking multiplication means comprises checking multiplication parts 160₁, . . . , and 160_N. The checking multiplication parts 160₁, . . . , and 160_Ndetermine fragments t_k1, . . . , and t_kNof a numeric value T_kthat satisfies a relation that T_k=Q_kÃ—B_kby a secure computation, and the fragments t_k1, . . . , and t_kNare distributed among and recorded in the secret sharing apparatuses 100₁, . . . , and 100_N(S160).

The tamper detection means comprises tamper detection parts 170₁, . . . , and 170_N. The tamper detection parts 170₁, . . . , and 170_Nchecks whether a relation that T_k=S_Ï€(k)holds for k=1 to K (S170). If t_knâ‰ s_Ï€(k)n, it is determined that there a tamper has occurred, and abnormal termination occurs. If the numeric values B₁, . . . , and B_Kare regarded as new numeric values A₁, . . . , and A_K, and the combination of the secret sharing apparatuses selected by the fragment replacement means is modified, the process described above can be repeated (S111, S112).

The secret sharing system according to the second embodiment has the same effects as the secret sharing apparatus according to the first embodiment and can check whether an illegal operation to transmit a tampered value to other secret sharing apparatuses has occurred in the course of a process of concealing the association between the numeric values A₁, . . . , and A_Kand the numeric values B₁, . . . , and B_K. In the case where sorting is also to be performed, the secret sharing apparatus 100_nfurther comprises a comparison part 210_nand an exchange part 220_n. The specific sorting process is the same as that according to the first embodiment.

Third Embodiment

In the first and second embodiments, it has been assumed that the number of the secret sharing apparatuses is N (N represents an integer equal to or greater than 3). However, in a third embodiment, the number of the secret sharing apparatuses that form the secret sharing system is limited to 3 for more specific description.

[Limited Shuffling]

FIG. 6 shows an example of a functional configuration of a secret sharing system according to the third embodiment. FIG. 7 shows an example of a specific configuration of a reshare part according to the third embodiment. FIG. 8 shows a flow of a secret sharing process performed by the secret sharing system according to the third embodiment. The secret sharing system according to this embodiment comprises 3 secret sharing apparatuses 100_Î±, 100_Î², and 100_Î³ and selection means 105. It is assumed that a numeric value A_kthat satisfies a relation A_k=a_kÎ±Î²+a_kÎ²Î³+a_kÎ³Î± is a k-th numeric value of K numeric values (K represents an integer equal to or greater than 2, k represents an integer equal to or greater than 1 and equal to or smaller than K, and (Î±, Î², Î³) is any of (1, 2, 3), (2, 3, 1) and (3, 1, 2)), and the three fragments of the numeric value is denoted as (a_kÎ³Î±, a_Î±Î²), (a_kÎ±Î², a_kÎ²Î³), and (a_kÎ²Î³, a_kÎ³Î±). The selection means 105 may be provided in any of the secret sharing apparatuses or provided as a separate apparatus.

The secret sharing system according to this embodiment comprises the selection means 105, fragment replacement means and reshare means. Each secret sharing apparatus 100_ncomprises a fragment replacement part 110_n, a reshare part 120_nand a recording part 190_n(n represents any of Î±, Î² and Î³). The recording part 190_nrecords fragments of numeric values A₁, . . . , and A_K, for example.

The selection means 105 selects two secret sharing apparatuses. And one of the secret sharing apparatuses selected by the selection means 105 is designated as a first secret sharing apparatus 100₁, the other is designated as a second secret sharing apparatus 100₂, and the secret sharing apparatus that is not selected is designated as a third secret sharing apparatus 100₃(S105). The k-th fragment recorded in the first secret sharing apparatus 100₁is denoted as a_k1=(a_k31, a_k12), the k-th fragment recorded in the second secret sharing apparatus 100₂is denoted as a_k2=(a_k12, a_k23), and the k-th fragment recorded in the third secret sharing apparatus 100₃is denoted as a_k3=(a_k23, a_k31).

The fragment replacement means comprises at least fragment replacement parts 110_Î±, 100_Î² and 100_Î³. The fragment replacement means generates a bijection Ï€ of {1, . . . , K}â†’{1, . . . , K} in the first secret sharing apparatus 100₁or the second secret sharing apparatus 100₂, designates a fragment a_Ï€(k)1recorded in the first secret sharing apparatus 100₁as the k-th fragment, and designates a fragment a_Ï€(k)2recorded in the second secret sharing apparatus 100₂as the k-th fragment (S110). As described above in the first embodiment, the bijection Ï€ may be a mapping of numbers 1 to K randomly rearranged. The bijection Ï€ is desirably a uniformly randomly rearranged mapping and can be generated by Fisher-Yates shuffle, for example.

The reshare means comprises at least reshare parts 120_Î±, 120_Î² and 120_Î³. As shown in FIG. 7, the reshare part 120_ncomprises a first random number generation part 121_n, a second random number generation part 122_n, a first calculation part 123_n, a second calculation part 124_n, a third calculation part 125_nand a fragment update part 126_n.

A first random number generation part 121₁of the first secret sharing apparatus 100₁generates a random value b_k31for reshare of the k-th fragment and transmits the value to the third secret sharing apparatus 100₃(S121). A second random number generation part 122₂of the second secret sharing apparatus 100₂generates a random value b_k23for reshare of the k-th fragment and transmits the value to the third secret sharing apparatus 100₃(S122). A first calculation part 123₁of the first secret sharing apparatus 100₁calculates a value x_kaccording to x_k=b_k31âˆ’a_Ï€(k)31for reshare of the k-th fragment and transmits the value x_kto the second secret sharing apparatus 100₂(S123).

A second calculation part 124₂of the second secret sharing apparatus 100₂calculates a value y_kaccording to y_k=b_k23âˆ’a_Ï€(k)23for reshare of the k-th fragment and transmits the value y_kto the first secret sharing apparatus 100₁(S124). A third calculation part 125₁of the first secret sharing apparatus 100₁and a third calculation part 125₂of the second secret sharing apparatus 100₂each calculate a value b_k12according to b_k12=a_Ï€(k)12âˆ’x_kâˆ’y_kfor reshare of the k-th fragment (S125). A fragment update part 126₁of the first secret sharing apparatus 100₁designates (b_k31, b_k12) as a fragment b_k1, a fragment update part 126₂of the second secret sharing apparatus 100₂designates (b_k12, b_k23) as a fragment b_k2, and a fragment update part 126₃of the third secret sharing apparatus 100₃designates (b_k23, b_k31) as a fragment b_k3(S126). The recording part 190_nof each secret sharing apparatus 100_nrecords not only the fragment b_knbut also information that the k-th fragment b_knrecorded in itself is a fragment of the numeric value B_k. As in the first embodiment, the fragments b_k1, b_k2and b_k3are fragments of the numeric value B_k. That is, Steps S121 to S125 correspond to Step S120.

Furthermore, if the numeric values B₁, . . . , and B_Kare regarded as new numeric values A₁, . . . , and A_K, and the combination of the secret sharing apparatuses selected by the fragment replacement means is modified, the process described above can be repeated (S111 and S112). Furthermore, if the above process is repeated by modifying the combination of the secret sharing apparatuses selected by the fragment replacement part so that every secret sharing apparatus has experience of not being selected at least once, the numeric values B₁, . . . , and B_Kthat cannot be associated with the numeric values A₁, . . . , and A_Kby all the secret sharing apparatuses can be obtained. In this embodiment, every secret sharing apparatus can have experience of not being selected at least once if the combinations of the secret sharing apparatuses selected by the fragment replacement means are {100_Î±, 100_Î²}, {100_Î², 100_Î³} and {100_Î³, 100_Î±}.

Thus, the secret sharing system according to the third embodiment has the same effects as the secret sharing system according to the first embodiment. In the case where sorting is also to be performed, the secret sharing apparatus 100_nfurther comprises a comparison part 210_nand an exchange part 220_n. The specific sorting process is the same as that according to the first embodiment.

[Modification of Limited Shuffling]

It is assumed that M represents an integer equal to or greater than 1, and m represents an integer equal to or greater than 1 and equal to or smaller than M. It is further assumed that A⁽¹⁾, . . . , and A^(M)are vectors each having K elements, and A^(m)=(A₁^(m), . . . , A_K^(m)). It is further assumed that the elements of the vectors A⁽¹⁾, . . . , and A^(M)are associated with each other. In other words, A_k⁽¹⁾, . . . , and A_k^(M)are a group of k-th numeric values associated with each other. In this modification, limited shuffling of the group of numeric values is performed while maintaining the association of the numeric values associated with each other. It is further assumed that A_k^(m)=a_kÎ±Î²^(m)+a_kÎ²Î³^(m)+a_kÎ³Î±^(m)(k represents an integer equal to or greater than 1 and equal to or smaller than K, m represents an integer equal to or greater than 1 and equal to or smaller than M, and (Î±, Î², Î³) is any of (1, 2, 3), (2, 3, 1) and (3, 1, 2)), and three fragments are denoted as (a_kÎ³Î±^(m), a_kÎ±Î²^(m)), (a_kÎ±Î²^(m), a_kÎ²Î³^(m), and (a_kÎ²Î³^(m), a_kÎ³Î±^(m)). Note that the limited shuffling described above is the limited shuffling in the case where M=1, and the following description concerns more general limited shuffling.

An example of a functional configuration of the secret sharing system is the same as that shown in FIG. 6, an example of a specific configuration of the reshare part is the same as that shown in FIG. 7, and a flow of the secret sharing process is the same as that shown in FIG. 8. The secret sharing system comprises the selection means 105, the fragment replacement means and the reshare means. The secret sharing apparatus 100_ncomprises at least the fragment replacement part 110_n, the reshare part 120_nand the recording part 190_n(n represents any of Î±, Î² and Î³). However, the components are configured as described below and perform the processings described below.

The recording part 190, records fragments a_1n⁽¹⁾, . . . , a_Kn⁽¹⁾, . . . , a_1n^(M), . . . , and a_Kn^(M), for example. The recording part 190_nalso records information concerning what number fragment of the numeric value A_kis the fragment a_knrecorded in itself.

The selection means 105 selects two secret sharing apparatuses. And one of the secret sharing apparatuses selected by the selection means 105 is designated as a first secret sharing apparatus 100₁, the other is designated as a second secret sharing apparatus 100₂, and the secret sharing apparatus that is not selected is designated as a third secret sharing apparatus 100₃(S105). The fragment of the numeric value A_k^(m)recorded in the first secret sharing apparatus 100₁is denoted as a_k1^(m)=(a_k31^(m), a_k12^(m)), the fragment of the numeric value A_k^(m)recorded in the second secret sharing apparatus 100₂is denoted as a_k2^(m)=(a_k12^(m), a_k23^(m)), and the fragment of the numeric value A_k^(m)recorded in the third secret sharing apparatus 100₃is denoted as a_k3^(m)=(a_k23^(m), a_k31^(m)).

The fragment replacement means comprises at least the fragment replacement parts 110_Î±, 100_Î² and 100_Î³. The fragment replacement means generates a bijection Ï€ of {1, . . . , K}â†’{1, . . . , K} in the first secret sharing apparatus 100₁or the second secret sharing apparatus 100₂, designates fragments a_Ï€(k)1⁽¹⁾, . . . , and a_Ï€(k)1^(M)recorded in the first secret sharing apparatus 100₁as fragments of the group of the k-th numeric values associated with each other and designates fragments a_Î±(k)2⁽¹⁾, . . . , and a_Ï€(k)2^(M)recorded in the second secret sharing apparatus 100₂as fragments of the group of the k-th numeric values associated with each other (S110).

The reshare means comprises at least reshare parts 120_Î±, 120_Î² and 120_Î³. As shown in FIG. 7, the reshare part 120_ncomprises the first random number generation part 121_n, the second random number generation part 122_n, the first calculation part 123_n, the second calculation part 124_n, the third calculation part 125_nand the fragment update part 126_n.

The first random number generation part 121₁of the first secret sharing apparatus 100₁generates random values b_k31⁽¹⁾, . . . , and b_k31^(M)for reshare of the fragments of the group of k-th numeric values associated with each other and transmits the values b_k31⁽¹⁾, . . . , and b_k31^(M)to the third secret sharing apparatus 100₃(S121). The second random number generation part 122₂of the second secret sharing apparatus 100₂generates random values b_k23⁽¹⁾, . . . , and b_k23^(M)for reshare of the fragments of the group of k-th numeric values associated with each other and transmits the values b_k23⁽¹⁾, . . . , and b_k23^(M)to the third secret sharing apparatus 100₃(S122). The first calculation part 123₁of the first secret sharing apparatus 100₁calculates a value x_k^(m)according to x_k^(m)=b_k31^(m)âˆ’a_Ï€(k)31^(m)for m=1 to M for reshare of the fragments of the group of the k-th numeric values associated with each other and transmits the values x_k⁽¹⁾, . . . , and x_k^(M)to the second secret sharing apparatus 100₂(S123).

The second calculation part 124₂of the second secret sharing apparatus 100₂calculates a value y_k^(m)according to y_k^(m)=b_k23^(m)âˆ’a_Ï€(k)23^(m)for m=1 to M for reshare of the fragments of the group of the k-th numeric values associated with each other and transmits the values y_k⁽¹⁾, . . . , and y_k^(M)to the first secret sharing apparatus 100₁(S124). The third calculation part 125₁of the first secret sharing apparatus 100₁and the third calculation part 125₂of the second secret sharing apparatus 100₂each calculate a value b_k12^(m)according to b_k12^(m)=a_Ï€(k)12^(m)âˆ’x_k^(m)âˆ’y_k^(m)for m=1 to M for reshare of the fragments of the group of the k-th numeric values associated with each other (S125). The fragment update part 126₁of the first secret sharing apparatus 100₁designates (b_k31^(m), b_k12^(m)) as a fragment b_k1^(m), the fragment update part 126₂of the second secret sharing apparatus 100₂designates (b_k12^(m), b_k23^(m)) as a fragment b_k2^(m), and the fragment update part 126₃of the third secret sharing apparatus 100₃designates (b_k23^(m), b_k31^(m)) as a fragment b_k3^(m)(S126). The recording part 190_nof each secret sharing apparatus 100_nrecords not only the fragment b_kn^(m)but also information that the k-th fragment b_kn^(m)recorded in itself is a fragment of the numeric value B_k^(m). As in the first embodiment, the fragments b_k1^(m), b_k2^(m), and b_k3^(m)are fragments of the numeric value B_k^(m). That is, Steps S121 to S126 correspond to Step S120.

Furthermore, if the numeric values B₁⁽¹⁾, . . . , B_K⁽¹⁾, . . . , B₁^(M), . . . , and B_K^(M)are regarded as new numeric values A₁⁽¹⁾, . . . , A_K⁽¹⁾, . . . , A₁^(M), . . . , and A_K^(M), and the combination of the secret sharing apparatuses selected by the fragment replacement means is modified, the process described above can be repeated (S111 and S112).

As described above, if the limited shuffling in which the association of the elements of the vectors is maintained is used, random replacement in the column direction can be performed by regarding each row as one element (a group of numeric values associated with each other) in secret sharing of data in the form of a table, for example.

Fourth Embodiment

In a fourth embodiment, again, the number of the secret sharing apparatuses that form the secret sharing system is limited to 3 for more specific description. In addition, the fourth embodiment described below concerns an example in which an illegal operation detection function is provided as in the second embodiment.

[Limited Shuffling]

A configuration of a secret sharing system according to the fourth embodiment is also shown in FIG. 6. A secret sharing apparatus 100_naccording to this embodiment additionally comprises the components shown by dotted lines. FIG. 9 shows a specific structure of a tamper detection part. FIG. 10 shows a flow of a secret sharing process performed by the secret sharing system according to the fourth embodiment. The secret sharing system according to this embodiment comprises 3 secret sharing apparatuses 100_Î±, 100_Î², and 100_Î³ and selection means 105 connected to a network 1000. It is assumed that a numeric value A_kthat satisfies a relation A_k=a_kÎ±Î²+a_kÎ²Î³+a_kÎ³Î± is a k-th numeric value of K numeric values (K represents an integer equal to or greater than 2, k represents an integer equal to or greater than 1 and equal to or smaller than K, and (Î±, Î², Î³) is any of (1, 2, 3), (2, 3, 1) and (3, 1, 2)), and the three fragments of the numeric value is denoted as (a_kÎ³Î±, a_kÎ±Î²), (a_kÎ±Î², a_kÎ²Î³), and (a_kÎ²Î³, a_kÎ³Î±).

The secret sharing system according to this embodiment comprises the selection means 105, initial information distribution means, initial multiplication means, fragment replacement means, reshare means, checking distribution means, checking multiplication means and tamper detection means. The secret sharing apparatus 100_ncomprises an initial information distribution part 130_n, an initial multiplication part 140_n, a fragment replacement part 110_n, a reshare part 120_n, a checking distribution part 150_n, a checking multiplication part 160_n, a tamper detection part 170_nand a recording part 190_n(n represents any of Î±, Î² and Î³). The recording part 190_nrecords fragments of numeric values A₁, . . . , and A_K, for example.

The selection means 105 selects two secret sharing apparatuses. And one of the secret sharing apparatuses selected by the selection means 105 is designated as a first secret sharing apparatus 100₁, the other is designated as a second secret sharing apparatus 100₂, and the secret sharing apparatus that is not selected is designated as a third secret sharing apparatus 100₃(S105). The k-th fragment recorded in the first secret sharing apparatus 100₁is denoted as a_k1=(a_k31, a_k12), the k-th fragment recorded in the second secret sharing apparatus 100₂is denoted as a_k2=(a_k12, a_k23), and the k-th fragment recorded in the third secret sharing apparatus 100₃is denoted as a_k3=(a_k23, a_k31).

The initial information distribution means comprises initial information distribution parts 130_Î±, 130_Î² and 130_Î³. The initial information distribution parts 130_Î±, 130_Î² and 130_Î³ determine a fragment p_knof each of K numeric values P₁, . . . , and P_Kthat are not known to any of the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ by a secure computation, and the fragment p_knis recorded in the secret sharing apparatus 100_n(S130). For example, the first secret sharing apparatus 100₁generates K random values R⁽¹⁾₁, . . . , and R⁽¹⁾_K, and the second secret sharing apparatus 100₂generates K random values R⁽²⁾₁, . . . , and R⁽²⁾_K. Then, fragments (r⁽¹⁾_k31, r⁽¹⁾_k12), (r⁽¹⁾_k12, r⁽¹⁾_k23), and (r⁽¹⁾_k23, r⁽¹⁾_k31) of the value R⁽¹⁾_kand fragments (r⁽²⁾_k31, r⁽²⁾_k12), (r⁽²⁾_k12, r⁽²⁾_k23), and (r⁽²⁾_k23, r⁽²⁾_k31) of the value R⁽²⁾_kare recorded in the secret sharing apparatuses 100₁, 100₂and 100₃in a secret sharing manner. Then, the secret sharing apparatuses 100₁, 100₂and 100₃determine fragments (p_k31, p_k12), (p_k12, p_k23), and (p_k23, p_k31) of a numeric value P_kthat satisfies a relation that P_k=R⁽¹⁾_k+R⁽²⁾_kby a secure computation, and the fragments are distributed among and recorded in the secret sharing apparatuses 100₁, 100₂and 100₃. Through this process, fragments of a numeric value that is not known to all the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ can be recorded in a distributed manner.

The initial multiplication means comprises initial multiplication parts 140_Î±, 140_Î² and 140_Î³. The initial multiplication parts 140_Î±, 140_Î² and 140_Î³ determine fragments (s_kÎ³Î±, s_kÎ±Î²), (s_kÎ±Î², s_Î²Î³), and (s_Î²Î³, s_Î³Î±) of a numeric value S_kthat satisfies a relation that S_k=P_kÃ—A_kby a secure computation, and the fragments are distributed among and recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ (S140).

The fragment replacement means and the reshare means are the same as those according to the third embodiment. The fragment replacement means and the reshare means serve to record fragments b_k1, b_k2, and b_k3in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ as fragments of a numeric value B_k. The checking distribution means comprises checking distribution parts 150_Î±, 150_Î² and 150_Î³. The checking distribution parts 150_Î±, 150_Î² and 150_Î³ generate fragments (q_kÎ³Î±, q_kÎ±Î²), (q_kÎ±Î², q_kÎ²Î³), and (q_kÎ²Î³, q_kÎ³Î±) of a numeric value Q_kthat satisfies a relation that Q_k=P_Ï€(k)for k=1 to K by a secure computation, and the fragments are distributed among and recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ (S150). For example, other fragments (râ€²⁽¹⁾_Ï€(k)31, râ€²⁽¹⁾_Ï€(k)12), (râ€²⁽¹⁾_Ï€(k)12, râ€²⁽¹⁾_Ï€(k)23), and (râ€²⁽¹⁾_Ï€(k)23, râ€²⁽¹⁾_Ï€(k)31) of the numeric value R⁽¹⁾_Ï€(k)generated by the first secret sharing apparatus 100₁in Step S130 and other fragments (râ€²⁽²⁾_Ï€(k)31, râ€²⁽²⁾_Ï€(k)12), (râ€²⁽²⁾_Ï€(k)12, râ€²⁽²⁾_Ï€(k)23), and (râ€²⁽²⁾_Ï€(k)23, râ€²⁽²⁾_Ï€(k)31) of the numeric value R⁽²⁾_Ï€(k)generated by the second secret sharing apparatus 100₂are recorded in a secret sharing manner Then, the secret sharing apparatuses 100₁, 100₂and 100₃generate fragments (q_k31, q_k12), (q_k12, q_k23), and (q_k23, q_k31) of the numeric value Q_kthat satisfies a relation that Q_k=R⁽¹⁾_Ï€(k)+R⁽²⁾_Ï€(k)by a secure computation using the other fragments, and the fragments are recorded in the secret sharing apparatuses 100₁, 100₂and 100₃in a distributed manner. Through the process described above, fragments of a numeric value Q_kthat satisfies a relation that Q_k=P_Ï€(k)and is not known to all the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ can be recorded in a distributed manner.

The checking multiplication means comprises checking multiplication parts 160_Î±, 160_Î² and 160_Î³. The checking multiplication parts 160_Î±, 160_Î² and 160_Î³ determine fragments (t_kÎ³Î±, t_kÎ±Î²), (t_kÎ±Î², t_kÎ²Î³), and (t_kÎ²Î³, t_kÎ³Î±) of a numeric value T_kthat satisfies a relation that T_k=Q_kÃ—B_kby a secure computation, and the fragments are recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ in a distributed manner (S160).

The tamper detection means comprises tamper detection parts 170_Î±, 170_Î² and 170_Î³. As shown in FIG. 9, the tamper detection part 170_ncomprises a third random number generation part 171_n, a fourth random number generation part 172_n, a fourth calculation part 173_n, a fifth calculation part 174_n, a first check part 175_n, a sixth calculation part 176_n, a seventh calculation part 177_nand a second check part 178_n. The tamper detection means performs a processing as described below depending on which of the first secret sharing apparatus 100₁, the second secret sharing apparatus 100₂and the secret sharing apparatus 100₃the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ operate as.

A third random number generation part 171₁of the first secret sharing apparatus 100₁generates a random number u_kand transmits the random number to the second secret sharing apparatus 100₂(S171). A fourth random number generation part 172₂of the second secret sharing apparatus 100₂generates a random number v_kand transmits the random number v_kto the first secret sharing apparatus 100₁(S172). The fourth calculation part 173₁of the first secret sharing apparatus 100₁calculates a value d_kaccording to d_k=s_Ï€(k)12âˆ’t_k12âˆ’u_kâˆ’v_kand transmits the value d_kto the third secret sharing apparatus 100₃(S173).

A fifth calculation part 174₂of the second secret sharing apparatus 100₂calculates a value e_kaccording to e_k=s_Ï€(k)12âˆ’t_k12âˆ’u_kâˆ’v_kand transmits the value e_kto the third secret sharing apparatus 100₃(S174). A first check part 175₃of the third secret sharing apparatus 100₃checks whether a relation d_k=e_kholds and terminates the processing if the relation does not holds (S175).

A sixth calculation part 176₁of the first secret sharing apparatus 100₁calculates a value f_kaccording to f_k=s_Ï€(k)31âˆ’t_k31+u_kand transmits the value f_kto the third secret sharing apparatus 100₃(S176). A seventh calculation part 177₂of the second secret sharing apparatus 100₂calculates a value g_kaccording to g_k=s_Ï€(k)23âˆ’t_k23+v_kand transmits the value g_kto the third secret sharing apparatus 100₃(S177). A second check part 178₃of the third secret sharing apparatus 100₃checks whether a relation that f_k+g_k+d_k=0 holds and terminates the processing if the relation does not hold (S178). If the numeric values B₁, . . . , and B_Kare regarded as new numeric values A₁, . . . , and A_K, and the combination of the secret sharing apparatuses selected by the fragment replacement means is modified, the process described above can be repeated (S111 and S112).

The secret sharing system according to the fourth embodiment has the same effects as the secret sharing apparatus according to the third embodiment and can check whether an illegal operation to transmit a tampered value to other secret sharing apparatuses has not occurred in the course of a process of concealing the association between the numeric values A₁, . . . , and A_Kand the numeric values B₁, . . . , and B_K. In the case where sorting is also to be performed, the secret sharing apparatus 100_nfurther comprises a comparison part 210_nand an exchange part 220_n. The specific sorting process is the same as that according to the first embodiment.

[Secret Calculation]

In the above description, it has been assumed that the secure computation is not limited to a particular method, and no specific example has been shown. In the following, a specific example of a basic secure computation that can be used in each component of the secret sharing systems according to the third and fourth embodiments will be described. In the following description, it will be assumed that fragments of a numeric value A recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ in a distributed manner are denoted as (a_Î³Î±, a_Î±Î²), (a_Î±Î², a_Î²Î³), and (a_{Î²Î³, a}_Î³Î±), fragments of a numeric value B recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ in a distributed manner are denoted as (b_Î³Î±, b_Î±Î²), (b_Î±Î², b_Î²Î³), and (b_Î²Î³, b_Î³Î±), and fragments of a numeric value C recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³ in a distributed manner are denoted as (c_Î³Î±, c_Î±Î²), (c_Î±Î², c_Î²Î³), and (c_Î²Î³, c_Î³Î±).

Secret Sharing of Numeric Value A

(1) Random numbers a_Î±Î², a_Î²Î³ are generated.
(2) A value a_Î³Î± is calculated according to a_Î³Î±=Aâˆ’a_Î±Î²âˆ’a_Î²Î³, (a_Î³Î±, a_Î±Î²), (a_Î±Î², a_Î²Î³), and (a_Î²Î³, a_Î±Î±) are designated as fragments of the value A, and the fragments (a_Î³Î±, a_Î±Î²), (a_Î±Î², a_Î²Î³), and (a_Î²Î³, a_Î³Î±) are distributed among and recorded in the secret sharing apparatuses 100_Î±, 100_Î² and 100_Î³.

Reconstruction of Numeric Value A

(1) The secret sharing apparatus 100_Î± transmits the value a_Î³Î± to the secret sharing apparatus 100_Î² and transmits the value a_Î±Î² to the secret sharing apparatus 100_Î³. The secret sharing apparatus 100_Î² transmits the value a_Î±Î² to the secret sharing apparatus 100_Î³ and transmits the value a_Î²Î³ to the secret sharing apparatus 100_Î±. The secret sharing apparatus 100_Î³ transmits the value a_Î²Î³ to the secret sharing apparatus 100_Î± and transmits the value a_Î³Î± to the secret sharing apparatus 100_Î².
(2) The secret sharing apparatus 100_Î± calculates a value a_Î±Î²+a_Î²Î³+a_Î³Î± to reconstruct the numeric value A if the value a_Î²Î³ received from the secret sharing apparatus 100_Î² and the value a_Î²Î³ received from the secret sharing apparatus 100_Î³ agree with each other. The secret sharing apparatus 100_Î² calculates the value a_Î±Î²+a_Î²Î³+a_Î³Î± to reconstruct the numeric value A if the value a_Î³Î± received from the secret sharing apparatus 100_Î³ and the value a_Î³Î± received from the secret sharing apparatus 100_Î± agree with each other. The secret sharing apparatus 100_Î³ calculates the value a_Î±Î²+a_Î²Î³+a_Î³Î±, to reconstruct the numeric value A if the value a_Î±Î² received from the secret sharing apparatus 100_Î± and the value a_Î±Î² received from the secret sharing apparatus 100_Î² agree with each other.

Secret Calculation of C=A+B

(1) The secret sharing apparatus 100_Î± calculates the fragment (c_Î³Î±, c_Î±Î²)=(a_Î³Î±+b_Î³Î±, a_Î±Î²+b_Î±Î²) and records the fragment (c_Î³Î±, c_Î±Î²), the secret sharing apparatus 100_Î² calculates the fragment (c_Î±Î², c_Î²Î³)=(a_Î±Î²+b_Î±Î², a_Î²Î³+b_Î²Î³) and records the fragment (c_{Î±Î², c}_Î²Î³), and the secret sharing apparatus 100_Î³ calculates the fragment (c_Î²Î³, c_Î³Î±)=(a_Î²Î³+b_Î²Î³, a_Î³Î±+b_Î³Î±) and records the fragment (c_Î²Î³, c_Î³Î±).

Secret Calculation of C=Aâˆ’B

(1) The secret sharing apparatus 100_Î± calculates the fragment (c_Î³Î±, c_Î±Î²)=(a_Î³Î±âˆ’b_Î³Î±, a_Î±Î²âˆ’b_Î±Î²) and records the fragment (c_Î³Î±, c_Î±Î²), the secret sharing apparatus 100_Î² calculates the fragment (c_Î±Î², c_Î²Î³)=(a_Î±Î²âˆ’b_Î±Î², a_Î²Î³âˆ’b_Î²Î³) and records the fragment (c_Î±Î², c_Î²Î³), and the secret sharing apparatus 100_Î³ calculates the fragment (c_Î²Î³, c_Î³Î±)=(a_Î²Î³âˆ’b_Î²Î³, a_Î³Î±âˆ’b_Î³Î±) and records the fragment (c_Î²Î³, c_Î³Î±).

Secret Calculation of C=A+S (S Represents a Known Constant)

(1) The secret sharing apparatus 100_Î± calculates the fragment (c_Î³Î±, c_Î±Î²)=(a_Î³Î±+S, a_Î±Î²) and records the fragment (c_Î³Î±, c_Î±Î²), and the secret sharing apparatus 100_Î³ calculates the fragment (c_Î²Î³, c_Î³Î±)=(a_Î³Î³, a_Î³Î±+S) and records the fragment (c_Î²Î³, c_Î³Î±). The secret sharing apparatus 100_Î² does not perform any processing.

Secret Calculation of C=AS (S Represents a Known Constant)

(1) The secret sharing apparatus 100_Î± calculates the fragment (c_Î³Î±, x_Î±Î²)=(a_Î³Î±S, a_Î±Î²S) and records the fragment (c_Î³Î±, c_Î±Î²), the secret sharing apparatus 100_Î² calculates the fragment (c_Î±Î², c_Î²Î³)=(a_Î±Î²S, a_Î²Î³S) and records the fragment (c_Î±Î², c_Î²Î³), and the secret sharing apparatus 100_Î³ calculates the fragment (c_Î²Î³, c_Î³Î±)=(a_{Î²Î³S, a}_Î³Î±S) and records the fragment (c_Î²Î³, c_Î³Î±).

Secret Calculation of C=AB

(1) The secret sharing apparatus 100_Î± generates random numbers r₁, r₂, and c_Î³Î± and calculates a value c_Î±Î² according to c_Î±Î²=(a_Î³Î±+a_Î±Î²)(b_Î³Î±+b_Î±Î²)âˆ’r₁âˆ’r₂âˆ’c_Î³Î±. Then, the secret sharing apparatus 100_Î± transmits (r₁, c_Î±Î²) to the secret sharing apparatus 100_Î² and (r₂, c_Î³Î±) to the secret sharing apparatus 100_Î³.
(2) The secret sharing apparatus 100_Î² calculates a value y according to y=a_Î±Î²b_Î²Î³+a_Î²Î³b_Î±Î²+r₁and transmits the value y to the secret sharing apparatus 100_Î³.
(3) The secret sharing apparatus 100_Î³ calculates a value z according to z=a_Î²Î³b_Î³Î±+a_Î³Î±b_Î²Î³+r₂and transmits the value z to the secret sharing apparatus 100_Î±.
(4) The secret sharing apparatus 100_Î² and the secret sharing apparatus 100_Î³ each calculates a value c_Î²Î³ according to c_Î²Î³=y+z+a_Î²Î³b_Î²Î³.
(5) The secret sharing apparatus 100_Î± records the fragment (c_Î³Î±, c_Î±Î²), the secret sharing apparatus 100_Î² records the fragment (c_Î±Î², c_Î²Î³), and the secret sharing apparatus 100_Î³ records the fragment (c_Î²Î³, c_Î³Î±).

[Program, Recording Medium]

The various processings described above can be performed not only sequentially in the order described above but also in parallel with each other or individually as required or depending on the processing power of the apparatus that performs the processings. Furthermore, of course, other various modifications can be appropriately made to the processings without departing from the spirit of the present invention.

In the case where the configurations described above are implemented by a computer, the specific processings of the functions of the apparatuses are described in a program. The computer executes the program to implement the processings described above.

The program that describes the specific processings can be recorded in a computer-readable recording medium. The computer-readable recording medium may be any type of recording medium, such as a magnetic recording device, an optical disk, a magneto-optical recording medium and a semiconductor memory.

The program may be distributed by selling, transferring or lending a portable recording medium, such as a DVD and a CD-ROM, in which the program is recorded, for example. Alternatively, the program may be distributed by storing the program in a storage device in a server computer and transferring the program from the server computer to other computers via a network.

The computer that executes the program first temporarily stores, in a storage device thereof, the program recorded in a portable recording medium or transferred from a server computer, for example. Then, when performing the processings, the computer reads the program from the storage device and performs the processings according to the read program. In an alternative implementation, the computer may read the program directly from the portable recording medium and perform the processings according to the program. As a further alternative, the computer may perform the processings according to the program each time the computer receives the program transferred from the server computer. As a further alternative, the processings described above may be performed on an application service provider (ASP) basis, in which the server computer does not transmit the program to the computer, and the processings are implemented only through execution instruction and result acquisition. The programs according to the embodiments of the present invention include a quasi-program, which is information to be processed by a computer (such as data that is not a direct instruction to a computer but has a property that defines the processings performed by the computer).

Although a predetermined program is executed on a computer to implement the apparatus according to the present invention in the embodiments described above, at least part of the specific processing may be implemented by hardware.