Secret calculation system, secret calculation apparatus, and secret calculation method

Abstract

The secret calculation system comprises three secret calculation apparatuses. An i.sup.th secret calculation apparatus (i=1, 2, 3) comprises a holder that holds (S[i], T[i]) and (S[i], T[i]) as distributed values of an n-bit number W and an n-bit W (n is any natural number), respectively; a first multiplicator that derives a logical conjunction of S[i] and S[i]; a second multiplicator that derives a logical conjunction of T[i] and T[i]; and a first subtractor that derives a difference between the logical conjunction derived by the first multiplicator and the logical conjunction derived by the second multiplicator.

Claims

1. A secret calculation system comprising three secret calculation apparatuses sharing an n-bit number W and an n-bit W (n=any natural number) in secret to each other, wherein an i.sup.th secret calculation apparatus (i=1, 2, 3) comprises: a holder that holds (S[i], T[i]) and (S[i], T[i]) as distributed values of the n-bit number W and the n-bit W, respectively; and a hardware processor configured to implement: a first multiplicator that derives a logical conjunction of S[i] and S[i]; a second multiplicator that derives a logical conjunction of T[i] and T[i]; and a first subtractor that derives a difference between the logical conjunction derived by the first multiplicator and the logical conjunction derived by the second multiplicator.

2. The secret calculation system according to claim 1, wherein the distributed values are
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q),
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q) when R[1], R[2], R[3] and R[1], R[2], R [3] are n-bit random numbers that satisfy R[1]+R[2]+R[3]=0 mod Q, and R[1]+R[2]+R[3]=0 mod Q (Q is an integer coprime to 3).

3. The secret calculation system according to claim 1, wherein the holder holds a local product element U[i]=(S[i].Math.S[i]T[i].Math.T[i])/3 mod Q (Q is an integer coprime to 3) calculated using the first and the second multiplicators and the first subtractor, and wherein the hardware processor of the i.sup.th secret calculation apparatus (i=1, 2, 3) further configured to implement: an adder that derives a sum X[i] of U[i] and V[i]; a communicator that transmits the sum X[i] calculated by the adder to an {(i+1 mod 3)+1}.sup.th secret calculation apparatus and receives a sum X[i mod 3+1] calculated by the adder of an (i mod 3+1).sup.th secret calculation apparatus; and an adder/subtractor that calculates distributed values (S[i], T[i]) of a product W.Math.W on the basis of addition/subtraction using the sum X[i] and the sum X[i mod 3+1] when V[1], V[2], and V[3] are n-bit random numbers that satisfy V[1]+V[2]+V[3]=0 mod Q.

4. The secret calculation system according to claim 3, wherein the distributed values are (S[i], T[i])=(X[i]X[i mod 3+1] mode Q, 2X[i]X[i mod 3+1]).

5. The secret calculation system according to claim 1, wherein the hardware processor of the i.sup.th secret calculation apparatus (i=1, 2, 3) further configured to implement: a key generator that generates a K-bit key L[i] (K is a natural number); a pseudorandom number generator that generates an nN-bit random number (N is a natural number) from a K-bit key; and a second subtractor that extracts every n bits from two nN-bit numbers and derives the difference mod Q (Q is an integer coprime to 3), the communicator transmits the key L[i] to an {(i+1 mod 3)+1}.sup.th secret calculation apparatus and receives a key L[i mod 3+1] calculated by the key generator of an (i mod 3+1).sup.th secret calculation apparatus, the pseudorandom number generator generates a first pseudorandom number on the basis of the key L[i] and generates a second pseudorandom number on the basis of the key L[i mod 3+1], and the second subtractor extracts every n bits from the first and the second pseudorandom numbers and calculates the difference mod Q.

6. The secret calculation system according to claim 5, wherein the adder of the i.sup.th secret calculation apparatus (i=1, 2, 3) uses a value calculated by the second subtractor as the random number V[i].

7. A secret calculation apparatus included in the secret calculation system according to claim 1.

8. A secret calculation method using three secret calculation apparatuses sharing an n-bit number W and an n-bit W (n=any natural number) in secret to each other, the secret calculation method including: having an i.sup.th secret calculation apparatus (i=1, 2, 3) hold (S [i], T[i]) and (S[i], T[i]) as distributed values of an n-bit number W and the n-bit W, respectively; having the i.sup.th secret calculation apparatus derive a logical conjunction of S[i] and S[i] as a first logical conjunction; having the i.sup.th secret calculation apparatus derive a logical conjunction of T[i] and T[i] as a second logical conjunction; and having the i.sup.th secret calculation apparatus derive a difference between the first logical conjunction and the second logical conjunction.

9. The secret calculation method according to claim 8, wherein the distributed values are
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q),
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q) when R[1], R[2], R[3] and R [1], R[2], R[3] are n-bit random numbers that satisfy R[1]+R[2]+R[3]=0 mod Q, and R[1]+R[2]+R[3]=0 mod Q (Q is an integer coprime to 3).

10. The secret calculation method according to claim 8 including: having the i.sup.th secret calculation apparatus (i=1, 2, 3) hold a local product element U[i]=(S[i].Math.S[i]T[i].Math.T[i])/3 mod Q (Q is an integer coprime to 3) calculated using the derived difference; having the i.sup.th secret calculation apparatus derive a sum X[i] of U[i] and V[i]; having the i.sup.th secret calculation apparatus transmit the calculated sum X[i] to an {(i+1 mod 3)+1}.sup.th secret calculation apparatus; having the i.sup.th secret calculation apparatus receive a sum X[i mod 3+1] calculated by an (i mod 3+1).sup.th secret calculation apparatus; and having the i.sup.th secret calculation apparatus calculate distributed values (S[i], T[i]) of a product W.Math.W on the basis of addition/subtraction using the sum X[i] and the sum X[i mod 3+1] when V[1], V[2], and V[3] are n-bit random numbers that satisfy V[1]+V[2]+V[3]=0 mod Q.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a block diagram illustrating the configuration of a secret calculation system relating to an exemplary embodiment.

(2) FIG. 2 is a drawing showing the configuration of a secret calculation system relating to a first exemplary embodiment.

(3) FIG. 3 is a block diagram illustrating the configuration of a secret calculation apparatus in the secret calculation system relating to the first exemplary embodiment.

(4) FIG. 4 is a block diagram illustrating the configuration of a secret calculation apparatus in a secret calculation system relating to a second exemplary embodiment.

PREFERRED MODES

(5) First, a summary of an exemplary embodiment will be given. Note that drawing reference signs in the summary are given solely to facilitate understanding and are not intended to limit the present invention to the modes shown in the drawings.

(6) FIG. 1 is a block diagram illustrating the configuration of a secret calculation system 100 relating to an exemplary embodiment. In FIG. 1, the secret calculation system 100 comprises three secret calculation apparatuses 10, 20, and 30. The secret calculation apparatuses 10, 20, and 30 will be referred to as the first, the second and the third secret calculation apparatuses, respectively. An i.sup.th secret calculation apparatus (i=1, 2, 3) comprises a holder 12 that holds (S[i], T[i]) and (S[i], T[i]) as distributed values of an n-bit number W and an n-bit W (n is any natural number), respectively; a first multiplicator 14 that derives a logical conjunction of S[i] and S[i]; a second multiplicator 16 that derives a logical conjunction of T[i] and T[i]; and a first subtractor 18 that derives a difference between the logical conjunction derived by the first multiplicator 14 and the logical conjunction derived by the second multiplicator 16.

(7) Further, when R[1], R[2], R[3] and R[1], R[2], R[3] are n-bit random numbers that satisfy R[1]+R[2]+R[3]=0 mod Q, and R[1]+R[2]+R[3]=0 mod Q, the distributed values are as follows.
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q),
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q)

(8) Here, Q is an integer coprime to 3 (for instance Q=2^n where n is a natural number).

(9) In this secret calculation system, the i.sup.th apparatus is able to derive a local product element U[i]=(T[i].Math.T[i]S[i].Math.S[i])/3 mod Q using the first and the second multiplicators and the first subtractor. Here, since U[1]+U[2]+U[3]=WW mod Q, three apparatuses can cooperate to restore the logical conjunction W=W.Math.W mod Q. According to the secret calculation system of an exemplary embodiment, it becomes possible to perform addition without having the apparatuses communicate with each other and calculate logical conjunction with a small amount of calculation.

Exemplary Embodiment 1

(10) Next, a secret calculation system relating to a first exemplary embodiment will be described with reference to the drawings.

(11) FIG. 2 is a drawing illustrating the configuration of the secret calculation system 100 relating to the present exemplary embodiment. In FIG. 2, the secret calculation system 100 comprises three secret calculation apparatuses 10, 20, and 30.

(12) FIG. 3 is a block diagram illustrating the configuration of the secret calculation apparatus 10. The secret calculation apparatuses 20 and 30 are configured identically to the secret calculation apparatus 10. In FIG. 3, the secret calculation apparatus 10 comprises a local multiplicator 36, a product redistributor 38, and a communicator 24. The local multiplicator 36 comprises the holder 12, the multiplicators and 16, and the subtractor 18. The product redistributor 38 comprises an adder 22 and an adder/subtractor 26.

(13) The secret calculation apparatuses 10, 20, and 30 divide a value W and hold the divided values. The holder 12 of the secret calculation apparatus 10 holds (R[1], R[3]W mod Q) using three randomly selected numbers R[1], R[2], and R[3] for n, which is an integer not less than 1, where R[1]+R[2]+R[3]=0 mod Q. Similarly, the holder 12 of the secret calculation apparatus 20 holds (R[2], R[1]W mod Q) and the holder 12 of the secret calculation apparatus 30 holds (R[3], R[2]W mod Q). Here, Q and 3 are coprime (for instance Q=2^n where n is a natural number).

(14) When two out of the three secret calculation apparatuses 10, 20 and 30 cooperate, they are able to restore W. Without loss of generality, when the secret calculation apparatuses 10 and 20 cooperate, such a restoration method can be explained. In other words, the value W can be restored by calculating W=R[1](R[1]W) mod Q using R[1] held by the holder 12 of the secret calculation apparatus 10 and R[1]W mod Q held by the holder 12 of the secret calculation apparatus 20.

(15) (Addition without Communication)

(16) Next, how the secret calculation apparatuses 10, 20, and 30 can perform addition without communicating with each other. When each of the bits W and W is divided and distributed among the secret calculation apparatuses 10, 20, and 30 and remains divided and distributed, the addition thereof is performed as follows.

(17) Here, it is assumed that the bit W is divided and distributed among the secret calculation apparatuses 10, 20, and 30 as follows. Using three randomly selected bits R[1], R[2], and R[3] that satisfy R[1]+R[2]+R[3]=0 mod 2, the holder 12 of the secret calculation apparatus 10 holds (S[1], T[1]):=(R[1], W+R[2] mod 2). Similarly, the holder 12 of the secret calculation apparatus 20 holds (S[2], T[2]):=(R[2], W+R[3] mod 2), and the holder 12 of the secret calculation apparatus 30 holds (S[3], T[3]):=(R[3], W+R[1] mod 2).

(18) Meanwhile, it is assumed that the bit W is divided and distributed among the secret calculation apparatuses 10, 20, and 30 as follows.

(19) Using three randomly selected bits R[1], R[2], and R[3] where R[1]+R[2]+R[3]=0 mod 2, the holder 12 of the secret calculation apparatus 10 holds (S[1], T[1]):=(R[1], W+R[2] mod 2). Similarly, the holder 12 of the secret calculation apparatus 20 holds (S[2], T[2]):=(R[2], W+R[3] mod 2), and the holder 12 of the secret calculation apparatus 30 holds (S[3], T[3]):=(R[3], W+R[1] mod 2).

(20) At this time, the secret calculation apparatus 10 calculates (S[1], T[1])=(S[1]+S[1] mod 2, T[1]+T[1] mod 2). Similarly, the secret calculation apparatus 20 calculates (S[2], T[2])=(S[2]+S[2] mod 2, T[2]+T[2] mod 2). Further, the secret calculation apparatus 30 calculates (S[3], T[3])=(S[3]+S[3] mod 2, T[3]+T[3] mod 2). Each of the secret calculation apparatuses 10, 20, and 30 holds the respective calculation result thereby holding W=W+W mod 2 in a distributed manner. W can be restored from these results as the original W or W. Therefore, addition can be performed without having the secret calculation apparatuses 10, 20, and 30 communicate with each other.

(21) (Negation)

(22) Next, the operation of negation will be described. When the bit W is divided and distributed among the apparatuses 10, 20, and 30, the bit W is negated while remaining distributed as follows.

(23) The bit W is assumed to be distributed among the secret calculation apparatuses 10, 20, and 30 as follows. Using three randomly selected bits R[1], R[2], and R[3] where R[1]+R[2]+R[3] =0 mod 2, the holder 12 of the secret calculation apparatus 10 holds (S[1], T[1]):=(R[1], W +R[2] mod 2). Similarly, the holder 12 of the secret calculation apparatus 20 holds (S[2], T[2]):=(R[2], W+R[3] mod 2). Further, the holder 12 of the secret calculation apparatus 30 holds (S[3], T[3]) =(R[3], W+R[1] mod 2).

(24) At this time, the secret calculation apparatus 10 calculates (S[1], T[1])=(S[1], T[1]+1 mod 2). Similarly, the secret calculation apparatus 20 calculates (S[2], T[2])=(S[2], T[2]+1 mod 2). Further, the secret calculation apparatus 30 calculates (S[3], T[3])=(S[3], T[3]+1 mod 2). Each of the secret calculation apparatuses 10, 20, and 30 holds the respective calculation result thereby holding W=W+1 mod 2 in a distributed manner. W can be restored from these results as the original W. Therefore, negation can be performed without having the secret calculation apparatuses 10, 20, and 30 communicate with each other.

(25) (Logical Conjunction)

(26) Next, the operation of logical conjunction will be described. The local multiplicator 36 and the product redistributor 38 shown in FIG. 3 are used in the logical conjunction operation. When the bits W and W are divided and distributed among the secret calculation apparatuses 10, 20, and 30, the logical conjunction W=W.Math.W mod Q thereof is calculated while the bits remain distributed as follows.

(27) The bit W is assumed to be distributed among the secret calculation apparatuses 10, 20, and 30 as follows. Using three randomly selected numbers R[1], R[2], and R[3] where R[1]+R[2]+R[3]=0 mod Q, the holder 12 of the secret calculation apparatus 10 holds (S[1], T[1]):=(R[1], R[3]W mod Q). Similarly, the holder 12 of the secret calculation apparatus 20 holds (S[2], T[2]):=(R[2], R[1]W mod 2). Further, the holder 12 of the secret calculation apparatus 30 holds (S[3], T[3])=(R[3], R[2]W mod Q).

(28) Meanwhile, the bit W is assumed to be distributed among the secret calculation apparatuses 10, 20, and 30 as follows. Using three randomly selected numbers R[1], R[2], and R[3] where R[1]+R[2]+R[3]=0 mod Q, the holder 12 of the secret calculation apparatus 10 holds (S[1], T[1])=(R[1], R[3]W mod Q). Similarly, the holder 12 of the secret calculation apparatus 20 holds (S[2], T[2]):=(R[2], R[1]W mod Q). Further, the holder 12 of the secret calculation apparatus 30 holds (S[3], T[3]):=(R[3], R[2]W mod Q).

(29) At this time, in the local multiplicator 36 of the secret calculation apparatus 10, the multiplicator 14 calculates the logical conjunction of the first element of the first input S[1] and the first element of the second input S[1] held by the holder 12 and outputs the result to the subtractor 18. Meanwhile, the multiplicator 16 calculates the logical conjunction of the second element of the first input T[2] and the second element of the second input T[1] and outputs the result to the subtractor 18. The subtractor 18 calculates a local product element U[1]=(T[1].Math.T[1]S[1].Math.S[1])/3 mod Q on the basis of the outputs from the multiplicators 14 and 16.

(30) Similarly, the local multiplicator 36 of the secret calculation apparatus 20 calculates a local product element U[2]=(T[2].Math.T[2]S[2].Math.S[2])/3 mod Q. Further, the local multiplicator 36 of the secret calculation apparatus 30 calculates a local product element U[3]=(T[3]T[3]S[3].Math.S[3])/3 mod Q. With each of the calculation results, the secret calculation apparatuses 10, 20, and 30 hold W=W.Math.W mod Q in a distributed manner.

(31) At this time, like the original W or W, the logical conjunction W cannot be restored only from the local product elements calculated by the secret calculation apparatuses. The logical conjunction W can be directly restored from the local product elements calculated by the secret calculation apparatuses by calculating W=U[1]+U[2]+U[3] mod Q. The following calculations indicate that the logical conjunction W can be restored.

(32) $U\left[1\right]+U\left[2\right]+U\left[3\right]=\left\{\left(T\left[1\right].Math.T^{}\left[1\right]-S\left[1\right].Math.S^{}\left[1\right]\right)+\left(T\left[2\right].Math.T^{}\left[2\right]-S\left[2\right].Math.S^{}\left[2\right]\right)+\left(T\left[3\right].Math.T^{}\left[3\right]-S\left[3\right].Math.S^{}\left[3\right]\right)\right\}/3\mathrm{mod}Q=\left\{-S\left[1\right]S^{}\left[1\right]+\left(R\left[3\right]-W\right)\left(R^{}\left[3\right]-W^{}\right)-S\left[2\right]S^{}\left[2\right]+\left(R\left[1\right]-W\right)\left(R^{}\left[1\right]-W^{}\right)-S\left[3\right]S^{}\left[3\right]+\left(R\left[2\right]-W\right)\left(R^{}\left[2\right]-W^{}\right)\right\}/3\mathrm{mod}Q=\left\{-R\left[1\right]R^{}\left[1\right]+R\left[3\right]R^{}\left[3\right]-R\left[3\right]W^{}-W{R}^{}\left[3\right]+{\mathrm{WW}}^{}-R\left[2\right]R^{}\left[2\right]+R\left[1\right]R^{}\left[1\right]-R\left[1\right]W^{}-W{R}^{}\left[1\right]+{\mathrm{WW}}^{}-R\left[3\right]R^{}\left[3\right]+R\left[2\right]R^{}\left[2\right]-R\left[2\right]W^{}-W{R}^{}\left[2\right]+{\mathrm{WW}}^{}\right\}/3\mathrm{mod}Q=3{\mathrm{WW}}^{}/3\mathrm{mod}Q={\mathrm{WW}}^{}\mathrm{mod}Q$

(33) Further, since Q and 3 are coprime, the reciprocal of 3 mod Q can always be calculated.

(34) As described, (U[1], U[2], U[3]) equals W.Math.W divided and distributed into three values. Similarly, when (U[1], U[2], U[3]) equals Z divided and distributed into three values where Z=U[1]+U[2]+U[3] mod Q, W.Math.W+Z mod Q is divided and distributed into the following three values: (U[1]+U[1] mod Q, U[2]+U[2] mod Q, U[3] +U[3] mod Q). Let's assume that the secret calculation apparatus 10 holds U[1] and U[1], the secret calculation apparatus 20 U[2] and U[2], and the secret calculation apparatus 30 U[3] and U[3]. In this case, each secret calculation apparatus is able to calculate the newly distributed value without communicating with the other secret calculation apparatuses. In other words, when a function is constituted by sums and products mod Q, sum operations can be performed any number of times without having the apparatuses communicate with each other until the input of a next product. When a product is calculated using the result of a product calculation, the next processing should be performed.

(35) In order to divide the logical conjunction W and distribute it among the three secret calculation apparatuses in the same manner as W and W, the product redistributors 38 of the secret calculation apparatuses 10, 20, and 30 are used.

(36) Here, there are randomly selected masks V[1], V[2], and V[3] where V[1]+V[2]+V[3]=0 mod Q, and the mask V[1] is given to the secret calculation apparatus 10, the mask V[2] to the secret calculation apparatus 20, and the mask V[3] to the secret calculation apparatus 30 in advance.

(37) The secret calculation apparatuses 10, 20, and 30 supplies a given mask V[i] to the product redistributor 38. The adder 22 of the secret calculation apparatus 30 calculates the sum of the local product element U[3] and the mask V[3] as in X[3]=U[3]+V[3] mod Q and calls the result a first sum X[3]. Then the communicator 24 of the secret calculation apparatus 30 transmits the derived first sum X[3] to the secret calculation apparatus 20. Similarly, the adder 22 of the secret calculation apparatus 20 generates a first sum X[2]=U[2]+V[2] mod n^2 and transmits the generated first sum X[2] to the secret calculation apparatus 10 via the communicator 24 of the secret calculation apparatus 20. Further, the adder 22 of the secret calculation apparatus 10 generates a first sum X[1]=U[1]+V[1] mod Q and transmits the generated first sum X[1] to the secret calculation apparatus 30 via the communicator 24 of the secret calculation apparatus 10.

(38) The secret calculation apparatuses 10, 20, and 30 receive the first sums X[2], X[3], and X[1], respectively, from the communicators 24 and output the received first sums X[2], X[3], and X[1] to the adder/subtractors 26. Each of the secret calculation apparatuses 10, 20, and 30 calculates an output first element S[i] and an output second element T[i] using the first sums X[1], X[2], and X[3] calculated by its own adder 22 and the received first sums X[2], X[3], and X[1]. More concretely, the adder/subtractor 26 of the secret calculation apparatus 10 calculates (S[1], T[1])=(X[1]X[2] mod Q, 2X[1]X[2] mod Q). Similarly, the adder/subtractor 26 of the secret calculation apparatus 20 calculates (S[2], T[2])=(X[2]X[3] mod Q, 2X[2]X[3] mod Q). Further, the adder/subtractor 26 of the secret calculation apparatus 30 calculates (S[3], T[3])=(X[3]X[1] mod Q, 2X[3]X[1] mod Q).

(39) Without loss of generality, the fact that the value of the logical conjunction W, like W and W, can be restored by two secret calculation apparatuses can be explained on the basis of the restoration method in the case where the secret calculation apparatuses 10 and 20 cooperate with each other. In other words, the logical conjunction W can be restored using the output first element S[1] from the secret calculation apparatus 10 and the output second element T[2] from the secret calculation apparatus 20 as follows.

(40) $W.Math.W^{}=S^{}\left[1\right]-T^{}\left[2\right]\mathrm{mod}Q=U\left[1\right]+V\left[1\right]+U\left[2\right]+U\left[3\right]+V\left[2\right]+V\left[3\right]\mathrm{mod}Q=U\left[1\right]+U\left[2\right]+U\left[3\right]\mathrm{mod}Q=W^{}$

(41) Further, the following calculation shows the logical conjunction W is divided and distributed as W and W.

(42) $S^{}\left[1\right]+S^{}\left[2\right]+S^{}\left[3\right]\mathrm{mod}Q=X\left[1\right]-X\left[2\right]+X\left[2\right]-X\left[3\right]+X\left[3\right]-X\left[1\right]\mathrm{mod}Q=0\mathrm{mod}Q$

(43) (Effects)

(44) By using the secret calculation system relating to the present exemplary embodiment, the sum mod Q of two values divided and distributed among three secret calculation apparatuses can be calculated without having these secret calculation apparatuses communicate with each other and can be held by the three secret calculation apparatuses in a distributed manner. Here, a method for holding the sum calculation result is the same as the method for holding each of the two bits in the beginning.

(45) Further, according to the secret calculation system of the present exemplary embodiment, by calculating the product mod Q of two values divided and distributed among three secret calculation apparatuses while having these secret calculation apparatuses communicate with each other, the calculation result can be held by the three secret calculation apparatuses in a distributed manner. The entire communication amount generated at this time is only 3n bits and is significantly less than the communication amount required in the secret calculation between two apparatuses described in Non-Patent Literature 2. Here, a method for holding the value of the product calculation result is the same as the method for holding each of the two values in the beginning.

(46) As described, both product and sum calculation results are held by the same method as that for holding the values before the calculations. As a result, it becomes possible to further continue product and sum operations on the calculation results. In other words, according to the secret calculation system of the present exemplary embodiment, a function described by sum and product mod Q can be calculated using three secret calculation apparatuses with a small communication amount while the data is divided and distributed.

(47) As described above, according to the present exemplary embodiment, any polynomial mod Q can be calculated while data is distributed and hidden among a plurality of secret calculation apparatuses. Further, the amount of communication and calculation required for such calculation can be reduced, compared with the related technologies. In a case where a service is provided with the secret calculation apparatuses handling secret data, such a secret calculation system also contributes to preventing the administrator of the secret calculation apparatuses from stealing the data. This is because, with different administrators allocated to a plurality of secret calculation apparatuses, no administrator is able to refer to the data in all the secret calculation apparatuses and this will prevent the stealing of the data by an administrator.

Exemplary Embodiment 2

(48) Next, a secret calculation system relating to a second exemplary embodiment will be described with reference to the drawings. FIG. 4 is a block diagram illustrating the configuration of a secret calculation apparatus 10 in the secret calculation system of the present exemplary embodiment. Secret calculation apparatuses 20 and 30 are configured identically to the secret calculation apparatus 10.

(49) In FIG. 4, in the present exemplary embodiment, the secret calculation apparatus 10 further comprises a mask generator 42, compared with the secret calculation apparatus 10 (FIG. 3) of the first exemplary embodiment. The mask generator 42 comprises a key generator 28, a pseudorandom number generator 32, and a subtractor 34. Further, since the operation of the local multiplicator 36 and the product redistributor 38 in the present exemplary embodiment is the same as that of these elements in the first exemplary embodiment, the explanation will be omitted.

(50) In the first exemplary embodiment, it is assumed that the secret calculation apparatuses 10, 20, and 30 receive the random bits V[1], V[2], and V[3] as masks that satisfy V[1]+V[2]+V[3]=0 mod Q. A set of these random bits are required for each product calculation. Therefore, when a large amount of products are calculated, it is desirable that V[i,1], V[i,2], V[i,3] satisfying V[i,1]+V[i,2]+V[i,3]=0 mod Q be generated regarding a large number of i =1, . . . , N. In the present exemplary embodiment, the mask generator 42 achieves this.

(51) Here, K is a safety variable. The key generators 28 of the secret calculation apparatuses 10, 20, and 30 generate K-bit keys L[1], L[2], and L[3]. The communicator 24 of the secret calculation apparatus 10 transmits the generated key L[1] to the secret calculation apparatus 30. Similarly, the communicator 24 of the secret calculation apparatus 20 transmits the generated key L[2] to the secret calculation apparatus 10. Further, the communicator 24 of the secret calculation apparatus 30 transmits the generated key L[3] to the secret calculation apparatus 20.

(52) The communicators 24 of the secret calculation apparatuses 10, 20, and 30 receive the keys L[2], L[3], and L[1] from the secret calculation apparatuses 20, 30, and 10, respectively. The received keys will be referred to as the received keys hereinafter.

(53) The pseudorandom number generator 32 has a pseudorandom number generator PRG. Here, the PRG is a pseudorandom number generator that outputs an nN-bit string from a K-bit string. The pseudorandom number generator 32 of the secret calculation apparatus 10 generates a first pseudorandom number PRG (L[1]) from the key L[1] and a second pseudorandom number PRG (L[2]) from the received key L[2]. The subtractor 34 generates N number of n-bit random numbers by dividing the first and the second pseudorandom numbers PRG (L[1]) and PRG (L[2]) by n bits and deriving the difference mod Q of each. Here, an i.sup.th n-bit random number from the first one is V[i.1] (i=1, . . . , N).

(54) Similarly, the secret calculation apparatus 20 generates a first pseudorandom number PRG (L[2]) and a second pseudorandom number

(55) PRG (L[3]) using the pseudorandom number generator 32, and generates a string of N number of n-bit random numbers from the first and the second pseudorandom numbers PRG (L[2]) and PRG (L[3]) using the subtractor 34. Here, an i.sup.th n-bit random number from the first one is V[i.2] (i=1, . . . , N). Further, the secret calculation apparatus 30 similarly generates a first pseudorandom number PRG (L[3]) and a second pseudorandom number PRG (L[1]) using the pseudorandom number generator 32, and generates a string of N number of n-bit random numbers from the first and the second pseudorandom numbers PRG (L[3]) and PRG (L[1]) using the subtractor 34. Here, an i.sup.th n-bit random number from the first one is V[i.3] (i=1, . . . , N).

(56) The mask generator 42 of the secret calculation apparatus 10 supplies the generated random number V[i.1] (i=1, . . . , N) to the adder 22 of the product redistributor 38. Similarly, the mask generator 42 of the secret calculation apparatus 20 supplies the generated random number V[i.2] to the adder 22 of the product redistributor 38. Further, the mask generator 42 of the secret calculation apparatus 30 supplies the generated random number V[i.3] to the adder 22 of the product redistributor 38.

(57) The secret calculation system relating to the present exemplary embodiment brings the same effects as the secret calculation system relating to the first exemplary embodiment. Further, according to the secret calculation system of the present exemplary embodiment, it becomes possible to perform secret calculations of a large amount of products at high speed by utilizing a mask generated by the mask generator.

(58) Further, the following modes are possible in the present invention.

(59) [Mode 1]

(60) As the secret calculation system relating to the first aspect.

(61) [Mode 2]

(62) The secret calculation system according to Mode 1, wherein the distributed values are
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q),
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q)

(63) when R[1], R[2], R[3] and R[1], R[2], R[3] are n-bit random numbers that satisfy R[1]+R[2]+R[3]=0 mod Q, and R[1]+R[2]+R[3]=0 mod Q (Q is an integer coprime to 3).

(64) [Mode 3]

(65) The secret calculation system according to Mode 1 or 2, wherein the holder holds a local product element U[i]=(S[i].Math.S[i]T[i].Math.T[i])/3 mod Q (Q is an integer coprime to 3) calculated using the first and the second multiplicators and the first subtractor, and the i.sup.th secret calculation apparatus (i=1, 2, 3) comprises:

(66) an adder that derives a sum X[i] of U[i] and V[i];

(67) a communicator that transmits the sum X[i] calculated by the adder to an {(i+1 mod 3)+1}.sup.th secret calculation apparatus and receives a sum X[i mod 3+1] calculated by the adder of an (i mod 3+1).sup.th secret calculation apparatus; and

(68) an adder/subtractor that calculates distributed values (S[i], T[i]) of a product W.Math.W on the basis of addition/subtraction using the sum X[i] and the sum X[i mod 3+1]

(69) when V[1], V[2], and V[3] are n-bit random numbers that satisfy V[1]+V[2]+V[3]=0 mod Q.

(70) [Mode 4]

(71) The secret calculation system according to Mode 3, wherein the distributed values are (S[i], T[i]) =(X[i]X[i mod 3+1] mode Q, 2X[i]X[i mod 3+1]).

(72) [Mode 5]

(73) The secret calculation system according to any one of Modes 1 to 4, wherein

(74) the i.sup.th secret calculation apparatus (i=1, 2, 3) comprises:

(75) a key generator that generates a K-bit key L[i] (K is a natural number); a pseudorandom number generator that generates an nN-bit random number (N is a natural number) from a K-bit key; and

(76) a second subtractor that extracts every n bits from two nN-bit numbers and derives the difference mod Q (Q is an integer coprime to 3), the communicator transmits the key L[i] to an {(i+1 mod 3)+1}.sup.th secret calculation apparatus and receives a key L[i mod 3+1] calculated by the key generator of an (i mod 3+1).sup.th secret calculation apparatus,

(77) the pseudorandom number generator generates a first pseudorandom number on the basis of the key L[i] and generates a second pseudorandom number on the basis of the key L[i mod 3+1], and the second subtractor extracts every n bits from the first and the second pseudorandom numbers and calculates the difference mod Q.

(78) [Mode 6]

(79) The secret calculation system according to Mode 5, wherein the adder of the i.sup.th secret calculation apparatus (i=1, 2, 3) uses a value calculated by the second subtractor as the random number V[i].

(80) [Mode 7]

(81) As the secret calculation apparatus relating to the second aspect.

(82) [Mode 8]

(83) As the secret calculation method relating to the third aspect.

(84) [Mode 9]

(85) The secret calculation method according to Mode 8, wherein the distributed values are
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3])=(R[3], R[2]W mod Q),
(S[1], T[1])=(R[1], R[3]W mod Q),
(S[2], T[2])=(R[2], R[1]W mod Q),
(S[3], T[3]) =(R[3], R[2]W mod Q)

(86) when R[1], R[2], R[3] and R[1], R[2], R[3] are n-bit random numbers that satisfy R[1] +R[2] +R[3] =0 mod Q, and R[1] +R[2] +R[3] =0 mod Q (Q is an integer coprime to 3).

(87) [Mode 10]

(88) The secret calculation method according to Mode 8 or 9 including: having the i.sup.th secret calculation apparatus (i=1, 2, 3) hold a local product element U[i]=(S[i].Math.S[i]T[i].Math.T[i])/3 mod Q (Q is an integer coprime to 3) calculated using the derived difference;

(89) having the i.sup.th secret calculation apparatus derive a sum X[i] of U[i] and V[i];

(90) having the i.sup.th secret calculation apparatus transmit the calculated sum X[i] to an {(i+1 mod 3)+1}.sup.th secret calculation apparatus;

(91) having the i.sup.th secret calculation apparatus receive a sum X[i mod 3+1] calculated by an (i mod 3+1).sup.th secret calculation apparatus; and

(92) having the i.sup.th secret calculation apparatus calculate distributed values (S[i], T[i]) of a product W.Math.W on the basis of addition/subtraction using the sum X[i] and the sum X[i mod 3+1]

(93) when V[1], V[2], and V[3] are n-bit random numbers that satisfy V[1]+V[2]+V[3]=0 mod Q.

(94) [Mode 11]

(95) The secret calculation method according to Mode 10, wherein

(96) the distributed values are (S[i], T[i]) =(X[i]X[i mod 3+1] mode Q, 2X[i]X[i mod 3+1]).

(97) Further, the disclosure of each Non-Patent Literature cited above is incorporated herein in its entirety by reference thereto. It should be noted that other objects, features and aspects of the present invention will become apparent in the entire disclosure and that modifications may be done without departing the gist and scope of the present invention as disclosed herein and claimed as appended herewith. Also it should be noted that any combination of the disclosed and/or claimed elements, matters and/or items may fall under the modifications. Particularly, the ranges of the numerical values used in the present description should be interpreted as a numeric value or small range example included in these ranges even in cases where no explanation is provided.

REFERENCE SIGNS LIST

(98) 10, 20, 30: secret calculation apparatus

(99) 12: holder

(100) 14, 16: multiplicator

(101) 18, 34: subtractor

(102) 22: adder

(103) 24: communicator

(104) 26: adder/subtractor

(105) 28: key generator

(106) 32: pseudorandom number generator

(107) 36: local multiplicator

(108) 38: product redistributor

(109) 42: mask generator

(110) 100: secret calculation system