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

Abstract

A secure computation system for secure exponentiation involving a non-secret base and a secret exponent comprises at least four secure computation server apparatuses connected to each other via a network, and each of the secure computation server apparatuses has: a reshare part that outputs reshares for an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and a multiplication part that performs the secure exponentiation by executing multiplication using shares obtained by having the reshare part reshare the exponent that has been decomposed into additions of shares of the exponent.

Claims

1. A secure computation system for secure exponentiation involving a non-secret base and a secret exponent, comprising at least four secure computation server apparatuses connected to each other via a network, wherein each of the secure computation server apparatuses has: a reshare part that outputs reshares for an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and a multiplication part that performs the secure exponentiation by executing multiplication using shares obtained by having the reshare part reshare the exponent that has been decomposed into additions of shares of the exponent.

2. The secure computation system according to claim 1, wherein each of the secure computation server apparatuses further comprises: an exponential remainder determination part that determines whether or not the exponent exceeds a modulus; and a multiplication correction part that performs multiplication that corrects a value on the basis of a result from the exponential remainder determination part.

3. The secure computation system according to claim 2, wherein the exponential remainder determination part determines whether or not the exponent exceeds a modulus by determining if the least significant bit of the exponent is inverted in each addition of shares of the exponent obtained by decomposing the exponent.

4. The secure computation system according to claim 3, wherein the reshare part outputs reshares of the exponentiation of the exponent with respect to the base for an input including the base and a share of the exponent and outputs reshares of the least significant bit of the exponent for an input including a share of the exponent.

5. A secure computation server apparatus out of at least four secure computation server apparatuses connected to each other via a network that perform secure exponentiation involving a non-secret base and a secret exponent, the secure computation server apparatus including: a reshare part that outputs reshares for an input including at least a share of as the exponent by an operation closed within each of the secure computation server apparatuses; and a multiplication part that performs secure exponentiation by executing multiplication using shares obtained by having the reshare part reshare the exponent that has been decomposed into additions of shares of the exponent.

6. A secure computation method performing secure exponentiation involving a non-secret base and a secret exponent using at least four secure computation server apparatuses connected to each other via a network, the secure computation method including: resharing an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and performing the secure exponentiation by executing multiplication using shares obtained by the resharing the exponent that has been decomposed into additions of shares of the exponent.

7. The secure computation method according to claim 6 further including: an exponential remainder determination whether or not the exponent exceeds a modulus; and a multiplication that corrects a value on the basis of a result from the exponential remainder determination.

8. The secure computation method according to claim 7, wherein the exponential remainder determination determines whether or not the exponent exceeds a modulus by determining if the least significant bit of the exponent is inverted in each addition of shares of the exponent obtained by decomposing the exponent.

9. The secure computation method according to claim 8, wherein the resharing outputs reshares of the exponentiation of the exponent with respect to the base for an input including the base and a share of the exponent and outputs reshares of the least significant bit of the exponent for an input including a share of the exponent.

10. A non-transient computer readable medium storing a secure computation program causing at least four secure computation server apparatuses connected to each other via a network to execute secure exponentiation involving a non-secret base and a secret exponent, the secure computation program including: a resharing process of outputting reshares for an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and a multiplication process of performing the secure exponentiation by executing multiplication using shares obtained in the resharing process by resharing the exponent that has been decomposed into additions of shares of the exponent.

11. The non-transient computer readable medium storing a secure computation program according to claim 10, further including: an exponential remainder determination process of determining whether or not the exponent exceeds a modulus; and a multiplication correction process of performing multiplication that corrects a value on the basis of a result from the exponential remainder determination process.

12. The non-transient computer readable medium storing a secure computation program according to claim 11, wherein the exponential remainder determination process determines whether or not the exponent exceeds a modulus by determining if the least significant bit of the exponent is inverted in each addition of shares of the exponent obtained by decomposing the exponent.

13. The non-transient computer readable medium storing a secure computation program according to claim 12, wherein the resharing process outputs reshares of the exponentiation of the exponent with respect to the base for an input including the base and a share of the exponent and outputs reshares of the least significant bit of the exponent for an input including a share of the exponent.

14. The secure computation server apparatus according to claim 5, further comprises: an exponential remainder determination part that determines whether or not the exponent exceeds a modulus; and a multiplication correction part that performs multiplication that corrects a value on the basis of a result from the exponential remainder determination part.

15. The secure computation server apparatus according to claim 14, wherein the exponential remainder determination part determines whether or not the exponent exceeds a modulus by determining if the least significant bit of the exponent is inverted in each addition of shares of the exponent obtained by decomposing the exponent.

16. The secure computation server apparatus according to claim 15, wherein the reshare part outputs reshares of the exponentiation of the exponent with respect to the base for an input including the base and a share of the exponent and outputs reshares of the least significant bit of the exponent for an input including a share of the exponent.

Description

BRIEF DESCRIPTION OF DRAWINGS

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

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

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

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

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

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

EXAMPLE EMBODIMENTS

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

First Example Embodiment

[0024] The following describes a secure computation system and a secure computation server apparatus relating to a first example embodiment with reference to FIGS. 1 and 2.

[0025] FIG. 1 is a block diagram showing an example of the functional configuration of the secure computation system according to the first example embodiment. As shown in FIG. 1, the secure computation system 100 according to the first example embodiment comprises a first secure computation server apparatus 100_1, a second secure computation server apparatus 1002, a third secure computation server apparatus 100_3, and a fourth secure computation server apparatus 100_4. The first, the second, the third, and the fourth secure computation server apparatuses 100_1, 100_2, 100_3, and 100_4 are connected to each other via a network so as to be able to communicate with each other.

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

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

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

[0029] Further, the secure computation system 100 comprising the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4) is able to verify whether or not there is any fraudulence (for instance, falsification) in the information exchanged among the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4). For instance, the first to the third secure computation server apparatuses 100_i (i=1, 2, 3) are able to verify whether or not there is any fraudulence in information transmitted by the fourth secure computation server apparatus 100_4 to the first to the third secure computation server apparatuses 100_i (i=1, 2, 3) while maintaining confidentiality.

[0030] The first to the third secure computation server apparatuses 100_i (i=1, 2, 3) can verify whether or not there is any fraudulence (for instance, falsification) in the information received from the fourth secure computation server apparatus 100_4 by comparing among the first to the third secure computation server apparatuses 100_i (i=1, 2, 3) the computation results obtained by combining the information received from the fourth secure computation server apparatus 100_4 with the share held by each of the first to the third secure computation server apparatuses 100_i (i=1, 2, 3).

[0031] For instance, in order to be able to verify whether or not there is any fraudulence (for instance, falsification) in the information exchanged among the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4) as described above, shares can be configured as follows.

[0032] Shares of xϵZq for each participant Pi (i=0, 1, 2, 3) are defined as follows.

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

μ.sub.x=x+σ.sub.x mod q

σ.sub.x=σ.sub.x.sup.1+σ.sub.x.sup.2 mod q

μ.sub.x=μ.sub.x.sup.1+μ.sub.x.sup.2 mod q

[x].sub.0.sup.q=(σ.sub.x.sup.1,μ.sub.x.sup.1,μ.sub.x.sup.2)

[x].sub.1.sup.q=(σ.sub.x.sup.1,σ.sub.x.sup.2,μ.sub.x.sup.1)

[x].sub.2.sup.q=(σ.sub.x.sup.2,μ.sub.x.sup.1,μ.sub.x.sup.2)

[x].sub.3.sup.q=(σ.sub.x.sup.1,σ.sub.x.sup.2,μ.sub.x.sup.2)

x=−σ.sub.x.sup.1−σ.sub.x.sup.2+μ.sub.x.sup.1+μ.sub.x.sup.2 mod q  [Math. 1]

[0033] By configuring the shares as above and using the method described in Non-Patent Literature 1, along with normal addition and multiplication, whether or not there is any fraudulence (for instance, falsification) in the information exchanged among the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4) can be verified.

[0034] Next, let us consider exponentiation. The exponentiation discussed herein is secure exponentiation involving a non-secret base and a secret exponent; it is an operation that obtains [b.sup.x].sup.q from b that is not secret-shared and [x].sup.q that is secret-shared.

[b.sup.x].sup.q←exp(b,[x].sup.q),bϵ.sub.q  [Math. 2]

[0035] Here, considering that x=−σ.sub.x.sup.1−σ.sub.x.sup.2+μ.sub.x.sup.1+σ.sub.x.sup.2 mod q, we can decompose b.sup.x as follows.

b.sup.x=b.sup.−σ.sup.x.sup.1.sup.−σ.sup.x.sup.2.sup.+μ.sup.x.sup.1.sup.+μ.sup.x.sup.2=b.sup.−σ.sup.x.sup.1b.sup.−σ.sup.x.sup.2b.sup.μ.sup.x.sup.1b.sup.μ.sup.x.sup.2 mod q  [Math. 3]

[0036] In other words, if each of b{circumflex over ( )}{−σ.sub.x.sup.1}, b{circumflex over ( )}{−σ.sub.x.sup.2}, b{circumflex over ( )}{μ.sub.x.sup.1}, b{circumflex over ( )}{μ.sub.x.sup.2} is obtained, b.sup.x can also be calculated. Note that, since {−σ.sub.x.sup.1, −σ.sub.x.sup.2, μ.sub.x.sup.1, μ.sub.x.sup.2} are values constituting shares distributed to and held in the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4), any one of the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4) cannot obtain all of these values at one time. Moreover, what needs to be derived is the share [b.sup.x].sup.q for obtaining b.sup.x though secure computation.

[0037] Therefore, in the present example embodiment, each of the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4) comprises a reshare part 101_i (i=1, 2, 3, 4) that outputs reshares for an input including at least a share of the exponent x by an operation closed within each apparatus and a multiplication part 102_i (i=1, 2, 3, 4) that performs secure exponentiation by executing multiplication using the reshares obtained by the reshare part 101_i (i=1, 2, 3, 4), as shown in FIG. 2.

[0038] Then, the reshare part 101_i (i=1, 2, 3, 4) receives the base b that is not secret-shared and the exponent [x].sup.q that is secret-shared as an input and outputs reshares of [b.sup.x].sup.q, the result of the exponentiation of the exponent [x].sup.q with respect to the base b, as follows.

([b.sup.−σ.sup.x.sup.1].sup.q,[b.sup.−σ.sup.x.sup.2].sup.q,[b.sup.μ.sup.x.sup.1].sup.q,[b.sup.μ.sup.x.sup.2].sup.q)←Reshare_Exp(b,[x].sup.q)

[b.sup.−σ.sup.x.sup.1].sub.0.sup.q=(b.sup.−σ.sup.x.sup.1,0,0),[b.sup.−σ.sup.x.sup.1].sub.1.sup.q=(b.sup.−σ.sup.x.sup.1,0,0),[b.sup.−σ.sup.x.sup.1].sub.2.sup.q=(0,0,0),[b.sup.−σ.sup.x.sup.1].sub.3.sup.q=(b.sup.−σ.sup.x.sup.1,0,0)

[b.sup.−σ.sup.x.sup.2].sup.q,[b.sup.μ.sup.x.sup.1].sup.q,[b.sup.μ.sup.x.sup.2].sup.q  [Math. 4]

are also defined in the same manner.

[0039] As can be seen from the above definitions, the shares other than the one held within the apparatus are treated as zero in this reshare operation. In other words, a secure computation server apparatus does not need to communicate with the other secure computation server apparatuses in order to obtain the shares that it does not have. This reshare operation is closed within each secure computation server apparatus, and such a reshare process is sometimes called “local reshare”.

[0040] Meanwhile, the multiplication part 102_i (i=1, 2, 3, 4) obtains [b.sup.x].sup.q, the result of the exponentiation of the exponent [x].sup.q with respect to the base b, using the reshares obtained by the reshare part 101_i (i=1, 2, 3, 4) as follows.

[b.sup.x].sup.q=[b.sup.−σ.sup.x.sup.1.sup.−σ.sup.x.sup.2.sup.+μ.sup.x.sup.1.sup.+μ.sup.x.sup.2].sup.q=[b.sup.−σ.sup.x.sup.1].sup.q.Math.[b.sup.−.sup.x.sup.2].sup.q.Math.[b.sup.μ.sup.x.sup.1].sup.q.Math.[b.sup.μ.sup.x.sup.2].sup.q  [Math. 5]

[0041] As described, in the present example embodiment, the exponentiation that obtains [b.sup.x].sup.q from b that is not secret-shared and [x].sup.q that is secret-shared as an input can be performed by providing in each of the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4): the reshare part 101_i (i=1, 2, 3, 4) that outputs reshares for an input including at least a share of the exponent x by an operation closed within each of the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4); and the multiplication part 102_i (i=1, 2, 3, 4) that performs secure exponentiation by executing multiplication using shares obtained by having the reshare part 101_i (i=1, 2, 3, 4) reshare the exponent x that has been decomposed into additions of shares of the exponent.

[0042] Further, it becomes possible to contribute to definitive fraud detection in secure exponentiation since the secure computation system 100 comprises the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4) and is able to verify whether or not there is any fraudulence (for instance, falsification) in the information exchanged among the first to the fourth secure computation server apparatuses 100_i (i=1, 2, 3, 4).

Second Example Embodiment

[0043] Next, the following describes an example embodiment in which the secure exponentiation described in the first example embodiment is more concretely implemented. In the first example embodiment, exponentiation is simply decomposed into products, however, sometimes this alone may not be sufficient. For instance, if the modulus q is a prime p and Fermat's little theorem is used, b.sup.x=b.sup.x′+kq=b.sup.x′+k mod q. Then, if the exponent x exceeds the modulus q, the exponentiation result b.sup.x must be multiplied by b.sup.1. In the second example embodiment, the case where the modulus q is a prime p (q=p) will be described.

[0044] FIG. 3 is a block diagram showing an example of the functional configuration of a secure computation system according to the second example embodiment. As shown in FIG. 3, the secure computation system 200 according to the second example embodiment comprises a first secure computation server apparatus 200_1, a second secure computation server apparatus 200_2, a third secure computation server apparatus 200_3, and a fourth secure computation server apparatus 200_4. The first, the second, the third, and the fourth secure computation server apparatuses 200_1, 200_2, 200_3, and 200_4 are connected to each other via a network so as to be able to communicate with each other.

[0045] In addition to being able to perform secure computation in the same manner as in the first example embodiment, the secure computation system 200 comprising the first to the fourth secure computation server apparatuses 200_i (i=1, 2, 3, 4) is also able to verify whether or not there is any fraudulence (for instance, falsification) in information exchanged among the first to the fourth secure computation server apparatuses 200_i (i=1, 2, 3, 4).

[0046] Further, as shown in FIG. 4, each of the first to the fourth secure computation server apparatuses 200_i (i=1, 2, 3, 4) comprises a reshare part 201_i (i=1, 2, 3, 4) that outputs reshares for an input including at least a share of the exponent x by an operation closed within each apparatus and a multiplication part 202_i (i=1, 2, 3, 4) that performs secure exponentiation by executing multiplication using the reshares obtained by the reshare part 201_i (i=1, 2, 3, 4).

[0047] In addition, each of the first to the fourth secure computation server apparatuses 200_i (i=1, 2, 3, 4) comprises an exponential remainder determination part 203_i (i=1, 2, 3, 4) that determines whether or not the exponent x exceeds the modulus p and a multiplication correction part 204_i (i=1, 2, 3, 4) that performs multiplication that corrects a value on the basis of a result from the exponential remainder determination part 203_i (i=1, 2, 3, 4).

[0048] Shares are configured in the same manner as in the first example embodiment. In other words, shares of xϵZq for each participant Pi (i=0, 1, 2, 3) are defined as follows.

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

μ.sub.x=x+σ.sub.x mod q,σ.sub.x=σ.sub.x.sup.1+σ.sub.x.sup.2 mod q,μ.sub.x=μ.sub.x.sup.1+μ.sub.x.sup.2 mod q

[x].sub.0.sup.q=(σ.sub.x.sup.1,μ.sub.x.sup.1,μ.sub.x.sup.2)

[x].sub.1.sup.q=(σ.sub.x.sup.1,μ.sub.x.sup.2,μ.sub.x.sup.1)

[x].sub.2.sup.q=(σ.sub.x.sup.2,μ.sub.x.sup.1,μ.sub.x.sup.2)

[x].sub.3.sup.q=(σ.sub.x.sup.1,μ.sub.x.sup.2,μ.sub.x.sup.2)

x=−σ.sub.x.sup.1−σ.sub.x.sup.2+μ.sub.x.sup.1+μ.sub.x.sup.2 mod q  [Math. 6]

[0049] Here, as described above, if p is a prime and Fermat's little theorem is used, b.sup.x=b.sup.x′+kq=b.sup.x′+k mod q. Meanwhile, given that x=−σ.sub.x.sup.1−σ.sub.x.sup.2+μ.sub.x.sup.1+μ.sub.x.sup.2, kϵ{0, 1, 2, 3}. In other words, the exponent x can exceed the modulus p by at most three times.

[0050] The exponential remainder determination part 203_i (i=1, 2, 3, 4) determines whether or not the exponent exceeds the modulus in additions of exponent shares obtained by decomposing the exponent. Specifically, the exponential remainder determination part determines whether or not the exponent exceeds the modulus in three additions: −σ.sub.x.sup.1−σ.sub.x.sup.2, (−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1, and ((−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1)+σ.sub.x.sup.2.

[0051] One can determine whether or not the exponent exceeds the modulus by noting that the modulus p is a prime and that the parity is reversed when the exponent exceeds the modulus p. For instance, if a0 is even and a1 is odd, a0+a1 is even when (1) a0+a1 exceeds the modulus. Meanwhile, if (1) a0+a1 does not exceed the modulus, a0+a1 is odd. Further, one can determine whether the parity is reversed by looking for an inversion of the least significant bit.

(Secure Computation Method)

[0052] The following describes a secure computation method in detail. FIG. 5 is a flowchart showing an outline of the procedure of the secure computation method.

[0053] In step A1, resharing is performed. In other words, reshares of b.sup.x, the result of the exponentiation of the exponent x with respect to the base b, are calculated for an input including the base b and a share of the exponent x, and reshares of the least significant bit of the exponent x are calculated for an input including a share of the exponent x. Specifically, the following calculations are performed.

([b.sup.−σ.sup.x.sup.1].sup.q,[b.sup.−σ.sup.x.sup.2],[b.sup.μ.sup.x.sup.1].sup.q,[b.sup.μ.sup.x.sup.2].sup.q)←Reshare_Exp(b,[x].sup.q)

[b.sup.−σ.sup.x.sup.1].sub.0.sup.q=(b.sup.−σ.sup.x.sup.1,0,0),[b.sup.−σ.sup.x.sup.1].sub.1.sup.q=(b.sup.−σ.sup.x.sup.1,0,0,),[b.sup.−σ.sup.x.sup.1].sub.2.sup.q=(0,0,0),[b.sup.−σ.sup.x.sup.1].sub.3.sup.q=(b.sup.−σ.sup.x.sup.1,0,0)

[b.sup.−σ.sup.x.sup.2].sup.q,[b.sup.μ.sup.x.sup.1].sup.q,[b.sup.μ.sup.x.sup.2].sup.q  [Math. 7]

are also defined in the same manner.

([−σ.sub.x.sup.1].sup.q,[−σ.sub.x.sup.2].sup.q,[μ.sub.x.sup.1].sup.q,[μ.sub.x.sup.2].sup.q)←Reshare([x].sup.q)

[−σ.sub.x.sup.1].sup.q,[−σ.sub.x.sup.2].sup.q,[μ.sub.x.sup.1].sup.q,[μ.sub.x.sup.2].sup.q

are also defined in the same manner as above.

{([−σ.sub.x.sup.1|.sub.j].sup.q,[−σ.sub.x.sup.2|.sub.j].sup.q,[μ.sub.x.sup.1|.sub.j].sup.q,[μ.sub.x.sup.2|.sub.j].sup.q)}.sub.j=0.sup.log(q)←Reshare_Bit([x]4)

[−σ.sub.x.sup.1|.sub.j].sup.q,[−σ.sub.x.sup.2|.sub.j].sup.q,[μ.sub.x.sup.1|.sub.j].sup.q,[μ.sub.x.sup.2|.sub.j].sup.q

are also defined in the same manner as above.

[0054] In step A2, the exponential remainder is determined. In other words, whether or not the exponent x exceeds the modulus is determined. For this, the following calculations are performed.

[0055] Using the results of the resharing in the step A1, the following calculations are executed. Note that the values below appear to give the shares of the exponentiation result, but do not give the proper value when the exponent x exceeds the modulus, as mentioned above.

[res.sub.0].sup.p=[b.sup.−σ.sup.x.sup.1].sup.p.Math.[b.sup.−σ.sup.x.sup.2].sup.p.Math.[b.sup.μ.sup.x.sup.1].sup.p.Math.[b.sup.μ.sup.x.sup.2].sup.p  [Math. 8]

[0056] Then, as described above, whether or not the exponent x exceeds the modulus p is determined by finding out if the exponent exceeds the modulus in three additions: −σ.sub.x.sup.1−σ.sub.x.sup.2, (−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1, and ((−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1)+μ.sub.x.sup.2. [0057] (1) Determine whether−σ.sub.x.sup.1−σ.sub.x.sup.2 exceeds the modulus. Note that LSB in the calculations below denotes the least significant bit. Further, [k.sub.0].sup.p is a variable designed to be one when −σ.sub.x.sup.1−σ.sub.x.sup.2 exceeds the modulus p and zero otherwise. Logical operations appear in the middle thereof to determine if the parity is reversed, but the calculation boils down to the computation of the least significant bit.

[l.sub.0].sup.p=LSB([−σ.sub.x.sup.1].sup.p+[−σ.sub.x.sup.2].sup.p)

[k.sub.0].sup.p=[−σ.sub.x.sup.1−σ.sub.x.sup.2>p]=[((−σ.sub.x.sup.1)|.sub.0⊕(−σ.sub.x.sup.2)|.sub.0)≠l.sub.0].sup.p

=[(−σ.sub.x.sup.1)|.sub.0⊕(−σ.sub.x.sup.2)|.sub.0⊕l.sub.0].sup.p=(([−σ.sub.x.sup.1|.sub.0].sup.p−[−σ.sub.x.sup.2|.sub.0].sup.p).sup.2−[−l.sub.0].sup.p).sup.2  [Math. 9] [0058] (2) Determine if (−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1 exceeds the modulus. In the calculations below, [k.sub.1].sup.p is a variable designed to be one when (−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1 exceeds the modulus p and zero otherwise.

[l.sub.1].sup.p=LSB([−σ.sub.x.sup.1].sup.p+[−σ.sub.x.sup.2].sup.p+[μ.sub.x.sup.1].sup.p)

[k.sub.1].sup.p=[l.sub.0⊕μ.sub.x.sup.1|.sub.0⊕l.sub.1].sup.p=(([l.sub.0].sup.p−[μ.sub.x.sup.1|.sub.0].sup.p).sup.2−[l.sub.1].sup.p).sup.2   [Math. 10] [0059] (3) Determine whether or not ((−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1)+μ.sub.x.sup.2 exceeds the modulus. In the calculations below, [k.sub.2].sup.p is a variable designed to be one when ((−σ.sub.x.sup.1−σ.sub.x.sup.2)+μ.sub.x.sup.1)+μ.sub.x.sup.2 exceeds the modulus p and zero otherwise.

[l.sub.2].sup.p=LSB([−σ.sub.x.sup.1].sup.p+[−σ.sub.x.sup.2].sup.p+[μ.sub.x.sup.1].sup.p+[μ.sub.x.sup.2].sup.p)

[k.sub.2].sup.p=[l.sub.1⊕μ.sub.x.sup.2|.sub.0l.sub.2].sup.p=(([l.sub.1].sup.p−[μ.sub.x.sup.2|.sub.0].sup.p).sup.2−[l.sub.2].sup.p).sup.2  [Math. 11]

[0060] In step A3, multiplication correction is performed. In other words, the value is corrected on the basis of the results from the exponential remainder determination in the step A2. Using [k.sub.0].sup.p, [k.sub.1].sup.p, and [k.sub.2].sup.p calculated as above, [res.sub.0].sup.p is corrected as follows.

[res.sub.1].sup.p=(1−[k.sub.0].sup.p).Math.[res.sub.0].sup.p+[k.sub.0].sup.p.Math.b.sup.−1.Math.[res.sub.0].sup.p

[res.sub.2].sup.p=(1−[k.sub.1].sup.p).Math.[res.sub.1].sup.p+[k.sub.1].sup.p.Math.b.sup.−1[res.sub.1].sup.p

[res.sub.3].sup.p=(1−[k.sub.2].sup.p).Math.[res.sub.2].sup.p+[k.sub.2].sup.p.Math.b.sup.−1.Math.[res.sub.2].sup.p  [Math. 12]

[0061] Since [k.sub.0].sup.p, [k.sub.1].sup.p, and [k.sub.2].sup.p are one when the exponent exceeds the modulus and are zero otherwise, the right sides of the above formulas are multiplied by b.sup.−1 when the exponent exceeds the modulus.

[0062] In step A4, the corrected [res.sub.3].sup.p is outputted as the result [b.sup.x].sup.q of the exponentiation of the exponent x with respect to the base b.

[0063] As described, in the present example embodiment, even in the case where the modulus p is a prime, whether or not the exponent x exceeds the modulus p is determined, and the exponentiation that obtains [b.sup.x].sup.q can be performed from the base b that is not secret-shared and the exponent [x].sup.p that is secret-shared as an input.

[0064] Further, it becomes possible to contribute to definitive fraud detection in secure exponentiation since the secure computation system 200 comprises the first to the fourth secure computation server apparatuses 200_i (i=1, 2, 3, 4) and is able to verify whether or not there is any fraudulence (for instance, falsification) in the information exchanged among the first to the fourth secure computation server apparatuses 200_i (i=1, 2, 3, 4).

Third Example Embodiment

[0065] Next, the following describes an example embodiment in which the secure exponentiation described in the second example embodiment is modified. The exponent could exceed the modulus three times in the second example embodiment, however, if the base and the exponent have different moduli, the number of conditional determinations can be reduced in some cases.

[0066] For instance, let us consider a case where a base modulo p′ and an exponent modulo q′ are primes satisfying p′=3q′+1 and [b.sup.x].sup.p′←exp(b, [x].sup.q′) is executed. Here, if −σ.sub.x.sup.1, −σ.sub.x.sup.2, μ.sub.x.sup.1, μ.sub.x.sup.2ϵ[0, q′−1] and bϵ[0, p′−1], the number of times x=−σ.sub.x.sup.1−σ.sub.x.sup.2+μ.sub.x.sup.1+μ.sub.x.sup.2 exceeds the modulus can be reduced to one.

[0067] Here, further description is omitted because the configuration and the calculation procedures described in the second example embodiment can also be used in the present example embodiment, and the exponentiation that obtains [b.sup.x].sup.p can also be performed from the base b that is not secret-shared and the exponent [x].sup.p that is secret-shared as an input in the present example embodiment. Further, it becomes possible to contribute to definitive fraud detection in secure exponentiation since whether or not there is any fraudulence (for instance, falsification) in the exchanged information can also be verified in the present example embodiment.

Fourth Example Embodiment

[0068] Next, the following describes an example embodiment in which the modulus is a power of two. When the modulus is a power of two, i.e., when q=2.sup.m, bϵZ.sub.2.sup.m and the exponentiation that obtains [b.sup.x].sup.q from b that is not secret-shared and [x].sup.q that is secret-shared as an input can be performed as follows. Note, however, that only cases where the base b is odd are considered here.

[b.sup.x].sup.2.sup.m←exp(b,[x].sup.2.sup.m),bϵZ.sub.2.sub.m  [Math. 13]

[0069] In this case, as in the first example embodiment, from the base b that is not secret-shared and the exponent [x].sup.q that is secret-shared as an input, reshares of [b.sup.x].sup.q, the result of the exponentiation of the exponent [x].sup.q with respect to the base b, can be defined.

([b.sup.−σ.sup.x.sup.1].sup.2.sup.m,[b.sup.−σ.sup.x.sup.2].sup.2.sup.m,[b.sup.μ.sup.x.sup.1].sup.2.sup.m,[b.sup.μ.sup.x.sup.2].sup.2.sup.m)←Reshare_Exp(b,[x].sup.2.sup.m)

[b.sup.−σ.sup.x.sup.1].sub.0.sup.2.sup.m=(b.sup.−σ.sup.x.sup.1,0,0),[b.sup.−σ.sup.x.sup.1].sub.1.sup.2.sup.m=(b.sup.−σ.sup.x.sup.1,0,0),[b.sup.−σ.sup.x.sup.1].sub.2.sup.2.sup.m=(0,0,0),[b.sup.−σ.sup.x.sup.1].sub.3.sup.2.sup.m=(b.sup.−σ.sup.x.sup.1,0,0)

[b.sup.−σ.sup.x.sup.2].sup.2.sup.m,[b.sup.μ.sup.x.sup.1].sup.2.sup.m,[b.sup.μ.sup.x.sup.2].sup.2.sup.m  [Math. 14]

are also defined in the same manner.

[0070] Here, whether or not a correction also needs to be made when the exponent x exceeds the modulus, as is the case with a prime modulus, will be examined in the case of the present example embodiment (when the modulus is a power of two).

[0071] If base b is odd, the base b and the modulus 2.sup.m are mutually prime. Then, the following relational expression holds from Euler's theorem.

b.sup.2.sup.m-1=1 mod 2.sup.m

b.sup.2.sup.m=(b.sup.2.sup.m-1).Math.(b.sup.2.sup.m-1)=1 mod 2.sup.m  [Math. 15]

[0072] In other words, no correction is required even when the exponent exceeds 2.sup.m. Therefore, the exponentiation of the exponent [x].sup.q with respect to the base b can be performed by executing the following calculation using the reshares above.

[b.sup.x].sup.2.sup.m=[b.sup.−σ.sup.x.sup.1.sup.−σ.sup.x.sup.2.sup.+μ.sup.x.sup.1.sup.+μ.sup.x.sup.2].sup.2.sup.m=([b.sup.−σ.sup.x.sup.1].sup.2.sup.m.Math.[b.sup.−σ.sup.x.sup.2].sup.2.sup.m).Math.([b.sup.μ.sup.x.sup.1].sup.2.sup.m.Math.[b.sup.μ.sup.x.sup.2].sup.2.sup.m)  [Math. 16]

[0073] Further description is omitted because the configuration and the calculation procedures described in the first example embodiment can also be used in the present example embodiment, and the exponentiation that obtains [b.sup.x].sup.p can also be performed from the base b that is not secret-shared and the exponent [x].sup.p that is secret-shared as an input in the present example embodiment. Further, it becomes possible to contribute to definitive fraud detection in secure exponentiation since whether or not there is any fraudulence (for instance, falsification) in the exchanged information can also be verified in the present example embodiment.

[Hardware Configuration]

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

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

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

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

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

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

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

[Supplementary Note 1]

[0081] A secure computation system for secure exponentiation involving a non-secret base and a secret exponent comprising at least four secure computation server apparatuses connected to each other via a network, wherein [0082] each of the secure computation server apparatuses has: [0083] a reshare part that outputs reshares for an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and [0084] a multiplication part that performs the secure exponentiation by executing multiplication using shares obtained by having the reshare part reshare the exponent that has been decomposed into additions of shares of the exponent.

[Supplementary Note 2]

[0085] The secure computation system according to Supplementary Note 1, wherein [0086] each of the secure computation server apparatuses further comprises: an exponential remainder determination part that determines whether or not the exponent exceeds a modulus; and [0087] a multiplication correction part that performs multiplication that corrects a value on the basis of a result from the exponential remainder determination part.

[Supplementary Note 3]

[0088] The secure computation system according to Supplementary Note 2, wherein the exponential remainder determination part determines whether or not the exponent exceeds a modulus by determining if the least significant bit of the exponent is inverted in each addition of shares of the exponent obtained by decomposing the exponent.

[Supplementary Note 4]

[0089] The secure computation system according to Supplementary Note 3, wherein the reshare part outputs reshares of the exponentiation of the exponent with respect to the base for an input including the base and a share of the exponent and outputs reshares of the least significant bit of the exponent for an input including a share of the exponent.

[Supplementary Note 5]

[0090] A secure computation server apparatus out of at least four secure computation server apparatuses connected to each other via a network, the secure computation server apparatus including: [0091] a reshare part that outputs reshares for an input including at least a share of an exponent by an operation closed within each of the secure computation server apparatuses; and [0092] a multiplication part that performs secure exponentiation by executing multiplication using shares obtained by having the reshare part reshare the exponent that has been decomposed into additions of shares of the exponent.

[Supplementary Note 6]

[0093] A secure computation method performing secure exponentiation involving a non-secret base and a secret exponent using at least four secure computation server apparatuses connected to each other via a network, the secure computation method including: [0094] a resharing step of outputting reshares for an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and [0095] a multiplication step of performing the secure exponentiation by executing multiplication using shares obtained in the resharing step by resharing the exponent that has been decomposed into additions of shares of the exponent.

[Supplementary Note 7]

[0096] The secure computation method according to Supplementary Note 6 further including: [0097] an exponential remainder determination step of determining whether or not the exponent exceeds a modulus; and [0098] a multiplication correction step of performing multiplication that corrects a value on the basis of a result from the exponential remainder determination part.

[Supplementary Note 8]

[0099] The secure computation method according to Supplementary Note 7, wherein the exponential remainder determination step determines whether or not the exponent exceeds a modulus by determining if the least significant bit of the exponent is inverted in each addition of shares of the exponent obtained by decomposing the exponent.

[Supplementary Note 9]

[0100] The secure computation method according to Supplementary Note 8, wherein the resharing step outputs reshares of the exponentiation of the exponent with respect to the base for an input including the base and a share of the exponent and outputs reshares of the least significant bit of the exponent for an input including a share of the exponent.

[Supplementary Note 10]

[0101] A secure computation program causing at least four secure computation server apparatuses connected to each other via a network to execute secure exponentiation involving a non-secret base and a secret exponent, the secure computation program including: [0102] a resharing process of outputting reshares for an input including at least a share of the exponent by an operation closed within each of the secure computation server apparatuses; and [0103] a multiplication process of performing the secure exponentiation by executing multiplication using shares obtained in the resharing process by resharing the exponent that has been decomposed into additions of shares of the exponent.

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

REFERENCE SIGNS LIST

[0105] 100, 200: secure computation system [0106] 100_i, 200_i: secure computation server apparatus [0107] 101_i, 201_i: reshare part [0108] 102_i, 202_i: multiplication part [0109] 203_i: exponential remainder determination part [0110] 204_i: multiplication correction part [0111] 10: hardware configuration [0112] 11: CPU (Central Processing Unit) [0113] 12: primary storage device [0114] 13: auxiliary storage device [0115] 14: IF (Interface) part