Secret computation apparatus, method for the same, and program

Abstract

An assigned share which is a proper subset of a subshare set with a plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values are stored. When a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, a provided value according to the provided corresponding value obtained from the subset of the assigned share is outputted. When a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, input of an acquired value according to the acquired corresponding value is accepted. When the acquired value is inputted, a secret share value is obtained at least using the acquired value.

Claims

1. A secret computation apparatus that obtains a secret share value of an operation result according to an input value, wherein the input value is a function value of a plurality of subshares; and the secret computation apparatus comprises: a storage that stores an assigned share which is a proper subset of a sub share set with the plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values; and processing circuitry configured to implement: an output part that, when a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, transmits a provided value according to the provided corresponding value obtained from the subset of the assigned share; an input part to which, when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value is inputted; and an operation part that, when the acquired value is inputted to the input part, obtains the secret share value at least using the acquired value, wherein the operation result is a multiplication result between the input value a and a second input value b; the input value a satisfies a=a.sub.0P+a.sub.1P+a.sub.2P for the subshares a.sub.0P, a.sub.1P, a.sub.2P; the second input value b satisfies b=b.sub.0P+b.sub.1P+b.sub.2P for second subshares b.sub.0P, b.sub.1P, b.sub.2P; a.sub.0P, b.sub.0P and b.sub.1P are values according to a.sub.0P, a.sub.1P, b.sub.0P and b.sub.1P, respectively; the storage stores the assigned share (a.sub.0P, a.sub.1P) which is a proper subset of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P), the meta information A indicating values according to the elements of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P, b.sub.1P, b.sub.2P), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P, b.sub.1P, b.sub.2P) or indicating that the elements are concealed values; the secret computation apparatus comprises processing circuitry configured to implement: a first sharing part that, when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, performs communication for sharing a first arbitrary value r.sub.P with an external first secret computation apparatus; and a second sharing part that, when a value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, performs communication for sharing a second arbitrary value r.sub.P with an external second secret computation apparatus; when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, the output part transmits the provided value c.sub.P:=a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P+r.sub.P to the second secret computation apparatus; when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, the input part receives the acquired value c.sub.P+ transmitted from the first secret computation apparatus; and the operation part comprises: a first processing part that sets c.sub.P:=c.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set; a second processing part that sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set; a third processing part that sets r.sub.P:=r.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fourth processing part that sets r.sub.P:=r.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, and sets e.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fifth processing part that obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B and/or obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when a value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B; and a sixth processing part that obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when the value according to a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B and/or obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.+r.sub.P when a value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B.

2. The secret computation apparatus according to claim 1, wherein the operation part comprises: a seventh processing part that, when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, sets C.sub.0P:= and, when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is obtained from the meta information A and B, obtains the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P from the meta information A and B and sets the value as C.sub.0P; an eighth processing part that, when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, sets C.sub.1P:= and, when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is obtained from the meta information A and B, obtains the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P from the meta information A and B and sets the value as C.sub.1P; and a ninth processing part that, when a value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, sets C.sub.2P:= and, when the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is obtained from the meta information A and B, obtains the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P from the meta information A and B and sets the value as C.sub.2P; and C.sub.0P, C.sub.1P, C.sub.2P are meta information about the secret share value; the secret share value includes c.sub.0P in the case of C.sub.0P:=; and the secret share value includes c.sub.1P in the case of C.sub.1P:=.

3. A secret computation apparatus that obtains a secret share value of an operation result according to an input value, wherein the input value is a function value of a plurality of subshares; and the secret computation apparatus comprises: a storage that stores an assigned share which is a proper subset of a sub share set with the plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values; and processing circuitry configured to implement: an output part that, when a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, transmits a provided value according to the provided corresponding value obtained from the subset of the assigned share; an input part to which, when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value is inputted; and an operation part that, when the acquired value is inputted to the input part, obtains the secret share value at least using the acquired value, wherein the operation result is an operation result .sub.n{0, . . . , N-1}a(n)b(n) between the input value {a(0), . . . , a(N1)} and a second input value {b(0), . . . , b(N1)}, and N1 and n=0, . . . , N1 are satisfied; a(n) satisfies a(n)=a.sub.0P(n)+a.sub.1P(n)+a.sub.2P(n) for the subshares a.sub.0P(n), a.sub.1P(n), a.sub.2P(n); b(n) satisfies b(n)=b.sub.0P(n)+b.sub.1P(n)+b.sub.2P(n) for second subshares b.sub.0P(n), b.sub.1P(n), b.sub.2P(n); a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n) are values according to a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n), respectively; the storage stores the assigned share (a.sub.0P(n), a.sub.1P(n)) which is a proper subset of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)), the meta information. A indicating values according to elements of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)) or indicating that the elements are concealed values; the secret computation apparatus comprises processing circuitry configured to implement: a first sharing part that, when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, performs communication for sharing a first arbitrary value r.sub.P with an external first secret computation apparatus; and a second sharing part that, when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, performs communication for sharing a second arbitrary value r.sub.P with an external second secret computation apparatus; when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, the output part transmit the provided value c.sub.P:=.sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)}+r.sub.P to the second secret computation apparatus; when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, the input part receives the acquired value c.sub.P+ transmitted from the first secret computation apparatus; and the operation part comprises: a first processing part that sets c.sub.P:=c.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set; a second processing part that sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set; a third processing part that sets r.sub.P:=r.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fourth processing part that sets r.sub.P:=r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fifth processing part that obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B and/or obtains C.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B; and a sixth processing part that obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B and/or obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.Pr.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B.

4. The secret computation apparatus according to claim 3, wherein the operation part comprises: a seventh processing part that sets C.sub.0P:= when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and, when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is obtained from the meta information A and B, obtains the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} from the meta information A and B and sets the value as C.sub.0P; an eighth processing part that sets C.sub.1P:= when the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, and, when the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is obtained from the meta information A and B, obtains the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} from the meta information A and B and sets the value as C.sub.1P; a ninth processing part that sets C.sub.2P:= when a value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, and, when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is obtained, obtains the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} from the meta information A and B and sets the value as C.sub.2P; and C.sub.0P, C.sub.1P, C.sub.2P are meta information about the secret share value; the secret share value includes c.sub.0P in the case of C.sub.0P:=; and the secret share value includes c.sub.1P in the case of C.sub.1P:=.

5. The secret computation apparatus according to any one of claims 1 to and 2, wherein the operation result is a value according to the input value and a second input value; the second input value is a function value of a plurality of second subshares; the storage stores a second assigned share which is a proper subset of a second subshare set with the plurality of second subshares as elements, and second meta information indicating values according to the elements of the second subshare set or indicating that the elements are concealed values; when the value according to the provided corresponding value according to the subset of the assigned share and a subset of the second assigned share is not obtained from the meta information and the second meta information, the output part transmits the provided value according to the provided corresponding value obtained from the subset of the assigned share and the subset of the second assigned share; and when the value according to the acquired corresponding value according to the subset of the external assigned share, which is a proper subset of the subshare set, and a subset of a second external assigned share, which is a proper subset of the second subshare set, is not obtained, from the meta information and the second meta information, the acquired value according to the acquired corresponding value is inputted to the input part.

6. A secret computation apparatus that obtains a secret share value of an operation result according to an input value, wherein the input value is a function value of a plurality of subshares; and the secret computation apparatus comprises: a storage that stores an assigned share which is a proper subset of a subshare set with the plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values; and processing circuitry configured to implement: an output part that, when a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, transmits a provided value according to the provided corresponding value obtained from the subset of the assigned share; an input part to which, when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value is inputted; and an operation part that, when the acquired value is inputted to the input part, obtains the secret share value at least using the acquired value, wherein the operation result is a value according to the input value and a second input value; the second input value is a function value of a plurality of second subshares; the storage stores a second assigned share which is a proper subset of a second subshare set with the plurality of second subshares as elements, and second meta information indicating values according to the elements of the second subshare set or indicating that the elements are concealed values; when the value according to the provided corresponding value according to the subset of the assigned share and a subset of the second assigned share is not obtained from the meta information and the second meta information, the output part outputs the provided value according to the provided corresponding value obtained from the subset of the assigned share and the subset of the second assigned share; and when the value according to the acquired corresponding value according to the subset of the external assigned share, which is a proper subset of the subshare set, and a subset of a second external assigned share, which is a proper subset of the second subshare set, is not obtained, from the meta information and the second meta information, the acquired value according to the acquired corresponding value is inputted to the input part, wherein the operation result is a multiplication result between the input value a and a second input value b; the input value a satisfies a=a.sub.0P+a.sub.1P+a.sub.2P for the subshares a.sub.0P, a.sub.1P, a.sub.2P; the second input value b satisfies b=b.sub.0P+b.sub.1P+b.sub.2P for the second subshares b.sub.0P, b.sub.1P, b.sub.2P; a.sub.0P, a.sub.1P, b.sub.0 and b.sub.1P are values according to a.sub.0P, a.sub.1P, b.sub.0P and b.sub.1P, respectively; the storage stores the assigned share (a.sub.0P, a.sub.1P) which is a proper subset of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P), the meta information A indicating values according to elements of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P) or indicating that the elements are concealed values, the second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of the second subshare set (b.sub.0P, b.sub.1P, b.sub.2P), and the second meta information B indicating values according to elements of the second subshare set (b.sub.0P, b.sub.1P, b.sub.2P) or indicating that the elements are concealed values; the secret computation apparatus comprises processing circuitry configured to implement: a first sharing part that, when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, performs communication for sharing a first arbitrary value r.sub.P with an external first secret computation apparatus; and a second sharing part that, when a value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, performs communication for sharing a second arbitrary value r.sub.P with an external second secret computation apparatus; when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, the output part transmits the provided value c.sub.P:=a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P+r.sub.P to the second secret computation apparatus; when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, the input part receives the acquired value c.sub.P+ transmitted from the first secret computation apparatus; and the operation part comprises: a first processing part that sets c.sub.P:=c.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set; a second processing part that sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set; a third processing part that sets r.sub.P:=r.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fourth processing part that sets r.sub.P:=r.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fifth processing part that obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B and/or obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when a value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B; and a sixth processing part that obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when the value according to a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B and/or obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when a value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B.

7. The secret computation apparatus according to claim 6, wherein the operation part comprises: a seventh processing part that, when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, sets C.sub.0P:= and, when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is obtained from the meta information A and B, obtains the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0 from the meta information A and B and sets the value as C.sub.0P; an eighth processing part that, when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, sets C.sub.1P:= and, when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is obtained from the meta information A and B, obtains the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P from the meta information A and B and sets the value as C.sub.1P; and a ninth processing part that, when a value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, sets C.sub.2P:= and, when the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is obtained from the meta information A and B, obtains the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P from the meta information A and B and sets the value as C.sub.2P; and C.sub.0P, C.sub.1P, C.sub.2P are meta information about the secret share value; the secret share value includes c.sub.0P in the case of C.sub.0P:=; and the secret share value includes c.sub.1P in the case of C.sub.1P:=.

8. A secret computation apparatus that obtains a secret share value of an operation result according to an input value, wherein the input value is a function value of a plurality of subshares; and the secret computation apparatus comprises: a storage that stores an assigned share which is a proper subset of a subshare set with the plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values; and processing circuitry configured to implement: an output part that, when a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, transmits a provided value according to the provided corresponding value obtained from the subset of the assigned share; an input part to which, when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value is inputted; and an operation part that, when the acquired value is inputted to the input part, obtains the secret share value at least using the acquired value, wherein the operation result is an operation result .sub.n{0, . . . , N-1}a(n)b(n) between the input value {a(0), . . . , a(N1)} and a second input value {b(0), . . . , b(N1)}, and N1 and n=0, . . . , N1 are satisfied; a(n) satisfies a(n)=a.sub.0P(n)+a.sub.1P(n)+a.sub.2P(n) for the subshares a.sub.0P(n), a.sub.1P(n), a.sub.2P(n); b(n) satisfies b(n)=b.sub.0P(n)+b.sub.1P(n)+b.sub.2P(n) for second subshares b.sub.0P(n), b.sub.1P(n), b.sub.2P(n); a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n) are values according to a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n), respectively; the storage stores the assigned share (a.sub.0P(n), a.sub.1P(n)) which is a proper subset of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)), the meta information A indicating values according to elements of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)) or indicating that the elements are concealed values; the secret computation apparatus comprises processing circuitry configured to implement: a first sharing part that, when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, performs communication for sharing a first arbitrary value r.sub.P with an external first secret computation apparatus; and a second sharing part that, when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, performs communication for sharing a second arbitrary value r.sub.P with an external second secret computation apparatus; when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, the output part transmits the provided value c.sub.P:=.sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)}+r.sub.P to the second secret computation apparatus; when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, the input part receives the acquired value c.sub.P+ transmitted from the first secret computation apparatus; and the operation part comprises: a first processing part that sets c.sub.P:=C.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set; a second processing part that sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set; a third processing part that sets r.sub.P:=r.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fourth processing part that sets r.sub.P:=r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fifth processing part that obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P((n)b.sub.1P(n)+c.sub.Pr.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B and/or obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B; and a sixth processing part that obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B and/or obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B.

9. The secret computation apparatus according to claim 8, wherein the operation part comprises: a seventh processing part that sets C.sub.0P:= when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and, when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is obtained from the meta information A and B, obtains the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} from the meta information A and B and sets the value as C.sub.0P; an eighth processing part that sets C.sub.1P:= when the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2(n)b.sub.1P(n)} is not obtained from the meta information A and B, and, when the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.0P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2(n)b.sub.1P(n)} is obtained from the meta information A and B, obtains the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} from the meta information A and B and sets the value as C.sub.1P; a ninth processing part that sets C.sub.2P:= when a value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, and, when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is obtained, obtains the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2(n)+a.sub.2(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} from the meta information A and B and sets the value as C.sub.2P; and C.sub.0P, C.sub.1P, C.sub.2P are meta information about the secret share value; the secret share value includes c.sub.0P in the case of C.sub.0P:=; and the secret share value includes c.sub.1P in the case of C.sub.1P:=.

10. A non-transitory computer-readable recording medium storing a program for causing a computer to function as the secret computation apparatus according to any one of claims 1 to 4.

11. A secret computation method for obtaining a secret share value of an operation result according to an input value, wherein the input value is a function value of a plurality of subshares; an assigned share which is a proper subset of a subshare set with the plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values are stored in a storage; and the method comprises the steps of: when a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, an output part transmitting a provided value according to the provided corresponding value obtained from the subset of the assigned share; when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value being inputted to an input part; and an operation part obtaining the secret share value at least using the acquired value when the acquired value is inputted to the input part, wherein the operation result is a multiplication result between the input value a and the second input value b; the input value a satisfies a=a.sub.0P+a.sub.1P+a.sub.2P for the subshares a.sub.0P, a.sub.1P, a.sub.2P; the second input value b satisfies b=b.sub.0P+b.sub.1P+b.sub.2P for second subshares b.sub.0P, b.sub.1P, b.sub.2P; a.sub.0P, a.sub.1P, b.sub.0P and b.sub.1P are values according to a.sub.0P, a.sub.1P, b.sub.0P and b.sub.1P, respectively; the storage (111-P) stores the assigned share (a.sub.0P, a.sub.1P) which is a proper subset of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P), the meta information A indicating values according to elements of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P, b.sub.1P, b.sub.2P), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P, b.sub.1P, b.sub.2P) or indicating that the elements are concealed values; a secret computation apparatus (11-P) comprises: a first sharing part (114-P) that, when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, performs communication for sharing a first arbitrary value r.sub.P with an external first secret computation apparatus (11-P.sub.+); and a second sharing part (114-P) that, when a value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, performs communication for sharing a second arbitrary value r.sub.P with an external second secret computation apparatus (11-P.sub.); when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, the output part (115-P) transmits the provided value c.sub.P:=a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P+r.sub.P to the second secret computation apparatus (11-P.sub.); when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, the acquired value c.sub.P+ transmitted from the first secret computation apparatus (11-P.sub.|) is inputted to the input part (115-P); and the operation part (112-P) comprises: a first processing part (1121-P) that sets c.sub.P:=c.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set; a second processing part (1122-P) that sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set; a third processing part (1123-P) that sets r.sub.P:=r.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fourth processing part (1124-P) that sets r.sub.P:=r.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fifth processing part (1125-P) that obtains C.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B and/or obtains c.sub.0P: =a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when a value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B; and a sixth processing part (1126-P) that obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when the value according to a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B and/or obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when a value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B.

12. A secret computation method for obtaining a secret share value of an operation result according to an input value, wherein the input value is a function value of a plurality of subshares; an assigned share which is a proper subset of a subshare set with the plurality of subshares as elements, and meta information indicating values according to the elements of the subshare set or indicating that the elements are concealed values are stored in a storage; and the method comprises the steps of: when a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, an output part transmitting a provided value according to the provided corresponding value obtained from the subset of the assigned share; when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value being inputted to an input part; and an operation part obtaining the secret share value at least using the acquired value when the acquired value is inputted to the input part, wherein the operation result is an operation result .sub.n{0, . . . , N-1}a(n)b(n) between the input value {a(0), . . . , a(N1)} and a second input value {b(0), . . . , b(N1)}, and N1 and n=0, . . . , N1 are satisfied; a(n) satisfies a(n)=a.sub.0P(n)+a.sub.1P(n)+a.sub.2P(n) for the subshares a.sub.0P(n), a.sub.1P(n), a.sub.2P(n); b(n) satisfies b(n)=b.sub.0P(n)+b.sub.1P(n)+b.sub.2P(n) for second subshares b.sub.0P(n), b.sub.1P(n), b.sub.2P(n); a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n) are values according to a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n), respectively; the storage (211-P) stores the assigned share (a.sub.0P(n), a.sub.1P(n)) which is a proper subset of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)), the meta information A indicating values according to elements of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)) or indicating that the elements are concealed values; a secret computation apparatus (21-P) comprises: a first sharing part (214-P) that, when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, performs communication for sharing a first arbitrary value r.sub.P with an external first secret computation apparatus (21-P.sub.+); and a second sharing part (214-P) that, when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, performs communication for sharing a second arbitrary value r.sub.P with an external second secret computation apparatus (21-P.sub.); when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.P)+(n)+a.sub.P(n)b.sub.0P(n)} is not obtained from the meta information A and B, the output part (215-P) transmits the provided value c.sub.P:=.sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)}+r.sub.P to the second secret computation apparatus (21-P.sub.); when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, the acquired value c.sub.P+ transmitted from the first secret computation apparatus (21-P.sub.+) is inputted to the input part (215-P); and the operation part (212-P) comprises: a first processing part (2121-P) that sets c.sub.P:=c.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set; a second processing part (2122-P) that sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set; a third processing part (2123-P) that sets r.sub.P:=r.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fourth processing part (2124-P) that sets r.sub.P:=r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set; a fifth processing part (2125-P) that obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B and/or obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B; and a sixth processing part (2126-P) that obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B and/or obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P|r.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram illustrating a functional configuration of a secret computation system of an embodiment;

(2) FIG. 2 is a block diagram illustrating a functional configuration of a secret computation apparatus of the embodiment;

(3) FIG. 3 is a conceptual diagram for illustrating a secret computation method of the embodiment;

(4) FIG. 4 is a flowchart for illustrating the secret computation method of the embodiment;

(5) FIG. 5 is the flowchart for illustrating the secret computation method of the embodiment;

(6) FIG. 6 is the flowchart for illustrating the secret computation method of the embodiment;

(7) FIG. 7 is the flowchart for illustrating the secret computation method of the embodiment;

(8) FIG. 8 is a conceptual diagram for illustrating a secret computation method of an embodiment;

(9) FIG. 9 is a flowchart for illustrating the secret computation method of the embodiment;

(10) FIG. 10 is the flowchart for illustrating the secret computation method of the embodiment;

(11) FIG. 11 is the flowchart for illustrating the secret computation method of the embodiment; and

(12) FIG. 12 is the flowchart for illustrating the secret computation method of the embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(13) Embodiments of the present invention will be described below.

(14) [Summary]

(15) In secret computation of the embodiments, each of a plurality of secret computation apparatuses obtains a secret share value of an operation result according to an input value. Here, the input value is secretly shared in accordance with a replicated secret sharing scheme. That is, the input value is a function value of a plurality of subshares (for example, an addition value, an addition/subtraction value or the like), and a proper subset of a subshare set with the plurality of the subshares as elements is assigned to each secret sharing apparatus as a share (a secret share value of the input value). However, there may be a case where values according to a part of the subshares are already known to each secret sharing apparatus. For example, a case where the value according to the part of subshares have been already acquired by secret computation performed in the past, a case where the values according to the part of the subshares are public information, and the like correspond to that case. A value according to may be itself or may be a function value of . The value according to is, for example, a value corresponding to . The operation result according to an input value may be the input value itself or may be a function value of the input value. According to such a situation, meta information indicating values according to elements of the subshare set or indicating that the elements are concealed values is set. Elements for which the values according to the elements are represented by the meta information can be identified from the meta information. Elements for which it is indicated by the meta information that the elements are concealed values cannot be identified from the meta information. In each secret computation apparatus, an assigned share and the meta information are stored. When a value according to a provided corresponding value according to a subset of the assigned share is not obtained from the meta information, the secret computation apparatus outputs a provided value according to the provided corresponding value obtained from the subset of the assigned share to the other secret computation apparatuses. The provided corresponding value according to the subset may be the subset itself or may be a function value of the subset. The provided value according to the provided corresponding value may be the provided corresponding value themselves or may be a function value of the provided corresponding value. On the other hand, when the value according to the provided corresponding value is obtained from the meta information, the secret computation apparatus does not have to output the provided value to the other secret computation apparatuses. Further, when a value according to an acquired corresponding value according to a subset of an external assigned share, which is a proper subset of the subshare set, is not obtained from the meta information, an acquired value according to the acquired corresponding value is inputted to the secret computation apparatus. The external assigned share means a share assigned to another secret computation apparatus. The acquired corresponding value according to the subset may be the subset itself or may be a function value of the subset. The acquired value according to the acquired corresponding value may be the acquired corresponding value itself or may be a function value of the acquired corresponding value. On the other hand, when the value according to the acquired corresponding value is obtained from the meta information, the acquired value does not have to be inputted to the secret computation apparatus. When the acquired value is inputted, the secret computation apparatus obtains the secret share value as the operation result according to the input value using at least the acquired value. Thereby, it is possible to reduce the number of times of transferring values among the secret computation apparatuses and improve efficiency.

(16) For example, in the case of obtaining secret share values of an operation result according to the input value and a second input value, a process as shown below is performed. In this case, the second input value is also secretly shared in accordance with the replicated secret sharing scheme similarly to the input value. That is, the second input value is a function value of a plurality of second subshares, and a proper subset of a second subshare set with the plurality of second subshares as elements is assigned to each secret sharing apparatus as a second share (a secret share value of the second input value). However, there may be a case where values according to a part of the second subshares are already known to each secret sharing apparatus. According to such a situation, second meta information indicating values according to elements of the second subshare set or indicating that the elements are concealed values is set. Elements for which the values according to the elements are represented by the second meta information can be identified from the second meta information. Elements for which it is indicated by the second meta information that the elements are concealed values cannot be identified from the second meta information. In each secret computation apparatus, a second assigned share and the second meta information are stored. When a value according to a provided corresponding value according to the subset of the assigned share and a subset of the second assigned share is not obtained from the meta information and the second meta information, the secret computation apparatus outputs a provided value according to the provided corresponding value obtained from the subset of the assigned share and the subset of the second assigned share to the other secret computation apparatuses. When a value according to all acquired corresponding value according to the subset of the external assigned share which is a proper subset of the subshare set and a subset of a second external assigned share which is a proper subset of the second subshare set is not obtained from the meta information and the second meta information, an acquired value according to the acquired corresponding value is inputted to the secret computation apparatus. Further, when the acquired value is inputted, the secret computation apparatus obtains the secret share values of the operation result according to the input value and the second input value using at least the acquired value.

(17) When the scheme described above is applied to multiplication, an operation result is a multiplication result ab between an input value a and a second input value b, and three secret computation apparatuses perform secret computation of the multiplication ab. The input value a satisfies a=a.sub.0P+a.sub.1P+a.sub.2P for subshares a.sub.0P, a.sub.1P, a.sub.2P, and the second input value b satisfies b=b.sub.0P+b.sub.1P+b.sub.2P for second subshares b.sub.0P, b.sub.1P, b.sub.2P. The secret computation apparatus stores an assigned share (a.sub.0P, a.sub.1P) which is a proper subset of a subshare set (a.sub.0P, a.sub.1P, a.sub.2P), meta information A indicating values according to elements of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P, b.sub.1P, b.sub.2P), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P, b.sub.1P, b.sub.2P) or indicating that the elements are concealed values. When a value according to a provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the information A and B, the secret computation apparatus performs communication for sharing a first arbitrary value r.sub.P with an external secret computation apparatus (a first secret computation apparatus). Otherwise, the communication for sharing the first arbitrary value r.sub.P is unnecessary. When a value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the information A and B, the secret computation apparatus performs communication for sharing a second arbitrary value r.sub.P with an external secret computation apparatus (a second secret computation apparatus). Otherwise, the communication for sharing the second arbitrary value r.sub.P is unnecessary. The lower subscript P corresponds to the present secret computation apparatus; the lower subscript P+ corresponds to the first secret computation apparatus; and the lower subscript P corresponds to the second secret computation apparatus. When the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, the secret computation apparatus outputs a provided value c.sub.P:=a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P+r.sub.P. When a value according to an acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, the secret computation apparatus accepts input of an acquired value c.sub.P+. Here, c.sub.P+:=a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P+r.sub.P+ is satisfied. Otherwise, the above communications are unnecessary. Here, := means to define that is (that is, to set the value of to ). The secret computation apparatus sets c.sub.P:=c.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set. The secret computation apparatus sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set. Further, the secret computation apparatus sets r.sub.P:=r.sub.P when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set. The secret computation apparatus sets r.sub.P:=r.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set. Furthermore, the secret computation apparatus obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.P-r.sub.P when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B and/or, the secret computation apparatus obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P when a value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B; and the secret computation apparatus obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when the value according to a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B and/or, the secret computation apparatus obtains c.sub.1P:=a.sub.1Pb.sub.1P+c.sub.P+r.sub.P when a value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B. Here, a.sub.0P, a.sub.1P, b.sub.0P and b.sub.1P are values according to a.sub.0P, a.sub.1P, b.sub.0P and b.sub.1P, respectively. Further, c.sub.0P and c.sub.1P are secret share values of the multiplication result ab. When a value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P and a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is obtained from the meta information A and B, restoration of the operation result ab is possible without c.sub.0P. In this case, operation of c.sub.0P can be omitted. Further, when a value according to a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P and a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is obtained from the meta information A and B, restoration of the operation result ab is possible without c.sub.1P. In this case, operation of c.sub.1P can be omitted.

(18) More specifically, for example, the secret computation apparatus sets C.sub.0P:= when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B, and, when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is obtained from the meta information A and B, obtains the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P from the meta information A and B and sets the value as C.sub.0P. Further, for example, the secret computation apparatus sets C.sub.1P:= when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B, and, when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is obtained from the meta information A and B, obtains the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P from the meta information A and B and sets the value as C.sub.1P. Furthermore, for example, the secret computation apparatus sets C.sub.2P:= when a value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.or+a.sub.orb.sub.2P is not obtained from the meta information A and B, and, when the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is obtained, obtains the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P from the meta information A and B and sets the value as C.sub.2P. In this case, C.sub.0P, C.sub.1P, C.sub.2P are meta information about secret share values of the multiplication result ab. In the case of C.sub.0P:=, the secret share values of the multiplication result ab include c.sub.0P; and, in the case of C.sub.1P:=, the secret share values of the multiplication result ab include c.sub.1P. As described above, it is possible to reduce the number of times of transferring values among the secret computation apparatuses and the number of times of transferring the secret share values at the time of restoration and improve efficiency. Furthermore, in the case of omitting operation of c.sub.0P or c.sub.1P, it is also possible to reduce the amount of operation in the secret computation apparatuses.

(19) Further, for example, when the meta information A indicates a value according to a.sub.0P, a.sub.0P is the value indicated by the meta information A. When the meta information A indicates a value according to a.sub.1P, a.sub.1P is the value indicated by the meta information A. When the meta information B indicates a value according to b.sub.0P, b.sub.0P is the value indicated by the meta information B. When the meta information B indicates a value according to b.sub.1P, b.sub.1P is the value indicated by the meta information B. Here, when a condition that the amount of data of the value according to a.sub.0P indicated by the meta information A is smaller than the amount of data of a.sub.0P (a condition 1-1), and/or the amount of data of the value according to a.sub.1P indicated by the meta information A is smaller than the amount of data of a.sub.1P (a condition 1-2), and/or the amount of data of the value according to b.sub.0P indicated by the meta information B is smaller than the amount of data of b.sub.0P (a condition 1-3), and/or the amount of data of the value according to b.sub.1P indicated by the meta information B is smaller than the amount of data of b.sub.1P (a condition 1-4) is satisfied, it is possible to reduce the amount of operation more than the case of using shares.

(20) In the case of applying the scheme described before to product-sum operation, the operation result is an operation result .sub.n{0, . . . , N-1}a(n)b(n) between an input value {a(0), . . . , a(N1)} and a second input value {b(0), . . . , b(N1)} (n{0, . . . , N1}, N1), and secret computation of the operation .sub.n{0, . . . , N-1}a(n)b(n) is performed by three secret computation apparatuses. Here, a(n) satisfies a(n)=a.sub.0P(n)+a.sub.1P(n)+a.sub.2P(n) for subshares a.sub.0P(n), a.sub.1P(n), a.sub.2P(n), and b(n) satisfies b(n)=b.sub.0P(n)+b.sub.1P(n)+b.sub.2P(n) for second subshares b.sub.0P(n), b.sub.1P(n), b.sub.2P(n). Here, .sub.n{0, . . . , N-1}(n).sup. indicates (0)+ . . . +(N1). That is, .sub.n{0, . . . , N-1}(n) indicates:

(21) $\begin{array}{cc}\underset{n=0}{\overset{N-1}{.Math.}}\left(n\right)& \left[\mathrm{Formula}1\right]\end{array}$
The secret computation apparatus stores an assigned share (a.sub.0P(n), a.sub.1P(n)) which is a proper subset of a subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)), meta information A indicating values according to elements of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)) or indicating that the elements are concealed values, a second assigned share (b.sub.0P, b.sub.1P) which is a proper subset of a second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)), and second meta information B indicating values according to elements of the second subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)) or indicating that the elements are concealed values. When a value according to a provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, the secret computation apparatus performs communication for sharing a first arbitrary value r.sub.P with an external secret computation apparatus (a first secret computation apparatus). Otherwise, the communication for sharing the first arbitrary value r.sub.P is unnecessary. When a value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, the secret computation apparatus performs communication for sharing a second arbitrary value r.sub.P with an external secret computation apparatus (a second secret computation apparatus). Otherwise, the communication for sharing the second arbitrary value r.sub.P is unnecessary. The secret computation apparatus outputs the provided value c.sub.P:=.sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)}+r.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and accepts input of an acquired value c.sub.P, when a value according to an acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B. Here, c.sub.P+:=.sub.n{0, . . . , N-1}{a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P}+r.sub.P+ is satisfied. Otherwise, the above communications are unnecessary. The secret computation apparatus sets c.sub.P:=c.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets c.sub.P:=0 when c.sub.P:=c.sub.P is not set. The secret computation apparatus sets c.sub.P+:=c.sub.P+ when the value according to the acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, and sets c.sub.P+:=0 when c.sub.P+:=c.sub.P+ is not set. Further, the secret computation apparatus sets r.sub.P:=r.sub.P when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set. The secret computation apparatus sets r.sub.P: =r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, and sets r.sub.P:=0 when r.sub.P:=r.sub.P is not set. Furthermore, the secret computation apparatus obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P (n)+cPr.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B and/or, the secret computation apparatus obtains c.sub.0P:=.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P/(n)b.sub.0P(n)} is not obtained from the meta information A and B. The secret computation apparatus obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B and/or, the secret computation apparatus obtains c.sub.1P:=.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P when a value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B. Here, a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n) are values according to a.sub.0P(n), a.sub.1P(n), b.sub.0P(n) and b.sub.1P(n), respectively. Further, c.sub.0P and c.sub.1P are secret share values of the multiplication result .sub.n{0, . . . , N-1}a(n)b(n). When the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} and .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is obtained from the meta information A and B, it is possible to restore the operation result .sub.n{0, . . . , N-1}a(n)b(n) without c.sub.0P. In this case, operation of c.sub.0P can be omitted. Furthermore, when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} and .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} and .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is obtained from the meta information A and B, it is possible to restore the operation result .sub.n{0, . . . , N-1}a(n)b(n) without c.sub.1P. In this case, operation of c.sub.1P can be omitted.

(22) More specifically, for example, when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B, the secret computation apparatus sets C.sub.0P:=. For example, when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is obtained from the meta information A and B, the secret computation apparatus obtains the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} and sets the value as C.sub.0P. For example, when the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B, the secret computation apparatus sets C.sub.1P:=. For example, when the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is obtained from the meta information A and B, the secret computation apparatus obtains the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} and sets the value as C.sub.1P. For example, when a value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B, the secret computation apparatus sets C.sub.2P:=. For example, when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is obtained, the secret computation apparatus obtains the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} from the meta information A and B and sets the value as C.sub.2P. Here, C.sub.0P, C.sub.1P, C.sub.2P are meta information about the secret share values of the operation result .sub.n{0, . . . , N-1}a(n)b(n). In the case of C.sub.0P:=, the secret share values of the operation result .sub.n{0, . . . , N-1}a(n)b(n) include c.sub.0P; and, in the case of C.sub.1P:=, the secret share values of the operation result .sub.n{0, . . . , N-1}a(n)b(n) include c.sub.1P. As described above, it is possible to reduce the number of transferring values among the secret computation apparatuses and the amount of transfer of the secret share values at the time of restoration and improve efficiency. Furthermore, in the case of omitting operation of c.sub.0P or c.sub.1P, it is also possible to reduce the amount of operation in the secret computation apparatus.

(23) Further, for example, when the meta information A indicates a value according to a.sub.0P(n), a.sub.0P(n) is the value indicated by the meta information A. When the meta information A indicates a value according to a.sub.1P(n), a.sub.1P(n) is the value indicated by the meta information A. When the meta information B indicates a value according to b.sub.0P(n), b.sub.0P(n) is the value indicated by the meta information B. When the meta information B indicates a value according to b.sub.1P(n), b.sub.0P(n) is the value indicated by the meta information B. Here, when a condition that the amount of data of the value according to a.sub.0P(n) indicated by the meta information A is smaller than the amount of data of a.sub.0P(n) (a condition 2-1), and/or the amount of data of the value according to a.sub.1P(n) indicated by the meta information A is smaller than the amount of data of a.sub.1P(n) (a condition 2-2), and/or the amount of data of the value according to b.sub.0P(n) indicated by the meta information B is smaller than the amount of data of b.sub.0P(n) (a condition 2-3), and/or the amount of data of the value according to b.sub.1P(n) indicated by the meta information B is smaller than the amount of data of b.sub.1P(n) (a condition 2-4) is satisfied, it is possible to reduce the amount of operation more than the case of using shares.

First Embodiment

(24) In a first embodiment, an example of applying the scheme described above to multiplication will be described.

(25) <Configuration>

(26) As illustrated in FIG. 1, a secret computation system 1 of the present embodiment has three secret computation apparatuses 11-0, 11-1 and 11-2, and these are configured to be communicable via a network such as the Internet. As illustrated in FIG. 2, a secret computation apparatus 11-P (P=0, 1, 2) of the present embodiment has a storage 111-P, an operation part 112-P, a controller 113-P, a sharing part 114-P and a communication part 115-P. The operation part 112-P has processing parts 1120-P to 112A-P. The secret computation apparatus 11-P is configured, for example, by a general-purpose or dedicated computer provided with a processor (a hardware processor) such as a CPU (central processing unit) and a memory such as a RANI (random-access memory) and a ROM (read-only memory), and the like executing a predetermined program. The computer may be provided with one processor and one memory or may be provided with a plurality of processors and memories. The program may be installed into the computer or may be recorded in a ROM or the like in advance. A part or all of the processing parts may be configured not with an electronic circuitry that realizes a functional configuration by a program being read, like the CPU, but with an electronic circuitry that realizes processing functions without using a program. Further, an electronic circuitry constituting one secret computation apparatus 11-m may comprise a plurality of CPUs. Each process executed by the secret computation apparatus 11-P is executed under the control of the controller 113-P, and information obtained by each process is stored into a temporary memory (not shown). The information stored into the temporary memory is read and used as necessary.

(27) <Premises for Processing>

(28) In the present embodiment, secret computation of multiplication ab between an input value a and an input value b is performed. The input value a is divided into three subshares a.sub.1, a.sub.2, a.sub.3 satisfying a=a.sub.1+a.sub.2+a.sub.3, and the input value b is divided into three subshares b.sub.1, b.sub.2, b.sub.3 satisfying b=b.sub.1+b.sub.2+b.sub.3. That is, the input value a is a function value of the subshares a.sub.1, a.sub.2, a.sub.3, and the input value b is a function value of the subshares b.sub.1, b.sub.2, b.sub.3. A share (a.sub.0P, a.sub.1P) (an assigned share), which is a proper subset of a subshare set (a.sub.0P, a.sub.1P, a.sub.2P) with three subshares a.sub.0P, a.sub.1P, a.sub.2P as elements, is assigned to each secret computation apparatus 11-P (P=0, 1, 2). Here, a.sub.0P=a.sub.1(P1 mod 3) and a.sub.1P=a.sub.0(P+1 mod 3) are satisfied. Other proper subsets (a.sub.0P, a.sub.2P) and (a.sub.1P, a.sub.2P) of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P) will be called external assigned shares. Further, a share (b.sub.0P, b.sub.1P) (an assigned share), which is a proper subset of a subshare set (b.sub.0P, b.sub.1P, b.sub.2P) with three subshares b.sub.0P, b.sub.1P, b.sub.2P as elements, is assigned to each secret computation apparatus 11-P (P=0, 1, 2). Here, b.sub.0P=b.sub.1(P1 mod 3) and b.sub.1P=b.sub.0(P+1 mod 3) are satisfied. Other proper subsets (b.sub.0P, b.sub.2P) and (b.sub.1P, b.sub.2P) of the subshare set (b.sub.0P, b.sub.1P, b.sub.2P) will be called external assigned shares. That is, shares (a.sub.00, a.sub.10)=(a.sub.2, a.sub.0) and (b.sub.00, b.sub.10)=(b.sub.2, b.sub.0) are assigned to the secret computation apparatus 11-0, shares (a.sub.01, a.sub.11)=(a.sub.0, a.sub.1) and (b.sub.01, b.sub.11)=(b.sub.0, b.sub.1) are assigned to the secret computation apparatus 11-1, and shares (a.sub.02, a.sub.12)=(a.sub.1, a.sub.2) and (b.sub.02, b.sub.12)=(b.sub.1, b.sub.2) are assigned to the secret computation apparatus 11-2. For the secret computation apparatus 11-P, shares that are not assigned thereto are the external assigned shares. In the storage 111-P of each secret computation apparatus 11-P (FIG. 2), the shares (a.sub.0P, a.sub.1P) and (b.sub.0P, b.sub.1P) (assigned shares) are stored (FIG. 3). These subshares apparently satisfy relationships of a=a.sub.0P+a.sub.1P+a.sub.2P and b=b.sub.0P+b.sub.1P+b.sub.2P.

(29) Meta information A indicating values according to the elements of the subshare set (a.sub.0P, a.sub.1P, a.sub.2P) or indicating that the elements are concealed values, and meta information B indicating values according to the elements of the subshare set (b.sub.0P, b.sub.1P, b.sub.2P) or indicating that the elements are concealed values are set. The meta information A indicating values according to elements a.sub.JP may indicate values A.sub.JP indicating the elements a.sub.JP (J=0, 1, 2) (that is, A.sub.JP:=a.sub.JP) or may indicate values A.sub.JP that satisfy a.sub.JP=f(A.sub.JP) for a function f that uniquely specifies the elements a.sub.JP. In the former case, A.sub.JP are elements of a set R with values that the input value a can take as elements. In the latter case, A.sub.JP are elements of such a domain R that a range of a function f belongs to the set R. The function f is, for example, a homomorphism function. The amount of data of the elements of the domain R may be smaller than the amount of data of the elements of the set R. The meta information A indicating that the elements a.sub.JP are concealed values indicates the values A.sub.JP= indicating that the elements a.sub.JP (J=0, 1, 2) are concealed values. In the case of A.sub.JP=, it is not possible to obtain the values of the elements a.sub.JP only from the meta information A. Any information that indicates such values A.sub.0P, A.sub.1P, A.sub.2P may be made to be the meta information A. For example, a set (A.sub.0P, A.sub.1P, A.sub.2P) with values A.sub.0P, A.sub.1P, A.sub.2P as elements may be made to be the meta information A; one value indicating the set (A.sub.0P, A.sub.1P, A.sub.2P) may be made to be the meta information A; or a set of values each of which indicates a subset with a plurality of elements of the set (A.sub.0P, A.sub.1P, A.sub.2P) may be made to be the meta information A. The above point similarly applies to the meta information B, and any information that indicates values B.sub.0P, B.sub.1P, B.sub.2P may be made to be the meta information B. Here, B.sub.JP:=b.sub.JP or b.sub.JP=f(B.sub.JP) or B.sub.JP:= is satisfied. If at least one of A.sub.0P, A.sub.1P, A.sub.1P, B.sub.0P, B.sub.1P and B.sub.2P is not , the number of times of transferring values among the secret computation apparatuses 11-P can be reduced. The meta information A and B are stored in the storages 111-P of all the secret computation apparatuses 11-P (P=0, 1, 2).

(30) <Secret Computation Process>

(31) Next, content of a process for secret computation of the present embodiment will be described with the use of FIGS. 3 to 7. Each of the secret computation apparatuses 11-P (P=0, 1, 2) executes the following process.

(32) The sharing part 114-P of the secret computation apparatus 11-P performs processing according to whether x.sub.01 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F). Here, x.sub.JK:=[A.sub.JPB.sub.KP+A.sub.KPB.sub.JP=]{T, F} ((J, K)=(0, 1), (1, 2), (2, 0)) is satisfied, and [A.sub.JPB.sub.KP+A.sub.KPB.sub.JP=] indicates a truth value indicating whether a proposition that A.sub.JPB.sub.KP+A.sub.KPB.sub.JP= is satisfied is true (T) or false (F). That A.sub.JPB.sub.KP+A.sub.KPB.sub.JP= is satisfied means that a value according to a.sub.JPb.sub.KP+a.sub.KPb.sub.JP is not obtained from the meta information A and B. If the value according to a.sub.JPb.sub.KP is not obtained from the meta information A and B (A.sub.JPB.sub.KP=) or the value according to a.sub.KPb.sub.JP is not obtained from the meta information A and B (A.sub.KPB.sub.JP=), the value according to a.sub.JPb.sub.KP+a.sub.KPb.sub.JP is not obtained from the meta information A and B (A.sub.JPB.sub.KP+A.sub.KPB.sub.JP=). In other words, it is meant that A.sub.JPB.sub.KP+A.sub.KPB.sub.JP= is (A.sub.JPB.sub.KP=)(A.sub.KPB.sub.JP=). For example, (1) in the case of A.sub.JP, B.sub.KPR or A.sub.JP, B.sub.KPR, A.sub.JPB.sub.KP is satisfied, and, in the case of A.sub.KP, B.sub.JPR or A.sub.KP, B.sub.JPR, A.sub.KPB.sub.JP is satisfied. (2) In the case of A.sub.JP=0, A.sub.JPB.sub.KP=0 and A.sub.JPB.sub.KP are satisfied irrespective of B.sub.KP. In the case of B.sub.KP=0, A.sub.JPB.sub.KP=0 and A.sub.JPB.sub.KP are satisfied irrespective of A. In the case of A.sub.KP=0, A.sub.KPB.sub.JP=0 and A.sub.KPB.sub.JP are satisfied irrespective of B. In the case of B.sub.JP=0, A.sub.KPB.sub.JP=0 and A.sub.KPB.sub.JP are satisfied irrespective of A.sub.KP. (3) In the case of A.sub.JP0 and B.sub.KP=, or in the case of A.sub.JP=0 and B.sub.KP0, A.sub.JPB.sub.KP= is satisfied. In the case of A.sub.KP0 and B.sub.JP=, or in the case of A.sub.KP=0 and B.sub.JP0, A.sub.KPB.sub.JP= is satisfied (step S101).

(33) If x.sub.01 is true (x.sub.01=T) (when a value according to a provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B), the sharing part 114-P performs communication for sharing an arbitrary value r.sub.P with an external secret computation apparatus 11-(P+1 mod 3). The arbitrary value r.sub.P may be a random number, a pseudorandom number or a constant. For example, the sharing part 114-P stores the generated or selected arbitrary value r.sub.P into the storage 111-P and sends it to the communication part 115-P. The communication part 115-P transmits the arbitrary value r.sub.P to the secret computation apparatus 11-(P+1 mod 3). The arbitrary value r.sub.P is inputted to a communication part 115-(P+1 mod 3) of the secret computation apparatus 11-(P+1 mod 3) and stored into a storage 111-(P+1 mod 3) (step S102). After that, the process proceeds to step S103. On the other hand, if x.sub.01 is false (x.sub.01=F), the process proceeds to step S103 without executing step S102.

(34) At step S103, the sharing part 114-P performs processing according to whether x.sub.20 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F) (step S103). If x.sub.20 is true (x.sub.20=T) (when a value according to a provided corresponding value a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B), the sharing part 114-P performs communication for sharing an arbitrary value r.sub.P:=r.sub.(P1 mod 3) with an external secret computation apparatus 11-(P1 mod 3). The arbitrary value r.sub.P may be a random number, a pseudorandom number or a constant. For example, a sharing part 114-(P1 mod 3) of the secret computation apparatus 11-(P1 mod 3) stores the generated or selected arbitrary value r.sub.P into a storage 111-(P1 mod 3) and sends it to a communication part 115-(P1 mod 3). The communication part 115-(P1 mod 3) transmits the arbitrary value r.sub.P to the secret computation apparatus 11-P. The arbitrary value r.sub.P is inputted to the sharing part 114-P, and the sharing part 114-P stores the arbitrary value r.sub.P into the storage 111-P (step S104). After that, the process proceeds to step S105. On the other hand, if x.sub.20 is false (x.sub.20=F), the process proceeds to step S105 without executing step S104.

(35) At step S105, the processing part 1120-P of the operation part 112-P performs processing according to whether x.sub.01 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F) (step S105). If x.sub.01 is true (x.sub.01=T) (when the value according to the provided corresponding value a.sub.upb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B), the processing part 1120-P reads the shares (a.sub.0P, a.sub.1P) and (b.sub.0P, b.sub.1P) and the arbitrary value r.sub.P from the storage 111-P; and obtains and outputs a provided value c.sub.P:=a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P+r.sub.P (step S106). The provided value c.sub.P is transmitted from the communication part 115-P to the external secret computation apparatus 11-(P1 mod 3). The provided value c.sub.P is inputted to the communication part 115-(P1 mod 3) of the secret computation apparatus 11-(P1 mod 3) and stored into the storage 111-(P1 mod 3) (step S107). After that, the process proceeds to step S110. On the other hand, if x.sub.01 is false (x.sub.01=F), the process proceeds to step S110 without executing steps S106 and S107.

(36) At step S110, the processing part 1127-P of the operation part 112-P obtains C.sub.0P: =A.sub.0PB.sub.0P+A.sub.0PB.sub.1P+A.sub.1PB.sub.0P from the meta information A and B stored in the storage 111-P and outputs C.sub.0P (step S110). Here, when a value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B (in the case of A.sub.0PB.sub.0P+A.sub.0PB.sub.1P+A.sub.1PB.sub.0P=), C.sub.0P:= is satisfied. In the case of A.sub.0PB.sub.0P= or A.sub.0PB.sub.1P= or A.sub.1PB.sub.0P=, A.sub.0PB.sub.0P+A.sub.1PB.sub.1P+A.sub.1PB.sub.0P= is satisfied. On the other hand, when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is obtained from the meta information A and B, C.sub.0P is the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P.

(37) Next, the processing part 1128-P of the operation part 112-P obtains C.sub.1P:=A.sub.1PB.sub.1P+A.sub.1PB.sub.2P+A.sub.2PB.sub.1P from the meta information A and B stored in the storage 111-P and outputs C.sub.1P (step S113). Here, when a value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B (in the case of A.sub.1PB.sub.1P+A.sub.1PB.sub.2P+A.sub.2PB.sub.1P=), C.sub.1P:= is satisfied. On the other hand, when the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is obtained from the meta information A and B, C.sub.1P is the value according to a.sub.1Pb.sub.1P+a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P.

(38) Next, the processing part 1128-P of the operation part 112-P obtains C.sub.2P:=A.sub.2PB.sub.2P+A.sub.2PB.sub.0P+A.sub.0PB.sub.2P from the meta information A and B stored in the storage 111-P and outputs C.sub.2P (step S116). Here, when a value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B (A.sub.2PB.sub.2P+A.sub.2PB.sub.0P+A.sub.0PB.sub.2P=), C.sub.2P:= is satisfied. On the other hand, when the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is obtained from the meta information A and B, C.sub.2P is the value according to a.sub.2Pb.sub.2P+a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P.

(39) Next, the processing part 112A-P of the operation part 112-P performs processing according to whether A.sub.0P corresponding to the meta information A stored in the storage 111-P is true (T) or false (F) (step S117). The processing part 112A-P sets a.sub.0P:=a.sub.0P (step S118) if A.sub.0P is true (A.sub.0P=T), and sets a.sub.0P:=A.sub.0P (step S119) if A.sub.0P is false (A.sub.0P=F). That is, when the meta information A indicates a value according to a.sub.0P, a.sub.0P is the value indicated by the meta information A.

(40) Further, the processing part 112A-P performs processing according to whether A.sub.1P corresponding to the meta information A stored in the storage 111-P is true (T) or false (F) (step S120). The processing part 112A-P sets a.sub.1P:=a.sub.1P (step S121) if A.sub.1P is true (A.sub.1P=T); and sets a.sub.1P:=A.sub.1P and outputs a.sub.1P (step S122) if A.sub.1P is false (A.sub.1P=F). That is, when the meta information A indicates a value according to a.sub.1P, a.sub.1P is the value indicated by the meta information A.

(41) Further, the processing part 112A-P performs processing according to whether B.sub.0P corresponding to the meta information B stored in the storage 111-P is true (T) or false (F) (step S123). The processing part 112A-P sets b.sub.0P:=b.sub.0P (step S124) if B.sub.0P is true (B.sub.0P=T); and sets b.sub.0P:=B.sub.0P and outputs b.sub.0P (step S125) if B.sub.0P is false (B.sub.0P=F). That is, when the meta information B indicates a value according to b.sub.0P, b.sub.0P is the value indicated by the meta information B.

(42) Next, the processing part 112A-P performs processing according to whether B.sub.1P corresponding to the meta information B stored in the storage 111-P is true (T) or false (F) (step S126). The processing part 112A-P sets b.sub.1P:=b.sub.1P (step S127) if B.sub.1P is true (B.sub.1P=T); and sets b.sub.1P:=B.sub.1P and outputs b.sub.1P (step S128) if B.sub.1P is false (B.sub.1P=F). That is, when the meta information B indicates a value according to b.sub.1P, b.sub.1P is the value indicated by the meta information B.

(43) The processing part 1121-P of the operation part 112-P performs processing according to whether x.sub.10 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F) (step S129). If x.sub.10 is true (x.sub.10=T) (when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B), the processing part 1121-P sets c.sub.P:=c.sub.P (step S130). Otherwise (when c.sub.P:=c.sub.P is not set), the processing part 1121-P sets c.sub.P:=0 (step S131) and outputs c.sub.P.

(44) The processing part 1122-P of the operation part 112-P performs processing according to whether x.sub.12 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F) (step S132). If x.sub.12 is true (T) (when a value according to an acquired corresponding value a.sub.1Pb.sub.2P+a.sub.2Pb.sub.1P is not obtained from the meta information A and B), the acquired value c.sub.P+:=c.sub.(P+1 mod 3) have been transmitted from the secret computation apparatus 11-(P+1 mod 3) at step S107 described before. The acquired value c.sub.P+ is inputted to the processing part 1122-P (step S133). The processing part 1122-P sets and outputs c.sub.P+:=c.sub.P+ (step S134). On the other hand, if x.sub.12 is false (F) (when c.sub.P+:=c.sub.P+ is not set), the processing part 1122-P sets and outputs c.sub.P+:=0 (step S135).

(45) The processing part 1123-P of the operation part 112-P performs processing according to whether x.sub.01 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F) (step S136). If x.sub.01 is true (T) (when the value according to the provided corresponding value a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B), the processing part 1122-P sets r.sub.P:=r.sub.P (step S137). Otherwise (when r.sub.P:=r.sub.P is not set), the processing part 1122-P sets r.sub.P:=0 (step S138) and outputs r.sub.P.

(46) The processing part 1124-P of the operation part 112-P performs processing according to whether x.sub.20 corresponding to the meta information A and B stored in the storage 111-P is true (T) or false (F) (step S139). If x.sub.20 is true (T) (when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B), the processing part 1124-P sets r.sub.P:=r.sub.P (step S140). Otherwise (when r.sub.P:=r.sub.P is not set), the processing part 1124-P sets r.sub.P:=0 (step S141) and outputs rP.sub..

(47) The processing part 1125-P of the operation part 112-P performs processing according to whether C.sub.0P= is satisfied or not (step S142). If C.sub.0P= is satisfied, the processing part 1125-P obtains c.sub.0P:=a.sub.0Pb.sub.1P+c.sub.Pr.sub.P (step S143); the operation part 112-P outputs c.sub.0P (step S144); and the process proceeds to step S145. C.sub.0P= is satisfied when the value according to a.sub.2Pb.sub.0P+a.sub.0Pb.sub.2P is not obtained from the meta information A and B or, C.sub.0P= is satisfied when the value according to a.sub.0Pb.sub.0P+a.sub.0Pb.sub.1P+a.sub.1Pb.sub.0P is not obtained from the meta information A and B. On the other hand, if C.sub.0P= is not satisfied, the process proceeds to step S145 without executing steps S143 and S144.

(48) At step S145, the processing part 1126-P of the operation part 112-P performs processing according to whether C.sub.1P= is satisfied or not (step S145). If C.sub.1P= is satisfied, the processing part 1126-P obtains c.sub.1P:=a.sub.1Pb.sub.1P++c.sub.Pr.sub.P (step S146), and the operation part 112-P outputs c.sub.1P (step S147). On the other hand, if C.sub.1P= is not satisfied, the process proceeds to step S148 without executing steps S146 and S147.

(49) At step 148, the operation part 112-P outputs C.sub.0P, C.sub.1P, C.sub.2P. Here, C.sub.0P, C.sub.1P, C.sub.2P are meta information about the secret share values of the operation result ab. Here, c.sub.0P and c.sub.1P are secret share values of the operation result ab. Here, c.sub.0P is required to be outputted only in the case of C.sub.0P:=, and c.sub.1P is required to be outputted only in the case of C.sub.1P:=.

(50) <Features of the Present Embodiment>

(51) In the present embodiment, it is possible to reduce the number of times of transmission/reception of values among the secret computation apparatuses 11-P according to values indicated by meta information A and B. Further, in the case where operation of a value that is not required to be transmitted or received any more can be omitted, the amount of operation can be also reduced. Furthermore, in the case where the amount of operation using the meta information is smaller than the amount of operation using shares also, it is possible to reduce the amount of operation.

Second Embodiment

(52) In a second embodiment, an example of applying the scheme described above to product-sum operation will be described.

(53) <Configuration>

(54) As illustrated in FIG. 1, a secret computation system 2 of the present embodiment has three secret computation apparatuses 21-0, 21-1 and 21-2, and these are configured to be communicable via a network such as the Internet. As illustrated in FIG. 2, a secret computation apparatus 21-P (P=0, 1, 2) of the present embodiment has a storage 211-P, an operation part 212-P, a controller 213-P, a sharing part 214-P and a communication part 215-P. The operation part 212-P has processing parts 2120-P to 212A-P. The secret computation apparatus 21-P is configured, for example, by the computer described before executing a predetermined program. Each process executed by the secret computation apparatus 21-P is executed under control of the controller 213-P, and information obtained by each process is stored into a temporary memory (not shown). The information stored into the temporary memory is read and used as necessary.

(55) <Premises for Processing>

(56) In the present embodiment, secret computation of product-sum operation .sub.n{0, . . . , N-1}a(n)b(n) between an input value {a(0), . . . , a(N1)} and an input value {b(0), . . . , b(N1)} is performed. Though N1 is satisfied, a process is the same as the first embodiment in the case of N=1. It is in the case of N2 that the present embodiment is substantially meaningful. Each a(n) (n=0, . . . , N1) is divided into three subshares a.sub.1(n), a.sub.2(n), a.sub.3(n) satisfying a(n)=a.sub.1(n)+a.sub.2(n)+a.sub.3(n), and each b(n) is divided into three subshares b.sub.1(n), b.sub.2(n), b.sub.3(n) satisfying b(n)=b.sub.1(n)+b.sub.2(n)+b.sub.3(n). That is, a(n) is a function value of the subshares a.sub.1(n), a.sub.2(n), a.sub.3(n), and b(n) is a function value of the subshares b.sub.1(n), b.sub.2(n), b.sub.3(n). To each secret computation apparatus 21-P (P=0, 1, 2), a share (a.sub.0P(n), a.sub.1P(n)) (an assigned share), which is a proper subset of a subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)) with three subshares a.sub.0P(n), a.sub.1P(n), a.sub.2P(n) as elements, is assigned. Here, a.sub.0P(n)=a.sub.1(n).sub.(P1 mod 3) and a.sub.1P(n)=a.sub.0(n).sub.(p+1 mod 3) are satisfied. Further, to each secret computation apparatus 21-P (P=0, 1, 2), a share (b.sub.0P(n), b.sub.1P(n)) (an assigned share), which is a proper subset of a subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)) with three subshares b.sub.0P(n), b.sub.1P(n), b.sub.2P(n) as elements, is assigned. Here, b.sub.0P(n)=b.sub.1(n).sub.(P1 mod 3) and b.sub.1P(n)=b.sub.0(n).sub.(P+1 mod 3) are satisfied. That is, shares (a.sub.00(n), a.sub.10(n))=(a.sub.2(n), a.sub.0(n)) and (b.sub.00(n), b.sub.10(n))=(b.sub.2(n), b.sub.0(n)) are assigned to the secret computation apparatus 21-0, shares (a.sub.01(n), a.sub.11(n))=(a.sub.0(n), a.sub.1(n)) and (b.sub.01(n), b.sub.11(n))=(b.sub.0(n), b.sub.1(n)) are assigned to the secret computation apparatus 21-1, and shares (a.sub.02(n), a.sub.12(n))=(a.sub.1(n), a.sub.2(n)) and (b.sub.02(n), b.sub.12(n))=(b.sub.1(n), b.sub.2(n)) are assigned to the secret computation apparatus 21-2. For the secret computation apparatus 21-P, shares that are not assigned thereto are the external assigned shares. In the storage 211-P of each secret computation apparatuses 21-P (FIG. 2), the shares (a.sub.0P(n), a.sub.1P(n)) and (b.sub.0P(n), b.sub.1P(n)) (assigned shares) are stored (FIG. 8). These subshares apparently satisfy relationships of a(n)=a.sub.0P(n)+a.sub.1P(n)+a.sub.2P(n) and b(n)=b.sub.0P(n)+b.sub.1P(n)+b.sub.2P(n).

(57) Meta information A indicating values according to the elements of the subshare set (a.sub.0P(n), a.sub.1P(n), a.sub.2P(n)) or indicating that the elements are concealed values, and meta information B indicating values according to the elements of the subshare set (b.sub.0P(n), b.sub.1P(n), b.sub.2P(n)) or indicating that the elements are concealed values are set. The meta information A indicating values according to the elements a.sub.JP(n) may indicate values A.sub.JP(n) indicating the elements a.sub.JP(n) (J=0, 1, 2) (that is, A.sub.JP(n):=a.sub.JP(n)) or may indicate values A.sub.JP(n) that satisfy a.sub.JP(n)=f(A.sub.JP(n)) for a function f that uniquely specifies the elements a.sub.JP(n). The function f is, for example, a homomorphism function. In the former case, A.sub.JP(n) are elements of a set R with values that the input value a(n) can take as elements. In the latter case, A.sub.JP(n) are elements of such a domain R that a range of a function f belongs to the set R. The meta information A indicating that the elements a.sub.JP(n) are concealed values indicates the values A.sub.JP(n)= indicating that the elements a.sub.JP(n) (J=0, 1, 2) are concealed values. In the case of A.sub.JP(n)=, it is not possible to obtain the values of the elements a.sub.JP(n) only from the meta information A. Any information that indicates such values A.sub.0P(n), A.sub.1P(n), A.sub.2P(n) may be made to be the meta information A. For example, a set (A.sub.0P(n), A.sub.1P(n), A.sub.2P(n)) (n=0, . . . N1) with values A.sub.0P(n), A.sub.1P(n), A.sub.2P(n) as elements may be made to be the meta information A; one value indicating the set (A.sub.0P(n), A.sub.1P(n), A.sub.2P(n)) may be made to be the meta information A; or a set of values each of which indicates a subset with a plurality of elements of the set (A.sub.0P(n), A.sub.1P(n), A.sub.2P(n)) may be made to be the meta information A. The above point similarly applies to the meta information B, and any information that indicates values B.sub.0P(n), B.sub.1P(n), B.sub.2P(n) may be made to be the meta information B. Here, B.sub.JP(n):=b.sub.JP(n) or b.sub.JP(n)=f(B.sub.JP(n)) or B.sub.JP(n):= is satisfied. In the present embodiment, if at least one of A.sub.0P(n), A.sub.1P(n), A.sub.2P(n), B.sub.0P(n), B.sub.1P(n) and B.sub.2P(n) is not , the number of times of transferring values among the secret computation apparatuses 21-P can be reduced. The meta information A and B are stored in the storages 211-P of all the secret computation apparatuses 21-P (P=0, 1, 2).

(58) <Secret Computation Process>

(59) Next, content of a process for secret computation of the present embodiment will be described with the use of FIGS. 8 to 12. Each of the secret computation apparatuses 21-P (P=0, 1, 2) executes the following process.

(60) The sharing part 214-P of the secret computation apparatus 21-P performs processing according to whether x.sub.01 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F). Here, x.sub.JK:=[.sub.n{0, . . . , N-1}{A.sub.JP(n)B.sub.KP(n)+A.sub.KP(n)B.sub.JP(n)}=]{T, F}((J, K)=(0, 1), (1, 2), (2, 0); n=0, . . . , N1) is satisfied. Here, [.sub.n{0, . . . , N-1}{A.sub.JP(n)B.sub.KP(n)+A.sub.KP(n)B.sub.JP(n)}=] indicates a truth value indicating whether a proposition that .sub.n{0, . . . , N-1}{A.sub.JP(n)B.sub.KP(n)+A.sub.KP(n)B.sub.JP(n)}= is satisfied is true (T) or false (F). That .sub.n{0, . . . , N-1}{A.sub.JP(n)B.sub.KP(n)+A.sub.KP(n)B.sub.JP(n)}= is satisfied means that a value according to .sub.n{0, . . . , N-1}{a.sub.JP(n)b.sub.KP(n)+a.sub.KP(n)b.sub.JP(n)} is not obtained from the meta information A and B (step S201).

(61) If x.sub.01 is true (x.sub.01=T) (when a value according to a provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B), the sharing part 214-P performs communication for sharing an arbitrary value r.sub.P with an external secret computation apparatus 21-(P+1 mod 3). For example, the sharing part 214-P stores the generated or selected arbitrary value r.sub.P into the storage 211-P and sends it to the communication part 215-P. The communication part 215-P transmits the arbitrary value r.sub.P to the secret computation apparatus 21-(P+1 mod 3). The arbitrary value r.sub.P is inputted to a communication part 215-(P+1 mod 3) of the secret computation apparatus 21-(P+1 mod 3) and stored into a storage 211-(P+1 mod 3) (step S202). After that, the process proceeds to step S203. On the other hand, if x.sub.01 is false (x.sub.01=F), the process proceeds to step S203 without executing step S202.

(62) At step S203, the sharing part 214-P performs processing according to whether x.sub.20 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F) (step S203). If x.sub.20 is true (x.sub.20=T) (when a value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B), the sharing part 214-P performs communication for sharing an arbitrary value r.sub.P:=r.sub.(P1 mod 3) with an external secret computation apparatus 21-(P1 mod 3). The arbitrary value r.sub.P may be a random number, a pseudorandom number or a constant. For example, a sharing part 214-(P1 mod 3) of the secret computation apparatus 21-(P1 mod 3) stores the generated or selected arbitrary value r.sub.P into a storage 211-(P1 mod 3) and sends it to a communication part 215-(P1 mod 3). The communication part 215-(P1 mod 3) transmits the arbitrary value r.sub.P to the secret computation apparatus 21-P. The arbitrary value r.sub.P is inputted to the sharing part 214-P, and the sharing part 214-P stores the arbitrary value r.sub.P into the storage 211-P (step S204). After that, the process proceeds to step S205. On the other hand, if x.sub.20 is false (x.sub.20=F), the process proceeds to step S205 without executing step S204.

(63) At step S205, the processing part 2120-P of the operation part 212-P performs processing according to whether x.sub.01 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F) (step S205). If x.sub.01 is true (x.sub.01=T) (when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B), the processing part 2120-P reads the shares (a.sub.0P(n), a.sub.1P(n)) and (b.sub.0P(n), b.sub.1P(n)) and the arbitrary value r.sub.P from the storage 211-P; and obtains and outputs a provided value c.sub.P:=.sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)}+r.sub.P (step S206). The provided value c.sub.P is transmitted from the communication part 215-P to the external secret computation apparatus 21-(P1 mod 3). The provided value c.sub.P is inputted to the communication part 215-(P1 mod 3) of the secret computation apparatus 21-(P1 mod 3) and stored into the storage 211-(P1 mod 3) (step S207). After that, the process proceeds to step S210. On the other hand, if x.sub.01 is false (x.sub.01=F), the process proceeds to step S210 without executing steps S206 and S207.

(64) At step S210, the processing part 2127-P of the operation part 212-P obtains C.sub.0P:=.sub.n{0, . . . , N-1}{A.sub.0P(n)B.sub.0P(n)+A.sub.0P(n)B.sub.1P(n)+A.sub.1P(n)B.sub.0P(n)} from the meta information A and B stored in the storage 211-P and outputs C.sub.0P (step S210). Here, if a value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B (in the case of .sub.n{0, . . . , N-1}{A.sub.0P(n)B.sub.0P(n)+A.sub.0P(n)B.sub.1P(n)+A.sub.1P(n)B.sub.0P(n)}=), C.sub.0P:= is satisfied. On the other hand, if the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is obtained from the meta information A and B, C.sub.0P is the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)}.

(65) Next, the processing part 2128-P of the operation part 212-P obtains C.sub.1P:=.sub.n{0, . . . , N-1}{A.sub.1P(n)B.sub.1P(n)+A.sub.1P(n)B.sub.2P(n)+A.sub.2P(n)B.sub.1P(n)} from the meta information A and B stored in the storage 211-P and outputs C.sub.1P (step S213). Here, if a value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B .sub.n{0, . . . , N-1}{A.sub.1P(n)B.sub.1P(n)+A.sub.1P(n)B.sub.2P(n)+A.sub.2P(n)B.sub.1P(n)}=), C.sub.1P:= is satisfied. On the other hand, if the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is obtained from the meta information A and B, C.sub.1P is the value according to .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)}.

(66) Next, the processing part 2128-P of the operation part 212-P obtains C.sub.2P:=.sub.n{0, . . . , N-1}{A.sub.2P(n)B.sub.2P(n)+A.sub.2P(n)b.sub.0P(n)+A.sub.0P(n)B.sub.2P(n)} from the meta information A and B stored in the storage 211-P and outputs C.sub.2P (step S216). Here, if a value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B .sub.n{0, . . . , N-1}{A.sub.2P(n)B.sub.2P(n)+A.sub.2P(n)B.sub.0P(n)+A.sub.0P(n)B.sub.2P(n)}=), C.sub.2P:= is satisfied. On the other hand, if the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is obtained from the meta information A and B, C.sub.2P is the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)}.

(67) The controller 213-P performs initialization so that n:=0 is obtained (step S2151). Next, the processing part 212A-P of the operation part 212-P performs processing according to whether A.sub.0P(n) corresponding to the meta information A stored in the storage 211-P is true (T) or false (F) (step S217). The processing part 212A-P sets a.sub.0P(n):=a.sub.0P(n) (step S218) if A.sub.0P(n) is true (A.sub.0P(n)=T), and sets a.sub.0P(n):=A.sub.0P(n) (step S219) if A.sub.0P(n) is false (A.sub.0P(n)=F). That is, if the meta information A indicates a value according to a.sub.0P(n), a.sub.0P(n) is the values indicated by the meta information A.

(68) Further, the processing part 212A-P performs processing according to whether A.sub.1P(n) corresponding to the meta information A stored in the storage 211-P is true (T) or false (F) (step S220). The processing part 212A-P sets a.sub.1P(n):=a.sub.1P(n) (step S221) if A.sub.1P(n) is true (A.sub.1P(n)=T); and sets a.sub.1P(n):=A.sub.1P(n) and outputs a.sub.1P(n) (step S222) if A.sub.1P(n) is false (A.sub.1P(n)=F). That is, if the meta information A indicates a value according to a.sub.1P(n), a.sub.1P(n) is the values indicated by the meta information A.

(69) Further, the processing part 212A-P performs processing according to whether B.sub.0P(n) corresponding to the meta information B stored in the storage 211-P is true (T) or false (F) (step S223). The processing part 212A-P sets b.sub.0P(n):=b.sub.0P(n) (step S224) if B.sub.0P(n) is true (B.sub.0P(n)=T); and sets b.sub.0P(n):=B.sub.0P(n) and outputs b.sub.0P(n) (step S225) if B.sub.0P(n) is false (B.sub.0P(n)=F). That is, if the meta information B indicates a value according to b.sub.0 (n), b.sub.0P(n) is the values indicated by the meta information B.

(70) Next, the processing part 212A-P performs processing according to whether B.sub.1P(n) corresponding to the meta information B stored in the storage 211-P is true (T) or false (F) (step S226). The processing part 212A-P sets b.sub.1P(n):=b.sub.1P(n) (step S227) if B.sub.1P(n) is true (B.sub.1P(n)=T); and sets b.sub.1P(n):=B.sub.1P(n) and outputs b.sub.1P(n) (step S228) if B.sub.1P(n) is false (B.sub.1P(n)=F). That is, if the meta information B indicates a value according to b.sub.1P(n), b.sub.1P(n) is the values indicated by the meta information B.

(71) The controller 213-P judges whether n=N-1 is satisfied (step S2152). Here, if n=N-1 is not satisfied, the controller 213-P sets n:=n+1 (step S2153) and returns to step S217. If n=N1 is satisfied, the processing part 2121-P of the operation part 212-P performs processing according to whether x.sub.10 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F) (step S229). If x.sub.10 is true (x.sub.10=T) (when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B), the processing part 2121-P sets c.sub.P:=C.sub.P (step S230). Otherwise (when c.sub.P:=c.sub.P is not set), the processing part 2121-P sets c.sub.P:=0 (step S231) and outputs c.sub.P.

(72) The processing part 2122-P of the operation part 212-P performs processing according to whether x.sub.12 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F) (step S232). If x.sub.12 is true (T) (when a value according to an acquired corresponding value .sub.n{0, . . . , N-1}{a.sub.1P(n)b.sub.2P(n)+a.sub.2P(n)b.sub.1P(n)} is not obtained from the meta information A and B), the acquired value c.sub.P+:=c.sub.(P+1 mod 3) have been transmitted from the secret computation apparatus 21-(P+1 mod 3) at step S207 described before. The acquired value c.sub.P+ is inputted to the processing part 2122-P (step S233). The processing part 2122-P sets and outputs c.sub.P+:=c.sub.P+ (step S234). On the other hand, if x.sub.12 is false (F) (when c.sub.P+:=c.sub.P+ is not set), the processing part 2122-P sets and outputs c.sub.P+:=0 (step S235).

(73) The processing part 2123-P of the operation part 212-P performs processing according to whether x.sub.01 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F) (step S236). If x.sub.01 is true (T) (when the value according to the provided corresponding value .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B), the processing part 2122-P sets r.sub.P:=r.sub.P (step S237). Otherwise (when r.sub.P:=r.sub.P is not set), the processing part 2122-P sets r.sub.P:=0 (step S238) and outputs r.sub.P.

(74) The processing part 2124-P of the operation part 212-P performs processing according to whether x.sub.20 corresponding to the meta information A and B stored in the storage 211-P is true (T) or false (F) (step S239). If x.sub.20 is true (T) (when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B), the processing part 2124-P sets r.sub.P:=r.sub.P (step S240). Otherwise (when r.sub.P:=r.sub.P is not set), the processing part 2124-P sets r.sub.P:=0 (step S241) and outputs r.sub.P.

(75) The processing part 2125-P of the operation part 212-P performs processing according to whether C.sub.0P= is satisfied or not (step S242). If C.sub.0P= is satisfied, the processing part 2125-P obtains c.sub.0P:.sub.n{0, . . . , N-1}a.sub.0P(n)b.sub.1P(n)+c.sub.Pr.sub.P (step S243); the operation part 212-P outputs c.sub.0P (step S244); and the process proceeds to step S245. C.sub.0P= is satisfied when the value according to .sub.n{0, . . . , N-1}{a.sub.2P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.2P(n)} is not obtained from the meta information A and B and/or, C.sub.0P= is satisfied when the value according to .sub.n{0, . . . , N-1}{a.sub.0P(n)b.sub.0P(n)+a.sub.0P(n)b.sub.1P(n)+a.sub.1P(n)b.sub.0P(n)} is not obtained from the meta information A and B. On the other hand, if C.sub.0P= is not satisfied, the process proceeds to step S245 without executing steps S243 and S244.

(76) At step S245, the processing part 2126-P of the operation part 212-P performs processing according to whether C.sub.1P= is satisfied or not (S245). If C.sub.1P= is satisfied, the processing part 2126-P obtains c.sub.1P:.sub.n{0, . . . , N-1}a.sub.1P(n)b.sub.1P(n)+c.sub.P+r.sub.P (step S246), and the operation part 212-P outputs c.sub.1P (step S247). On the other hand, if C.sub.1P= is not satisfied, the process proceeds to step S248 without executing steps S246 and S247.

(77) At step 248, the operation part 212-P outputs C.sub.0P, C.sub.1P, C.sub.2P. Here, C.sub.0P, C.sub.1P, C.sub.2P are meta information about secret share values of an operation result .sub.n{0, . . . , N-1}a(n)b(n). Here, c.sub.0P and c.sub.1P are secret share values of the operation result .sub.n{0, . . . , N-1}a(n)b(n). Here, c.sub.0P is required to be outputted only in the case of C.sub.0P:=, and c.sub.1P is required to be outputted only in the case of C.sub.1P:=.

(78) <Features of the Present Embodiment>

(79) In the present embodiment, it is possible to reduce the number of times of transmission/reception of values among the secret computation apparatuses 21-P according to values indicated by meta information A and B. Further, in the case where operation of a value that is not required to be transmitted or received any more can be omitted, the amount of operation can be also reduced. Furthermore, in the case where the amount of operation using the meta information is smaller than the amount of operation using shares also, it is possible to reduce the amount of operation.

(80) [Modifications and the Like]

(81) The present invention is not limited to the above embodiments. For example, in the embodiments described above, the case of performing multiplication or product-sum operation by secret computation is illustrated. However, the present invention may be applied to any scheme if the scheme is such that values are transferred among a plurality of secret computation apparatuses, and each secret computation apparatus performs secret computation using values received from the other secret computation apparatuses. Further, each operation described above may be operation on a finite field, operation on an extension field, operation on a ring, or operation on other algebraic systems.

(82) The various processes described above are not only executed in time-series order according to the description but also may be executed in parallel or individually according to the processing capacity of an apparatus that executes the processes or as necessary. Further, instead of secret computation apparatuses transferring values via a network, transfer of values may be performed via a portable storage medium. In addition, it goes without saying that appropriate modification is possible within a range not departing from the spirit of the present invention.

(83) In the case of realizing the configuration described above by a computer, processing content of functions each apparatus should have is written by a program By executing the program on the computer, the above processing functions are realized on the computer. The program in which the processing content is written can be recorded in a computer-readable recording medium. An example of the computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory and the like.

(84) Distribution of the program is performed, for example, by sale, transfer, lending and the like of a portable recording program such as a DVD and a CD-ROM in which the program is recorded. Furthermore, a configuration is also possible in which the program is stored in a storage device of a server computer, and the program is distributed by transferring the program from the server computer to other computers via a network.

(85) For example, a computer that executes such a program first stores the program recorded in a portable recording medium or the program transferred from a server computer into its storage device once. At the time of executing a process, the computer reads the program stored in its storage device and executes the process in accordance with the read program. As another execution form of the program, the computer may read the program directly from the portable recording medium and executes the process in accordance with the program. Furthermore, it is also possible to, each time a program is transferred from the server computer to the computer, execute a process in accordance with the received program A configuration is also possible in which, without transferring the program from the server computer to the computer, the process described above is executed by a so-called ASP (Application Service Provider) type service in which processing functions are realized only by an instruction to execute the program and acquisition of a result.

(86) In the above embodiments, the processing functions of the present apparatus are realized by executing a predetermined program on a computer. However, at least a part of the processing functions may be realized by hardware.

DESCRIPTION OF REFERENCE NUMERALS

(87) 11-0 to 11-2, 21-0 to 21-2 secret computation apparatus 1, 2 secret computation system