SECURE COMPUTATION SYSTEM, SECURE COMPUTATION SERVER APPARATUS, SECURE COMPUTATION METHOD, AND SECURE COMPUTATION PROGRAM
20240146505 ยท 2024-05-02
Assignee
Inventors
Cpc classification
International classification
Abstract
An secure computation server apparatus in a secure computation system includes: a local shuffle part that computes, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses and sends the permuted values of the share to the remaining secure computation server apparatus; a comparison and verification part that compares values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value, and adopts the values that are same at least two values as an accurate permutation; and a shuffle synthesis part that synthesizes mini-shuffles, by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts.
Claims
1. A secure computation system, which includes five secure computation server apparatuses connected to each other via a network, an individual one of the secure computation server apparatuses comprising: a local shuffle part that computes, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses and sends the permuted values of the share to the remaining secure computation server apparatus; a comparison and verification part that compares values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value, and adopts the values that are same at least two values as an accurate permutation; and a shuffle synthesis part that synthesizes, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts.
2. The secure computation system according to claim 1; wherein the mini-shuffles are each determinably generated by using seeds held by the four secure computation server apparatuses and an identifier held by the five secure computation server apparatuses as input and are each masked by pseudo random numbers whose total is zero regarding the five secure computation server apparatuses.
3. The secure computation system according to claim 1; wherein the shared permutation is determinably generated by using a seed shared by the four secure computation server apparatuses as input.
4. The secure computation system according to claim 1; wherein the comparison and verification part determines that the received values are each an accurate value by determining that hash values of the received values are same.
5. A secure computation server apparatus, which is one of five secure computation server apparatuses connected to each other via a network, the secure computation server apparatus comprising: a local shuffle part that computes, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses and sends the permuted values of the share to the remaining secure computation server apparatus; a comparison and verification part that compares values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value, and adopts the values that are same at least two values as an accurate permutation; and a shuffle synthesis part that synthesizes, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts.
6. A secure computation method, which uses five secure computation server apparatuses connected to each other via a network, the secure computation method comprising: causing an individual one of the secure computation server apparatuses to compute, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses; causing the individual one of the secure computation server apparatuses to send the permuted values of the share to the remaining secure computation server apparatus; causing the individual one of the secure computation server apparatuses to compare values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value; causing the individual one of the secure computation server apparatuses to adopt the values that are same at least two values as an accurate permutation; and causing the individual one of the secure computation server apparatuses to synthesize, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a corresponding permutation adopted.
7. The secure computation method according to claim 6; wherein the mini-shuffles are each determinably generated by using seeds held by the four secure computation server apparatuses and an identifier held by the five secure computation server apparatuses as input and are each masked by pseudo random numbers whose total is zero regarding the five secure computation server apparatuses.
8. The secure computation method according to claim 6; wherein the shared permutation is determinably generated by using a seed shared by the four secure computation server apparatuses as input.
9. The secure computation method according to claim 6; wherein it is determined that the permuted values of the share are each an accurate value by determining that hash values of the received values are same.
10. A non-transient computer readable medium storing a secure computation program, causing at least five secure computation server apparatuses connected to each other via a network to perform a secure computation, the program comprising: computing, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses; sending the permuted values of the share to the remaining secure computation server apparatus; comparing values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value; adopting the values that are same at least two values as an accurate permutation; and synthesizing, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a corresponding permutation adopted.
11. The secure computation server apparatus according to claim 5; wherein the mini-shuffles are each determinably generated by using seeds held by the four secure computation server apparatuses and an identifier held by the five secure computation server apparatuses as input and are each masked by pseudo random numbers whose total is zero regarding the five secure computation server apparatuses.
12. The secure computation server apparatus according to claim 5; wherein the shared permutation is determinably generated by using a seed shared by the four secure computation server apparatuses as input.
13. The secure computation server apparatus according to claim 5; wherein the comparison and verification part determines that the received values are each an accurate value by determining that hash values of the received values are same.
14. The non-transient computer readable medium storing the secure computation program according to claim 10; wherein the mini-shuffles are each determinably generated by using seeds held by the four secure computation server apparatuses and an identifier held by the five secure computation server apparatuses as input and are each masked by pseudo random numbers whose total is zero regarding the five secure computation server apparatuses.
15. The non-transient computer readable medium storing the secure computation program according to claim 10; wherein the shared permutation is determinably generated by using a seed shared by the four secure computation server apparatuses as input.
16. The non-transient computer readable medium storing the secure computation program according to claim 10; wherein it is determined that the permuted values of the share are each an accurate value by determining that hash values of the received values are same.
Description
BRIEF DESCRIPTION OF DRAWINGS
[0018]
[0019]
[0020]
[0021]
[0022]
[0023]
DESCRIPTION OF EMBODIMENTS
[0024] Hereinafter, example embodiments of the present invention will be described with reference to the accompanying drawings. However, the present invention is not limited to the following example embodiments. In addition, in the drawings, the same or equivalent elements are denoted by the same reference characters, as necessary. In addition, the drawings are schematic drawings, and therefore, it should be noted that the sizes, ratios, etc. of the individual elements may differ from their actual sizes, ratios, etc. An element in a drawing may have a portion whose size or ratio differs from that of the portion of the element in a different drawing.
First Example Embodiment
[0025] Hereinafter, a secure computation system and secure computation server apparatuses according to a first example embodiment will be described with reference to
[0026]
[0027] In the secure computation system 100 including the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from a value inputted to any one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) while keeping the input value and the values acquired in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4).
[0028] In addition, in the secure computation system 100 including the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from the shares dispersedly stored in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) while keeping the values in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4).
[0029] The shares of the computation results may be reconstructed by causing the first to fifth secure computation server apparatuses 100_0 to 100_4 to exchange their shares with each other. Alternatively, the shares may be decoded by transmitting the shares to an external apparatus other than the first to fifth secure computation server apparatuses 100_0 to 100_4.
[0030] In addition, in the secure computation system 100 including the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), even when one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is operated by a dishonest person, it is possible to continue an accurate secure computation without stopping the processes.
[0031] For example, the following construction may be adopted as the construction of the shares that enables continuation of an accurate secure computation without stopping the processes even when one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) is operated by a dishonest person as described above.
[0032] Shares of an element x of a residue class ring Z.sub.n of modulo n, that is, x?Z.sub.n, on the residue class ring Z.sub.n are defined as follows (the shares may be referred to as arithmetic shares, as necessary). Note that n=2.sup.m, where m is an integer of 2 or more. That is, a residue class ring Z.sub.2 of modulo 2 is distinguished from the residue class ring Z.sub.n of modulo n.
[0033] An element x of the residue class ring Z.sub.n of modulo n, that is, x?Z.sub.n, is decomposed to satisfy the following relationship: [0034] x=x.sub.0+x.sub.1+x.sub.2+x.sub.3+x.sub.4 mod n [0035] [x].sub.i dispersedly held by the individual participants P.sub.i, (i=0, 1, 2, 3, 4) is defined as follows. [0036] [x].sub.i=(x.sub.i, x.sub.i+1, x.sub.i+2, x.sub.i+3, note that x.sub.4+1=x.sub.0
[0037] Shares of an element x of the residue class ring Z.sub.2 of modulo 2, that is, x?Z.sub.2, on the residue class ring Z.sub.2 (the shares may be referred to as logic shares, as necessary) are defined in the same way as the above shares on the residue class ring Z.sub.n where n=2. However, a different notation [x].sup.B is used to distinguish the residue class ring Z.sub.2 of modulo 2 from the residue class ring Z.sub.n of modulo n. That is, the shares are specifically defined as follows.
[0038] An element x of the residue class ring Z.sub.2 of modulo 2, that is, x?Z.sub.2, is decomposed as follows. In Equation 1, + inside a circle represents an exclusive-or.
x=x.sub.0?x.sub.1?x.sub.2?x.sub.3?x.sub.4 mod 2[Equation 1]
[0039] [x].sup.B.sub.i dispersedly held by the individual participants P.sub.i, (i=0, 1, 2, 3, 4) is defined as follows. [0040] [x].sup.B.sub.i=(x.sub.i, x.sub.i+1, x.sub.i+2, x.sub.i+3), note that x.sub.4+1=x.sub.0
[0041] If these shares [x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, and [x].sub.4 held by the individual participants P.sub.i, (i=0, 1, 2, 3, 4) are determined as described above, the individual participants P.sub.i, (i=0, 1, 2, 3, 4) cannot reconstruct x from their shares [x].sub.0, [x].sub.1, [x].sub.2, [x].sub.3, and [x].sub.4 held thereby. However, it is possible to realize secret sharing in which x can be reconstructed if the shares held by at least two of the participants P.sub.i (i=0, 1, 2, 3, 4) are combined. This secret sharing scheme is referred to as a 2-out-of-5 Replicated Secret Sharing Scheme.
[0042] Herein, a shuffle is used when a share sequence constructed as described above is dispersedly held by the individual participant. That is, an individual component x.sub.j of a sequence having a sequence length M is decomposed into shares as follows, and the shares are dispersedly held by the individual participants P.sub.i (i=0, 1, 2, 3, 4).
{right arrow over (x)}=(x.sub.0, . . . ,x.sub.1, . . . ,x.sub.M?1)
x.sub.j=x.sub.j,0+x.sub.j,1+x.sub.j,2+x.sub.j,3+x.sub.j,4 mod L
{right arrow over (x.sub.i)}=(x.sub.0,i, . . . ,x.sub.M?1,i)(i=0,1,2,3,4)[Equations 2]
[0043] In this secure computation based on the secret sharing scheme, not only when x is reconstructed but also when the locations in a sequence are shuffled, there is a situation in which the individual participants directly or indirectly receive the values of the sub-shares not held thereby from other participants. This is because it is necessary to shuffle the locations in a sequence while maintaining the values indicated by the shares held in a secret sharing manner by the individual participants. In addition, it is necessary that the values indicated by the shares be maintained even after the locations in the sequence are changed without letting the individual participants know the values indicated by their shares held thereby.
[0044] Thus, when a bit conversion is performed, too, there is a situation in which the individual participants also directly or indirectly receive the values of the sub-shares not held thereby from other participants. In this situation, if one of the other participants is a dishonest person, a participant could receive a different value instead of a value that the participant is originally supposed to receive. If this happens, the secure computation is performed based on an erroneous value, resulting in an erroneous result. In some cases, the computation itself cannot be performed properly.
[0045] To solve this problem, in the secure computation system 100 according to the present example embodiment, as illustrated in
[0046] The local shuffle part 101_i computes, by using a shared permutation shared by four of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), permuted values of a share for a remaining one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) and sends the permuted values of the share to the remaining secure computation server apparatus. The comparison and verification part 102_i compares the permuted values of the share with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be the same value, and adopts the values that are same at least two values as an accurate permutation. The shuffle synthesis part 103_i synthesizes, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts 102_i.
[0047] As described above, in the secure computation system 100 according to the present example embodiment, an individual one of the four of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) permutes the locations of its sub-shares by using a permutation completed thereby and also performs a permutation for the remaining one of the secure computation server apparatuses. This remaining secure computation server apparatus receives the sub-shares permuted by the four secure computation server apparatuses from these four secure computation server apparatuses, compares the permuted values of the share, which are received from at least three of the four secure computation server apparatuses and which are supposed to be the same value, and adopts the values that are same at least two values as an accurate permutation. As a result, mini-shuffles are constructed in the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4).
[0048] It should be noted here that, since each of the four secure computation server apparatuses completes a permutation by itself, each computation server apparatus knows how the locations in the share sequence have been permuted, and that because the remaining one of the secure computation server apparatuses receives a permuted result, this remaining secure computation server apparatus does not know how the locations in the share sequence have been permuted. Thus, regarding the five combinations of four secure computation server apparatuses selected from the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4), if all the mini-shuffles constructed as described above are synthesized, a permutation (shuffle) that cannot be traced by any one of the first to fifth secure computation server apparatuses 100_i (i=0, 1, 2, 3, 4) can be constructed.
[0049] Next, a secure computation method according to the present example embodiment will be described.
[0050] As illustrated in
[0051] As described above, in the secure computation system 100 and the secure computation method according to the present example embodiment, a participant receives received values, which are received from at least three of the other participants and which are supposed to be the same value, and adopts the received values that are same at least two received values as an accurate value. In this way, even if one of the other participants is a dishonest person, the participants can determine an accurate value. That is, even if there is a dishonest person, it is possible to realize Guaranteed Output Delivery (GOD) that can acquire an accurate computation without stopping the processes. In addition, because no hash function is used in the above processes, Guaranteed Output Delivery (GOD) is realized in a normal model.
[0052] The first example embodiment described above is an example embodiment for describing only a basic concept of the present invention. A second example embodiment described below is a practical example embodiment to which the above-described concept is applied.
Second Example Embodiment
[0053] Hereinafter, a secure computation system and secure computation server apparatuses according to a second example embodiment will be described with reference to
[0054]
[0055] In the secure computation system 200 including the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), it is possible to compute target shares from a value inputted to any one of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) while keeping the input value and the values acquired in the computation processes secret, and it is possible to dispersedly store the computation results in the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4).
[0056] In addition, in the secure computation system 200 including the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), even when one of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) is operated by a dishonest person, it is possible to continue an accurate secure computation without stopping the processes.
[0057]
[0058] The local shuffle part 201_i computes, by using a shared permutation shared by four of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), permuted values of a share for a remaining one of the first to fifth secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4) and sends the permuted values of the share to the remaining secure computation server apparatus. The comparison and verification part 202_i compares the permuted values of the share with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be the same value, and adopts the values that are same at least two values as an accurate permutation. The shuffle synthesis part 203_i synthesizes, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses 200_i (i=0, 1, 2, 3, 4), mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts 202_i.
[0059] Hereinafter, building blocks used for execution of the bit conversion according to the present example embodiment will be described.
[Generation of Pseudo Random Numbers and Sharing of Seeds] A pseudo-random function F.sub.n, seeds, and an identifier have a relationship as follows. The pseudo-random function F.sub.n, is a binary operation defined with a security parameter x.
F.sub.n:{0,1}K.sup.k?{0,1}.sup.k.fwdarw.{0,1}.sup.n
Seeds seed.sub.i ?{0,1}.sup.k ((i=0, 1, 2, 3, 4) are values appropriately shared by the individual secure computation server apparatuses 200_i, and an identifier vid ?{0,1}.sup.k is a public value such as a counter. The pseudo-random function F.sub.n determinably generates pseudo random numbers by using the seeds and the identifier as its inputs.
[0060] Regarding the five seeds seed.sub.i ?{0,1}.sup.k ((i=0, 1, 2, 3, 4), an individual one of the secure computation server apparatuses 200_i holds (seed.sub.i, seed.sub.i+1, seed.sub.i+2, seed.sub.i+3). Note that seed.sub.4+1=seed.sub.0. That is, an individual one of the secure computation server apparatuses 200_i holds the seeds seed, other than the seed seed.sub.i+4. For example, the sharing of these seeds can be appropriately set by an administrator or the like as a presetting of the secure computation server apparatuses 200_i.
[0061] [Creation of Mask]
[0062] Next, a pseudo random number (Correlated Randomness) that is seen as a random number by the participant P.sub.i+4 and cannot be removed and that can be determinably computed by the other participants P.sub.i, P.sub.i+1, P.sub.i+2, and P.sub.i+3 is created, and this pseudo random number will be used as a mask when the permuted shares, which will be described below, are sent.
[0063] First, since the participant P.sub.i+4 does not hold the seed seed.sub.i+3, if the seed seed.sub.i+3 is used as an input of the pseudo-random function F.sub.n, the following pseudo random number satisfies the above condition. That is, although the following r.sub.k is seen as a random number by the participant P.sub.i+4 and cannot be removed, the following r.sub.k can be determinably computed by the other participants P.sub.i, P.sub.i+1, P.sub.i+2, and P.sub.i+3. r.sub.k=F.sub.n(vid.sub.k, seed.sub.i+3)?F.sub.n(vid.sub.k+1, seed.sub.i+3) mod n
[0064] In addition, by changing the index k in the identifier vid.sub.k from k=0 to k=4, five pseudo random numbers r.sub.k can be created. A set of these pseudo random numbers r.sub.k is defined as follows. Whether the following pseudo random numbers r.sub.0, r.sub.1, r.sub.2, r.sub.3, and r.sub.4 determined as follows satisfy r.sub.0+r.sub.1+r.sub.2+r.sub.3+r.sub.4=0 can be easily determined.
(r.sub.0,r.sub.1,r.sub.2,r.sub.3,r.sub.4)=CR(i+4,{vid.sub.k}.sup.4.sub.k=0,seed.sub.i+3)
[0065] Although the pseudo random numbers r.sub.0, r.sub.1, r.sub.2, r.sub.3, and r.sub.4 created as described above are seen as random numbers by the participant P.sub.i+4 and cannot be removed, these pseudo random numbers can be determinably computed by the other participants P.sub.i, P.sub.i+1, P.sub.i+2, and P.sub.i+3. However, although the pseudo random numbers r.sub.0, r.sub.1, r.sub.2, r.sub.3, and r.sub.4 cannot be removed by the participant P.sub.i+4, if all the pseudo random numbers r.sub.0, r.sub.1, r.sub.2, r.sub.3, and r.sub.4 are collected, because the sum is 0, the pseudo random numbers r.sub.0, r.sub.1, r.sub.2, r.sub.3, and r.sub.4 can be removed by the participant P.sub.i+4.
[0066] [Construction of Mini-Shuffles]
[0067] The construction of a mini-shuffle corresponds to the local shuffle step (S11) and the comparison and verification step (S12) described in the above first example embodiment.
[0068] The following description will be made on an example in which, among the participants P.sub.i (i=0, 1, 2, 3, 4), each of the participants P.sub.i (i=1, 2, 3, 4) computes a permutation of the participant P.sub.0 for the participant P.sub.0 by using a permutation shared thereby and sends the computed permutation to the participant P.sub.0.
[0069] A permutation ?.sub.0 ?S.sub.M shared by the participants P.sub.i (i=1, 2, 3, 4) is constructed as follows. As described above, the participants P.sub.i, (i=0, 1, 2, 3, 4) hold the seeds (seed.sub.i, seed.sub.i+1, seed.sub.i+2, seed.sub.i+3). In other words, each participant P.sub.i (i=0, 1, 2, 3, 4) does not hold the seed seed.sub.i+4. That is, while the participant P.sub.0 does not hold the seed seed.sub.4, the other participants P.sub.i (i=1, 2, 3, 4) hold the seed seed.sub.4 Thus, the permutation ?.sub.0 ?S.sub.M shared by the participants P.sub.i (i=1, 2, 3, 4) is constituted by using a pseudo random number generated by using the seed seed.sub.4. In this way, although the permutation ?.sub.0 ?S.sub.M is traceable by the participants P.sub.i (i=1, 2, 3, 4), the permutation (To ?S.sub.M is not traceable by the participant P.sub.0.
[0070] Next, by using the permutation ?.sub.0 ?S.sub.M constructed as described above and the pseudo random number r.sub.k, each of the participants P.sub.i (i=1, 2, 3, 4) computes the permutation of the participant P.sub.0 for the participant P.sub.0 and sends the computed permutation to the participant P.sub.0 as follows. It should be noted here that, from the method of constructing the shares in secret sharing, there are shares shared by the participants P.sub.i (i=1, 2, 3, 4) and the participant P.sub.0 and that the participants P.sub.i (i=1, 2, 3, 4) can compute the permutation of the participant P.sub.0 for the participant P.sub.0.
{P.sub.2,P.sub.3,P.sub.4}: {right arrow over (r.sub.0)}+?.sub.0({right arrow over (x.sub.0)})[Equations 3]
{P.sub.1,P.sub.3,P.sub.4}: {right arrow over (r.sub.1)}+?.sub.0({right arrow over (x.sub.1)})
{P.sub.1,P.sub.2,P.sub.4}: {right arrow over (r.sub.2)}+?.sub.0({right arrow over (x.sub.2)})
{P.sub.1,P.sub.2,P.sub.3}:{right arrow over (r.sub.3)}+?.sub.0({right arrow over (x.sub.3)})
x.sub.i=(x.sub.0,i, . . . ,x.sub.M?1,i)(i=0,1,2,3)
x.sub.j=x.sub.j,0+x.sub.j,1+x.sub.j,2+x.sub.j,3+x.sub.j,4 mod L
r.sub.i=(r.sub.i,0, . . . ,r.sub.i,j, . . . ,r.sub.i,m?1)
r.sub.0,j+r.sub.1,j+r.sub.2,j+r.sub.3,j+r.sub.4,j=0 mod L(j=0, . . . ,m?1)
[0071] In the above transmission, note that the participants P.sub.2, P.sub.3, P.sub.4 send the same value to the participant P.sub.0, the participants P.sub.1, P.sub.3, P.sub.4 send the same value to the participant P.sub.0, the participants P.sub.1, P.sub.2, P.sub.4 send the same value to the participant P.sub.0, the participants P.sub.1, P.sub.2, P.sub.3 send the same value to the participant P.sub.0. From this nature, the participant P.sub.0 can compare the values of the permuted shares, which are received from three participants and which are supposed to be the same value, and can adopt the received values that are same at least two received values as an accurate permutation. That is, even if one of the other participants is a dishonest person, the participants can determine an accurate value. That is, even if there is a dishonest person, it is possible to realize Guaranteed Output Delivery (GOD) that can acquire an accurate computation without stopping the processes.
[0072] In addition, in the above transmission, by using a hash function shared by the participants P.sub.i (i=1, 2, 3, 4) and transmitting the hash value as follows, the communication amount can be reduced. First, one of the three participants converts a value by using the hash function and sends the obtained hash value to the participant P.sub.0. The other two participants send the value, not a hash value, to the participant P.sub.0 without change. Upon receiving the value, the participant P.sub.0 converts the value into a hash value by using the hash function. Next, the participant P.sub.0 compares the hash values with each other. If at least two of the hash values are the same value, the participant P.sub.0 adopts this value as an accurate value.
[0073] By performing the process as described above, a share corresponding to the permutation ?.sub.0 ?S.sub.M that can be computed by the participants P.sub.i (i=1, 2, 3, 4) and that cannot be computed by the participant P.sub.0 can be constituted as follows.
P.sub.i:[?.sub.0({right arrow over (x)})].sub.1,i=({right arrow over (r.sub.1)}+?.sub.0({right arrow over (x.sub.1)}),{right arrow over (r.sub.i+1)}+?.sub.0({right arrow over (x.sub.i+1)}),{right arrow over (r.sub.i+2)}+?.sub.0({right arrow over (x.sub.i+2)}),{right arrow over (r.sub.i+3)}?.sub.0({right arrow over (x.sub.i+3)}))
{right arrow over (x.sub.i)}=(x.sub.0,i, . . . ,x.sub.M?1,i)(i=0,1,2,3)
x.sub.j=x.sub.j,0+x.sub.j,1+x.sub.j,2+x.sub.j,3+x.sub.j,4 mod L
r.sub.1=(r.sub.i,0, . . . ,r.sub.i,j, . . . ,r.sub.i,m?1)
r.sub.0,j+r.sub.1,j+r.sub.2,j+r.sub.3,j+r.sub.4,j=0 mod L(j=0, . . . ,m?1)[Equations 4]
[0074] [Synthesis of Mini-Shuffles]
[0075] In the above construction of mini-shuffles, of all the participants P.sub.i (i=0, 1, 2, 3, 4), each of the participants P.sub.i (i=1, 2, 3, 4) computes the permutation of the participant P.sub.0 for the participant P.sub.0 by using a permutation shared by the participants P.sub.i (i=1, 2, 3, 4) and sends the computed permutation to the participant P.sub.0. However, alternatively, a combination of four participants P.sub.i and one participant P.sub.0 may be changed. In this way, five mini-shuffles can be constructed. Each of these five mini-shuffles represents a permutation that is not traceable by one of the participants P.sub.i, (i=0, 1, 2, 3, 4).
[0076] Thus, by synthesizing all the permutations ?.sub.i (i=0, 1, 2, 3, 4)?S.sub.M, each of which is not traceable by one of the participants P.sub.i, (i=0, 1, 2, 3, 4), a permutation ? (shuffle) that is not traceable by any one of the participants P.sub.i (i=0, 1, 2, 3, 4) can be constructed.
?=?.sub.0??.sub.1??.sub.2? ?.sub.3??.sub.4[Equation 5]
[0077] Regarding the communication cost of the shuffle constructed as described above, the number of communication rounds is 5, and the communication amount is 40 nm bits. Regarding a single mini-shuffle, the number of communication rounds is 1, and the communication amount is 8 nm bits. Because five mini-shuffles are performed, the above communication cost is achieved.
Hardware Configuration Example
[0078]
[0079] The hardware configuration example illustrated in
[0080] As illustrated in
[0081] The CPU 11 executes various commands included in the secure computation program executed by the corresponding one of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4). The main storage device 12 is, for example, a RAM (Random Access Memory) and temporarily stores various kinds of programs such as the secure computation program executed by the corresponding one of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) so that the CPU 11 can execute the programs.
[0082] The auxiliary storage device 13 is, for example, an HDD (Hard Disk Drive) and can store, in the mid-to-long term, various kinds of programs such as the secure computation program executed by the corresponding one of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4). These various kinds of programs such as the secure computation program can be recorded in a non-transitory computer-readable storage medium and can be provided as a program product. The auxiliary storage device 13 can be used to store, in the mid-to-long term, various kinds of programs such as the secure computation program recorded in a non-transitory computer-readable storage medium. The IF part 14 provides an interface regarding the input and output among the corresponding secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4).
[0083] An information processing apparatus that adopts the hardware configuration 10 as described above realizes the functions of any one of the secure computation server apparatuses 100_i and 200_i (i=0, 1, 2, 3, 4) by executing the corresponding one of the above-described secure computation methods as a program.
[0084] The above example embodiments can partially or entirely be described, but not limited to, as the following notes.
[Note 1]
[0085] A secure computation system, which includes five secure computation server apparatuses connected to each other via a network, an individual one of the secure computation server apparatuses including: [0086] a local shuffle part that computes, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses and sends the permuted values of the share to the remaining secure computation server apparatus; [0087] a comparison and verification part that compares values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value, and adopts the values that are same at least two values as an accurate permutation; and [0088] a shuffle synthesis part that synthesizes, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts.
[Note 2]
[0089] The secure computation system according to note 1; wherein the mini-shuffles are each determinably generated by using seeds held by the four secure computation server apparatuses and an identifier held by the five secure computation server apparatuses as input and are each masked by pseudo random numbers whose total is zero regarding the five secure computation server apparatuses.
[Note 3]
[0090] The secure computation system according to note 1 or 2; wherein the shared permutation is determinably generated by using a seed shared by the four secure computation server apparatuses as input.
[Note 4]
[0091] The secure computation system according to any one of notes 1 to 3; wherein the comparison and verification part determines that the received values are each an accurate value by determining that hash values of the received values are same.
[Note 5]
[0092] A secure computation server apparatus, which is one of five secure computation server apparatuses connected to each other via a network, the secure computation server apparatus including: [0093] a local shuffle part that computes, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses and sends the permuted values of the share to the remaining secure computation server apparatus; [0094] a comparison and verification part that compares values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value, and adopts the values that are same at least two values as an accurate permutation; and [0095] a shuffle synthesis part that synthesizes, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a permutation adopted by a corresponding one of the comparison and verification parts.
[Note 6]
[0096] A secure computation method, which uses five secure computation server apparatuses connected to each other via a network, the secure computation method including: [0097] causing an individual one of the secure computation server apparatuses to compute, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses; [0098] causing the individual one of the secure computation server apparatuses to send the permuted values of the share to the remaining secure computation server apparatus; [0099] causing the individual one of the secure computation server apparatuses to compare values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value; [0100] causing the individual one of the secure computation server apparatuses to adopt the values that are same at least two values as an accurate permutation; and [0101] causing the individual one of the secure computation server apparatuses to synthesize, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a corresponding permutation adopted.
[Note 7]
[0102] The secure computation method according to note 6; wherein the mini-shuffles are each determinably generated by using seeds held by the four secure computation server apparatuses and an identifier held by the five secure computation server apparatuses as input and are each masked by pseudo random numbers whose total is zero regarding the five secure computation server apparatuses.
[Note 8]
[0103] The secure computation method according to note 6 or 7; wherein the shared permutation is determinably generated by using a seed shared by the four secure computation server apparatuses as input.
[Note 9]
[0104] The secure computation method according to any one of notes 6 to 8; wherein it is determined that the permuted values of the share are each an accurate value by determining that hash values of the received values are same.
[Note 10]
[0105] A secure computation program, causing at least five secure computation server apparatuses connected to each other via a network to perform a secure computation, the program including: [0106] computing, by using a shared permutation shared by four of the five secure computation server apparatuses, permuted values of a share for a remaining one of the five secure computation server apparatuses; [0107] sending the permuted values of the share to the remaining secure computation server apparatus; [0108] comparing values with each other, which are received from at least three of the four secure computation server apparatuses and which are supposed to be a same value; [0109] adopting the values that are same at least two values as an accurate permutation; and [0110] synthesizing, regarding five combinations of four secure computation server apparatuses selected from the five secure computation server apparatuses, mini-shuffles, each of which is constructed by using a shared permutation shared by a corresponding combination of four secure computation server apparatuses and a corresponding permutation adopted.
[0111] The disclosure of the above NPL is incorporated herein by reference thereto. Modifications and adjustments of the example embodiments or examples are possible within the scope of the overall disclosure (including the claims) of the present invention and based on the basic technical concept of the present invention. Various combinations or selections (including partial deletion) of various disclosed elements (including the elements in each of the claims, example embodiments, examples, drawings, etc.) are possible within the scope of the disclosure of the present invention. That is, the present invention of course includes various variations and modifications that could be made by those skilled in the art according to the overall disclosure including the claims and the technical concept. The description discloses numerical value ranges. However, even if the description does not particularly disclose arbitrary numerical values or small ranges included in the ranges, these values and ranges should be deemed to have been specifically disclosed. In addition, as needed and based on the gist of the present invention, partial or entire use of the individual disclosed matters in the above literatures that have been referred to in combination with what is disclosed in the present application should be deemed to be included in what is disclosed in the present application, as a part of the disclosure of the present invention.
REFERENCE SIGNS LIST
[0112] 100, 200 secure computation system [0113] 100_i, 200_i secure computation server apparatus [0114] 101_i, 201_i local shuffle part [0115] 102_i, 202_i comparison and verification part [0116] 103_i, 203_i shuffle synthesis part [0117] 10 hardware configuration [0118] 11 CPU (Central Processing Unit) [0119] 12 main storage device [0120] 13 auxiliary storage device [0121] 14 IF (Interface) part