Share generating device, share converting device, secure computation system, share generation method, share conversion method, program, and recording medium

Abstract

A share generating device obtains N seeds s.sub.0, . . . , s.sub.N−1, obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and a function value e, and obtains information containing a member y.sub.i and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs the share SS.sub.i. It is to be noted that the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1), which satisfy m=m(0)+ . . . +m(N−1).

Claims

1. A share generating device for a secure computation, wherein N is an integer greater than or equal to 2, m is an integer greater than or equal to 1, m(i) is an integer greater than or equal to 0, i=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field, the share generating device comprising: processing circuitry that: obtains N seeds s.sub.0, . . . , s.sub.N−1, obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and a function value e, where P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values of the seeds s.sub.0, . . . , s.sub.N−1 and e=f(P(s.sub.0), . . . , P(s.sub.N−1))∈F.sup.m is a function value of the function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m, and obtains information containing a member y.sub.i∈F.sup.m(i) and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs, over a network, the share SS.sub.i to a respective share converting device among a plurality of share converting devices A.sub.i (i=0, . . . , N−1), where the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) which satisfy m=m(0)+ . . . +m(N−1), wherein v is an integer greater than or equal to 1, ceil is a ceiling function, the member y.sub.i can be divided into m(i) sub-members (y.sub.i).sub.0, . . . , (y.sub.i).sub.m(i)−1∈F, m′(i) is ceil(m(i)/v), and (y′.sub.i).sub.j is ((y.sub.i).sub.vj, (y.sub.i)v.sub.j|1, . . . , (y.sub.i).sub.v(j|1)−1∈F.sup.v belonging to a set F.sup.v, the processing circuitry further obtains N arbitrary values r.sub.0, . . . , r.sub.N−1∈F.sup.v belonging to the set F.sup.v, and obtains a checksum c.sub.i=Σ.sub.0≤j<m′(i)−1{(y′.sub.i).sub.jr.sub.i.sup.j|1}+(y′.sub.i).sub.m′(i)−1r.sub.i.sup.m′(i)+1∈F.sup.v, and the share SS.sub.i, which is generated by the processing circuitry, further contains N−1 arbitrary values r.sub.d, where d∈{0, . . . , N−1} and d≠i, and a checksum c.sub.i−1 mod N, wherein each share SS.sub.i is a share that is transmitted respectively to each of the plurality of share converting devices A.sub.i, and each share converting device A.sub.i converts each respective share SS.sub.i, whose total amount of communication data is smaller than that of shares in accordance with Shamir's secret sharing scheme, into a respective share [x].sub.i in accordance with Shamir's secret sharing scheme.

2. A share generating device for a secure computation, wherein N is an integer greater than or equal to 2, m is an integer greater than or equal to 1, m(i) is an integer greater than or equal to 0, i=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field, the share generating device comprising: processing circuitry that: obtains N seeds s.sub.0, . . . , s.sub.N−1, obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and a function value e, where P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values of the seeds s.sub.0, . . . , s.sub.N−1 and e=f(P(s.sub.0), . . . , P(s.sub.N−1))∈F.sup.m is a function value of the function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m, and obtains information containing a member y.sub.i∈F.sup.m(i) and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs, over a network, the share SS.sub.i to a respective share converting device among a plurality of share converting devices A.sub.i (i=0, . . . , N−1), where the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1 ∈F.sup.m(N−1) which satisfy m=m(0)+ . . . +m(N−1), wherein each share SS.sub.i is a share that is transmitted respectively to each of the plurality of share converting devices A.sub.i, and each share converting device A.sub.i converts each respective share SS.sub.i, into a respective share [x].sub.i in accordance with Shamir's secret sharing scheme, and a total amount of data of shares SS.sub.0, . . . , SS.sub.N−1 is less than N times an amount of data of the plaintext x.

3. A share generating device for a secure computation, wherein N is an integer greater than or equal to 2, m is an integer greater than or equal to 1, m(i) is an integer greater than or equal to 0, i=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field, the share generating device comprising: processing circuitry that: obtains N seeds s.sub.0, . . . , s.sub.N−1, obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and a function value e, where P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values of the seeds s.sub.0, . . . , s.sub.N−1 and e=f(P(s.sub.0), . . . , P(s.sub.N−1))∈F.sup.m is a function value of the function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m, and obtains information containing a member y.sub.i∈F.sup.m(i) and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs, over a network, the share SS.sub.i to a respective share converting device among a plurality of share converting devices A.sub.i (i=0, . . . , N−1), where the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) which satisfy m=m(0)+ . . . +m(N−1), wherein the function value e is e=Σ.sub.0≤i<NP(s.sub.i)∈F.sup.m and the function value y is y=x−e∈F.sup.m, and each share SS.sub.i is a share that is transmitted respectively to each of the plurality of share converting devices A.sub.i, and each share converting device A.sub.i converts each respective share SS.sub.i, whose total amount of communication data is smaller than that of shares in accordance with Shamir's secret sharing scheme, into a respective share [x].sub.i in accordance with Shamir's secret sharing scheme.

4. A computer-readable recording medium that stores a program for making a computer function as the share generating device according to any one of claims 1 to 3.

5. A share generation method performed by processing circuitry of a share generating device for a secure computation, wherein N is an integer greater than or equal to 2, m is an integer greater than or equal to 1, m(i) is an integer greater than or equal to 0, i=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field F, the share generation method comprising a seed generation step in which the processing circuitry obtains N seeds s.sub.0, . . . , s.sub.N−1, an arithmetic step in which P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values of the seeds s.sub.0, . . . , s.sub.N−1, e=f(P(s.sub.0), . . . , P(s.sub.N−1))∈F.sup.m is a function value of the function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m, and the processing circuitry obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and the function value e, and a share generation step in which the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) which satisfy m=m(0)+ . . . +m(N−1), and the processing circuitry obtains information containing a member y.sub.i∈F.sup.m(i) and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs, over a network, the share SS.sub.i to a respective share converting device among a plurality of share converting devices A.sub.i (i=0, . . . , N−1), wherein v is an integer greater than or equal to 1, ceil is a ceiling function, the member y.sub.i can be divided into m(i) sub-members (y.sub.i).sub.0, . . . , (y.sub.i).sub.m(i)−1∈F, m′(i) is ceil(m(i)/v), and (y′.sub.i).sub.j is ((y.sub.i)v.sub.j, (y.sub.i).sub.vj+1, . . . , (y.sub.i).sub.v(j+1)−1)∈F.sup.v belonging to a set F.sup.v, the share generating method includes an arbitrary value generation step in which the processing circuitry obtains N arbitrary values r.sub.0, . . . , r.sub.N−1∈F.sup.v belonging to the set F.sup.v, and a checksum generation step in which the processing circuitry obtains a checksum c.sub.i=Σ.sub.0≤j<m′(i)−1{(y′.sub.i).sub.jr.sub.i.sup.j+1}+(y′.sub.i).sub.m′(i)−1r.sub.i.sup.m′(i)+1∈F.sup.v, and the share SS.sub.i, which is generated by the share generation step, further contains N−1 arbitrary values r.sub.d, where d∈{0, . . . , N−1} and d≠i, and a checksum c.sub.i−1 mod N, wherein each share SS.sub.i is a share that is transmitted respectively to each of the plurality of share converting devices A.sub.i, and each share converting device A.sub.i converts each respective share SS.sub.i, whose total amount of communication data is smaller than that of shares in accordance with Shamir's secret sharing scheme, into a respective share [x].sub.i in accordance with Shamir's secret sharing scheme.

6. A share generation method performed by a share generating device for a secure computation, wherein N is an integer greater than or equal to 2, m is an integer greater than or equal to 1, m(i) is an integer greater than or equal to 0, i=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field F, and the share generation method includes a seed generation step in which a seed generation unit obtains N seeds s.sub.0, . . . , s.sub.N−1, an arithmetic step in which P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values of the seeds s.sub.0, . . . , s.sub.N−1, e=f(P(s.sub.0), . . . , P(s.sub.N−1))∈F.sup.m is a function value of the function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m, and an arithmetic unit obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and the function value e, and a share generation step in which the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) which satisfy m=m(0)+ . . . +m(N−1), and a share generation unit obtains information containing a member y.sub.i∈F.sup.m(i) and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs, over a network, the share SS.sub.i to a respective share converting device among a plurality of share converting devices A.sub.i (i=0, . . . , N−1), wherein each share SS.sub.i is a share that is transmitted respectively to each of the plurality of share converting devices A.sub.i, and each share converting device A.sub.i converts each respective share SS.sub.i, into a respective share [x].sub.i in accordance with Shamir's secret sharing scheme, and a total amount of data of shares SS.sub.0, . . . , SS.sub.N−1 is less than N times an amount of data of the plaintext x.

7. A share generation method performed by a share generating device for a secure computation, wherein N is an integer greater than or equal to 2, m is an integer greater than or equal to 1, m(i) is an integer greater than or equal to 0, i=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field F, and the share generation method includes a seed generation step in which a seed generation unit obtains N seeds s.sub.0, . . . , s.sub.N−1, an arithmetic step in which P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values of the seeds s.sub.0, . . . , s.sub.N−1, e=f(P(s.sub.0), . . . , P(s.sub.N−1))∈F.sup.m is a function value of the function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m, and an arithmetic unit obtains a function value y=g(x, e)∈F.sup.m of plaintext x∈F.sup.m and the function value e, and a share generation step in which the function value y is expressed by members y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) which satisfy m=m(0)+ . . . +m(N−1), and a share generation unit obtains information containing a member y.sub.i∈F.sup.m(i) and N−1 seeds s.sub.d, where d∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs, over a network, the share SS.sub.i to a respective share converting device among a plurality of share converting devices A.sub.i (i=0, . . . , N−1), wherein the function value e is e=Σ.sub.0≤i<NP(s.sub.i)∈F.sup.m and the function value y is y=x−e∈F.sup.m, wherein each share SS.sub.i is a share that is transmitted respectively to each of the plurality of share converting devices A.sub.i, and each share converting device A.sub.i converts each respective share SS.sub.i, whose total amount of communication data is smaller than that of shares in accordance with Shamir's secret sharing scheme, into a respective share [x].sub.i in accordance with Shamir's secret sharing scheme.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram illustrating the configuration of a secure computation system of an embodiment.

(2) FIG. 2 is a block diagram illustrating the functional configuration of a share generating device of the embodiment.

(3) FIG. 3 is a block diagram illustrating the functional configuration of a share converting device of the embodiment.

(4) FIG. 4 is a flow diagram for explaining a share generation method of the embodiment.

(5) FIG. 5 is a flow diagram for explaining a share conversion method of the embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(6) Hereinafter, embodiments of the present invention will be described with reference to the drawings.

First Embodiment

(7) First, a first embodiment will be described.

(8) <Configuration>

(9) As illustrated in FIG. 1, a secure computation system 1 of the present embodiment includes a share generating device 11 and N share converting devices 12-A.sub.0, . . . , 12-A.sub.N−1, and these devices can communicate with one another through a network such as the Internet. It is to be noted that N is an integer greater than or equal to 2. For example, N is an integer greater than or equal to 3. One example of N is N=3. Although FIG. 1 illustrates one share generating device 11, the secure computation system 1 may include a plurality of share generating devices.

(10) As illustrated in FIG. 2, the share generating device 11 of the present embodiment includes a seed generation unit 111, an arithmetic unit 112, a division unit 113, a share generation unit 116, a communication unit 117, a storage 118, and a control unit 119 and executes each processing under control of the control unit 119. Information output from each processing unit (a part that performs processing) of the share generating device 11 is stored in the storage 118 and is read therefrom when necessary and input to another processing unit.

(11) As illustrated in FIG. 3, each share converting device 12-A.sub.i (i=0, . . . , N−1) includes a communication unit 1201-A.sub.i, a joint possession unit 1202-A.sub.i, a secret sharing unit 1203-A.sub.i, a secure computation unit 1206-A.sub.i, an arithmetic unit 1207-A.sub.i, a Shamir conversion unit 1208-A.sub.i, a share generation unit 1209-A.sub.i, a storage 1210-A.sub.i, and a control unit 1211-A.sub.i and executes each processing under control of the control unit 1211-A.sub.i. Information output from each processing unit of the share converting device 12-A.sub.i is stored in the storage 1210-A.sub.i and is read therefrom when necessary and input to another processing unit.

(12) <Share Generation Method>

(13) A share generation method which is performed by the share generating device 11 of the present embodiment will be described using FIG. 4. It is to be noted that a “share” means a fragment in secret sharing.

(14) First, the seed generation unit 111 (FIG. 2) obtains N seeds s.sub.0, . . . , s.sub.N−1 and outputs the N seeds s.sub.0, . . . , s.sub.N−1. There is no limitation on the data format of the seeds s.sub.0, . . . , s.sub.N−1, and any values can be used as the seeds s.sub.0, . . . , s.sub.N−1. One example of the seeds s.sub.0, . . . , s.sub.N−1 is elements of a set F.sup.w whose members are sequences of w elements of field F (s.sub.0, . . . , s.sub.N−1∈F.sup.w). It is to be noted that α∈β means that α is a member of β. w is an integer greater than or equal to 1. If w=1, F.sup.w is a field F. An example of the field F is a set of remainders modulo a prime number p (α mod p, where α is any number), and the operation result in the field F in this case is obtained as a remainder modulo a prime number p. p≥3 holds and, for instance, p=2.sup.61−1 holds. A seed s.sub.i (i=0, . . . , N−1) may be an arbitrary value or an output value obtained by other processing. The “arbitrary value” may be a random number (a pseudo random number or a true random number), a value selected from a plurality of preset values, or a value obtained by other processing. For example, the seed generation unit 111 generates N random numbers and outputs them as the seeds s.sub.0, . . . , s.sub.N−1 (Step S111).

(15) Plaintext x∈F.sup.m to be secret-shared and the seeds s.sub.0, . . . , s.sub.N−1 output from the seed generation unit 111 are input to the arithmetic unit 112. It is to be noted that in is an integer greater than or equal to 1. For instance, in is an integer greater than or equal to 2 or an integer greater than or equal to 3. The arithmetic unit 112 obtains a function value y=g(x, e)∈F.sup.m of the plaintext x∈F.sup.m and a function value e=f(P(s.sub.0), . . . , P(s.sub.N−1)) ∈ F.sup.m and outputs the function value y. It is to be noted that P is a function. The range of the function P belongs to a set F.sup.m whose members are sequences of m elements of field F. One example of the set F.sup.m is a set of in-dimensional vectors, whose members are in elements of field F. The domain of definition of the function P may be any domain of definition; for example, the domain of definition of the function P belongs to the set F.sup.w. For instance, w<m holds. An example of the function P is a pseudo random number generating function. P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m are function values (for example, pseudo random numbers) of the seeds s.sub.0, . . . , s.sub.N−1. g:F.sup.m×2.fwdarw.F.sup.m is a linear function (a function with linearity) that maps elements of two sets F.sup.m to elements of one set F.sup.m. For example, y=x−e∈F.sup.m holds. However, this does not limit the present invention. For instance, a value which is obtained by an operation expressed by a formula obtained by multiplying part or all of the terms of x−e by a constant may be used as y, a value which is obtained by an operation expressed by a formula obtained by replacing part or all of the terms of x−e with an inverse element may be used as y, a value which is obtained by an operation expressed by a formula obtained by replacing part or all of the terms of x−e with an inverse element and then multiplying part or all of the terms by a constant may be used as y, or a value which is obtained by an operation expressed by a formula obtained by adding a constant term to x−e may be used as y. The function value e=f(P(s.sub.0), . . . , P(s.sub.N−1)) is a function value of function values P(s.sub.0), . . . , P(s.sub.N−1)∈F.sup.m. f:F.sup.m×n.fwdarw.F.sup.m is a linear function that maps elements of n sets F.sup.m to elements of one set F.sup.m. For instance, e=f(P(s.sub.0), . . . , P(s.sub.N−1))=Σ.sub.0≤i<NP(s.sub.i)=P(s.sub.0)+ . . . +P(s.sub.N−1)∈F.sup.m holds. However, this does not limit the present invention. For example, a value which is obtained by an operation expressed by a formula obtained by multiplying part or all of the terms of P(s.sub.0)+ . . . +P(s.sub.N−1) by a constant may be used as e, a value which is obtained by an operation expressed by a formula obtained by replacing part or all of the terms of P(s.sub.0)+ . . . +P(s.sub.N−1) with an inverse element may be used as e, a value which is obtained by an operation expressed by a formula obtained by replacing part or all of the terms of P(s.sub.0)+ . . . +P(s.sub.N−1) with an inverse element and then multiplying part or all of the terms by a constant may be used as e, or a value which is obtained by an operation expressed by a formula obtained by adding a constant term to P(s.sub.0)+ . . . +P(s.sub.N−1) may be used as e (Step S112).

(16) The function value y∈F.sup.m is input to the division unit 113. The division unit 113 divides the function value y into N members y.sub.0, . . . , y.sub.N−1 and outputs the members y.sub.0, . . . , y.sub.N−1. It is to be noted that, for i=0, . . . , N−1, y.sub.i∈F.sup.m(i) holds, m(i) is an integer greater than or equal to 0 (for example, m(i) is an integer greater than or equal to 1), m≥N holds, and m=m(0)+ . . . +m(N−1) is satisfied. For instance, it is also possible to make m(0)= . . . =m(N−1)=m/N hold if m is a multiple of N. However, irrespective of whether or not in is a multiple of N, all of m(0), . . . , m(N−1) may not be identical with one another. For example, at least part of m(0), . . . , m(N−1) may be 0. It is to be noted that γ ∈F.sup.0 represents a null value. If m(i)=0, y.sub.i∈F.sup.m(i) is a null value. The function value y is expressed by members y.sub.0 ∈ F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) (for example, a sequence of y.sub.0, . . . , y.sub.N−1). For instance, the function value y is expressed as a sequence y.sub.0| . . . |y.sub.N−1 obtained by arranging y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1). If m=1, only one of m(0), . . . , m(N−1) is 1 and the others are 0. In this case, the division unit 113 does not have to divide the function value y, and outputs any one of the members y.sub.0, . . . , y.sub.N−1 as the function value y and all of the other members as null values (Step S113).

(17) The members y.sub.0, . . . , y.sub.N−1 output from the division unit 113 and the seeds s.sub.0, . . . , s.sub.N−1 output from the seed generation unit 111 are input to the share generation unit 116. The share generation unit 116 assigns a member y.sub.i and N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, to each share converting device 12-A.sub.i (i=0, . . . , N−1), and obtains information containing the member y.sub.i and the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, as a share SS.sub.i of the plaintext x in secret sharing and outputs the share SS.sub.i. It is to be noted that, if i≠0 and i≠N−1, the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, are seeds s.sub.0, . . . , s.sub.i−1, s.sub.i+1, . . . , s.sub.N−1. If i=0, the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, are seeds s.sub.1, . . . , s.sub.N−1. If i=N−1, the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, are seeds s.sub.0, . . . , s.sub.N−2. Each share SS.sub.i is a share of each share converting device 12-A.sub.i (i=0, . . . , N−1). Each share SS.sub.i may contain other information, but does not contain a member y.sub.d, where d ∈{0, . . . , N−1} and d≠i, and a seed s.sub.i. It is to be noted that information containing the member y.sub.i∈F.sup.0, which is a null value, and the N−1 seeds s.sub.d means information indicating that the member y.sub.i is a null value and containing the N−1 seeds s.sub.d. The information containing the member y.sub.i∈F.sup.0, which is a null value, and the N−1 seeds s.sub.d contains the N−1 seeds s.sub.d, but does not actually contain the member y.sub.i. The size of the seeds s.sub.1, . . . , s.sub.N−1 and N do not depend on m. In (2, N)-Shamir's secret sharing, the order of magnitude of the total share size that relates to the data size in of the plaintext x is O(Nm); in the present embodiment, the order of magnitude of the total share size that relates to the data size in of the plaintext x is just O(m). The size of each share is O(m/N). For example, the total amount of data of shares SS.sub.0, . . . , SS.sub.N−1 is less than N times the amount of data of the plaintext x. For instance, the amount of data of each share SS.sub.i is smaller than the amount of data of the plaintext x (Step S116).

(18) Each share SS.sub.i output from the share generation unit 116 is input to the communication unit 117. The communication unit 117 outputs each share SS.sub.i to each share converting device 12-A, (i=0, . . . , N−1). Each output share SS.sub.i is transmitted to each share converting device 12-A, through the network. That is, the share SS.sub.0 is transmitted to the share converting device 12-A.sub.0, the share SS.sub.1 is transmitted to the share converting device 12-A.sub.1, . . . , and the share SS.sub.N−1 is transmitted to the share converting device 12-A.sub.N−1 (Step S117).

(19) <Share Conversion Method>

(20) A share conversion method which is performed by each share converting device 12-A.sub.i of the present embodiment will be described using FIG. 5.

(21) The share SS.sub.i output from the share generating device 11 and containing the member y.sub.i and the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, is received (accepted) by the communication unit 1201-A.sub.1 (a first input unit) of the share converting device 12-A.sub.i (FIG. 3). The received share SS.sub.i is stored in the storage 1210-A.sub.i (Step S1201-A.sub.i).

(22) The joint possession unit 1202-A.sub.i possesses an arbitrary value t.sub.i∈ F.sup.m(i) jointly with a joint possession unit 1202-A.sub.1−1 mod N of another share converting device 12-A.sub.i−1 mod N. That is, the joint possession unit 1202-A.sub.i and the joint possession unit 1202-A.sub.i−1 mod N obtain the same arbitrary value t.sub.i. The joint possession unit 1202-A.sub.i and the joint possession unit 1202-A.sub.i−1 mod N may jointly possess the arbitrary value t.sub.i by transmitting the arbitrary value t.sub.i or information for identification of the arbitrary value t.sub.i to the joint possession unit 1202-A.sub.i−1 mod N from the joint possession unit 1202-A.sub.i, the joint possession unit 1202-A.sub.i and the joint possession unit 1202-A.sub.i−1 mod N may jointly possess the arbitrary value t.sub.i by transmitting the arbitrary value t.sub.1 or information for identification of the arbitrary value t.sub.i to the joint possession unit 1202-A.sub.i from the joint possession unit 1202-A.sub.i−1 mod N, or joint possession of the arbitrary value t.sub.i may be achieved as a result of the joint possession unit 1202-A.sub.i and the joint possession unit 1202-A.sub.i−1 mod N jointly possessing a common seed value and executing the same processing using the common seed value. The arbitrary value t.sub.i may be a random number (a pseudo random number or a true random number), a value obtained by other processing, or a value selected from a plurality of predetermined values. Joint possession of the arbitrary value t.sub.i∈F.sup.m(i) may be performed when Step S1201-A.sub.i is executed, in response to a request from the other joint possession unit 1202-A.sub.i−1 mod N, or in response to other events, or may be performed in advance. The joint possession unit 1202-A.sub.i outputs the obtained arbitrary value t.sub.i. If the member y.sub.i is a null value, the arbitrary value t.sub.i is also set at a null value (Step S1202-A.sub.i).

(23) The member y.sub.i contained in the share SS.sub.i and the arbitrary value t.sub.i output from the joint possession unit 1202-A.sub.i are input to the secret sharing unit 1203-A.sub.i. The secret sharing unit 1203-A.sub.i obtains a share [y.sub.i].sub.u∈F.sup.m(i) (a Shamir share) of each share converting device 12-A.sub.u (u=0, . . . , N−1) by secret-sharing the member y.sub.i in accordance with Shamir's secret sharing scheme and outputs the share [y.sub.i].sub.u. It is to be noted that the arbitrary value t.sub.i is assumed to be a share [y.sub.i].sub.i−1 mod N of the share converting device 12-A.sub.i−1 mod N. Shamir's secret sharing scheme of the embodiment is a 2-out-of-N threshold sharing scheme, in which, given any two different shares, plaintext can be reconstructed; however, given any one piece of share information, information on the plaintext cannot be obtained at all. In the 2-out-of-N threshold sharing scheme, if the secret-shared member y.sub.i and one share [y.sub.i].sub.i−1 mod N=t.sub.i are determined, another share can be obtained. For instance, on the assumption that the arbitrary value t.sub.i is the share [y.sub.i].sub.i−1 mod N of the share converting device 12-A.sub.i−1 mod N, the secret sharing unit 1203-A.sub.i identifies an equation (for example, identifies a coefficient of each term of the equation) which holds between the member y.sub.i, the share [y.sub.i].sub.i−1 mod N=t.sub.i, and another share [y.sub.i].sub.u′∈F.sup.m(i) (u′ ∈{0, . . . , N−1} and u′≠i−1 mod N) using Lagrange's interpolation formula and generates the other share [y.sub.i].sub.u′ ∈F.sup.m(i) by solving the equation. The communication unit 1201-A.sub.i (a first output unit) outputs (transmits) shares [y.sub.i].sub.d obtained in the secret sharing unit 1203-A.sub.i to the other N−1 share converting devices 12-A.sub.d (d ∈ {0, . . . , N−1} and d≠i). Since the share converting device 12-A.sub.i and the share converting device 12-A.sub.i−1 mod N already jointly possess the share [y.sub.i].sub.i−1 mod N=t.sub.i (Step S1202-A.sub.i), further transmission of the share [y.sub.i].sub.i−1 mod N=t.sub.i to the share converting device 12-A.sub.i−1 mod N may be omitted. If the member y.sub.i is a null value, the share [y.sub.i].sub.u is also set at a null value. The communication unit 1201-A.sub.i (a second input unit) receives (accepts) shares [y.sub.d].sub.i output (transmitted) from the other share converting devices 12-A.sub.d in a similar manner (Step S1203-A.sub.i).

(24) The share [y.sub.i].sub.i of the share converting device 12-A.sub.i, which has been output from the secret sharing unit 1203-A.sub.i, and the shares [y.sub.d].sub.i transmitted from the other share converting devices 12-A.sub.d (d ∈{0, . . . , N−1} and d≠i) are input to the secure computation unit 1206-A.sub.i (a first secure computation unit). The secure computation unit 1206-A.sub.i obtains a share [y].sub.i∈F.sup.m by joining (concatenating) shares [y.sub.0].sub.i, . . . , [y.sub.N−1].sub.i to one another by publicly known secure computation and outputs the share [y].sub.i. The share [y].sub.i is a share of the function value y in accordance with Shamir's secret sharing scheme. The function value y is what is obtained by joining the N members y.sub.0, . . . , y.sub.N−1. For example, a sequence y.sub.0| . . . |y.sub.N−1 obtained by arranging y.sub.0∈F.sup.m(0), . . . , y.sub.N−1∈F.sup.m(N−1) is y. To obtain the share [y].sub.i∈F.sup.m by joining the shares [y.sub.0].sub.i, . . . , [y.sub.N−1].sub.i in accordance with Shamir's secret sharing scheme by secure computation, it is only necessary to use, for instance, a sequence of the shares [y.sub.0].sub.i, . . . , [y.sub.N−1].sub.i as a share [y]. That is, the share [y] is expressed by shares [y.sub.0].sub.i∈F.sup.m(0), . . . , [y.sub.N−1].sub.i∈F.sup.m(N−1). For example, a sequence [y.sub.0].sub.i| . . . |[y.sub.N−1].sub.i obtained by arranging the shares [y.sub.0].sub.i, . . . , is the share [y] (Step S1206-A.sub.i).

(25) The N−1 seeds s.sub.d contained in the share SS.sub.i are input to the arithmetic unit 1207-A.sub.i. The arithmetic unit 1207-A.sub.i obtains N−1 function values P(s.sub.d) ∈F.sup.m (for example, pseudo random numbers) of the N−1 seeds s.sub.d and outputs the N−1 function values P(s.sub.d) (d ∈{0, . . . , N−1} and d≠i). The function P which is used for this operation is the same as the function P for obtaining the function value y in the arithmetic unit 112 of the share generating device 11. A set SET.sub.i of the N−1 function values P(s.sub.d), where d ∈{0, . . . , N−1} and d≠i (that is, the set SET.sub.i has the N−1 function values P(s.sub.d), where d ∈{0, . . . , N−1} and d≠i, as members thereof), is a share of the function value e=f(P(s.sub.0), . . . , P(s.sub.N−1)) ∈F.sup.m with respect to function values P(s.sub.0), . . . , P(s.sub.N−1) of the N seeds s.sub.0, . . . , s.sub.N−1. That is, if there are at least two different sets, sets SET.sub.i′ and SET.sub.i″ (i′, i″ ∈{0, . . . , N−1} and i′≠i″), the function value e=f(P(s.sub.0), . . . , P(s.sub.N−1)) can be reconstructed. In other words, the set SET.sub.i is a (2, N)-replication secret sharing share of the function value e (Step S1207-A.sub.i).

(26) The set SET.sub.i of the N−1 function values P(s.sub.d), where d ∈{0, . . . , N−1} and d≠i, is input to the Shamir conversion unit 1208-A.sub.i. The Shamir conversion unit 1208-A.sub.i converts the set SET which is the (2, N)-replication secret sharing share of the function value e, into a share [e].sub.i of the function value e in accordance with Shamir's secret sharing scheme by a publicly known Shamir conversion method and outputs the share [e].sub.i. Examples of a method of converting a (2, N)-replication secret sharing share into a share in accordance with Shamir's secret sharing scheme include a method described in “Ronald Cramer, Ivan Damgard, Yuval Ishai: Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. TCC 2005: 342-362” (Reference Literature 1) (Step S1208-A.sub.i).

(27) The share [y].sub.i output from the secure computation unit 1206-A.sub.i and the share [e].sub.i output from the Shamir conversion unit 1208-A.sub.i are input to the share generation unit 1209-A.sub.i (a first share generation unit). As described earlier, the share [y].sub.i is a share of the function value y=g(x, e) ∈ F.sup.m with respect to the plaintext x and the function value e in accordance with Shamir's secret sharing scheme. Here, a function that satisfies x=g.sup.−1(y, e) ∈F.sup.m with respect to y=g(x, e) is defined as g.sup.−1:F.sup.m×2.fwdarw.F.sup.m. For example, if y=x−e, x=y+e holds. The share generation unit 1209-A.sub.i obtains a share [x].sub.i∈F.sup.m of x=g.sup.−1(y, e) in accordance with Shamir's secret sharing scheme by secure computation using the share [y].sub.i and the share [e].sub.i and outputs the share [x].sub.i. For instance, if x=y+e, the share generation unit 1209-A.sub.i obtains a share [y+e].sub.i by secure computation using the share [y].sub.i and the share [e].sub.i and outputs the share [y+e].sub.i. Secure computation using shares in accordance with Shamir's secret sharing scheme is described in, for example, “Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10” (Reference Literature 2) (Step S1209-A.sub.i).

Features of the Present Embodiment

(28) The share generating device 11 outputs information containing the member y.sub.i∈F.sup.m(i) and the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, to each share converting device 12-A.sub.i as the share SS.sub.i. This makes it possible to make the total amount of communication data smaller than that of shares in accordance with Shamir's secret sharing scheme. Each share converting device 12-A.sub.i can convert the share SS.sub.i into the share [x].sub.i in accordance with Shamir's secret sharing scheme. This makes it possible to perform secure computation.

Second Embodiment

(29) A second embodiment is a modification of the first embodiment. In the present embodiment, a checksum corresponding to a share is generated at the time of generation of a share and the share is verified using the checksum at the time of share conversion. In the following description, an explanation of a matter that has already been described in the first embodiment is sometimes simplified, using the same reference character as that of the first embodiment.

(30) <Configuration>

(31) As illustrated in FIG. 1, a secure computation system 2 of the present embodiment includes a share generating device 21 and N share converting devices 22-A.sub.0, . . . , 22-A.sub.N−1, and these devices can communicate with one another through a network such as the Internet. Although FIG. 1 illustrates one share generating device 21, the secure computation system 2 may include a plurality of share generating devices.

(32) As illustrated in FIG. 2, the share generating device 21 of the present embodiment includes a seed generation unit 111, an arithmetic unit 112, a division unit 113, an arbitrary value generation unit 214, a checksum generation unit 215, a share generation unit 216, a communication unit 117, a storage 118, and a control unit 119 and executes each processing under control of the control unit 119. Information output from each processing unit is stored in the storage 118 and is read therefrom when necessary and input to another processing unit.

(33) As illustrated in FIG. 3, each share converting device 22-A.sub.i (i=0, . . . , N−1) includes a communication unit 1201-A.sub.i, a joint possession unit 1202-A.sub.i, a secret sharing unit 1203-A.sub.i, a share generation unit 2204-A.sub.i, a verification unit 2205-A.sub.i, a secure computation unit 1206-A.sub.i, an arithmetic unit 1207-A.sub.i, a Shamir conversion unit 1208-A.sub.i, a share generation unit 1209-A.sub.i, a storage 1210-A.sub.i, and a control unit 1211-A.sub.i and executes each processing under control of the control unit 1211-A.sub.i. Information output from each processing unit is stored in the storage 1210-A.sub.i and is read therefrom when necessary and input to another processing unit.

(34) <Share Generation Method>

(35) A share generation method which is performed by the share generating device 21 will be described using FIG. 4. First, in place of the share generating device 11, the share generating device 21 executes the processing from Steps S111 to S113 described in the first embodiment.

(36) Next, the arbitrary value generation unit 214 obtains N arbitrary values r.sub.0, . . . , r.sub.N−1∈F.sup.v belonging to a set F.sup.v and outputs the arbitrary values r.sub.0, . . . , r.sub.N−1. It is to be noted that v is an integer greater than or equal to 1. A greater data amount reduction effect can be achieved if v is less than or equal to m (for instance, v is less than m). For example, v=1 holds. One example of the set F.sup.v is an extension field whose basic field is a field F and whose degree of a field extension is v. The “arbitrary value” may be a random number (a pseudo random number or a true random number) or a value selected from a plurality of preset values. For instance, the arbitrary value generation unit 214 generates N random numbers and outputs them as the arbitrary values r.sub.0, . . . , r.sub.N−1 (Step S214).

(37) The members y.sub.0, . . . , y.sub.N−1 output from the division unit 113 and the arbitrary values r.sub.0, . . . , r.sub.N−1 output from the arbitrary value generation unit 214 are input to the checksum generation unit 215. Here, each member y.sub.i ∈F.sup.m(i) can be divided into m(i) sub-members (y.sub.i).sub.0, . . . , (y.sub.i).sub.m(i)−1∈F. For example, each member y.sub.i is expressed as a sequence (y.sub.i).sub.0| . . . |(y.sub.i).sub.m(i)−1 obtained by arranging the sub-members (y.sub.i).sub.0, . . . , (y.sub.i).sub.m(i)−1. Moreover, m′(i) is ceil(m(i)/v) and (y′.sub.i).sub.j is ((y.sub.i).sub.vj, (y.sub.i).sub.vj+1, . . . , (y.sub.i).sub.v(j+1)−1) ∈F.sup.v belonging to the set F.sup.v. It is to be noted that ceil is a ceiling function and m′(i) is ceil(m(i)/v) (that is, m′(i) is the smallest integer which is greater than or equal to m(i)/v). Furthermore, for j=m′(i)−1, if the number of (y′.sub.i).sub.v(m′(i)−1), (y.sub.i).sub.v(m′(i)−1)+1, . . . , (y.sub.i).sub.vm′(i)−1 is less than v, it is assumed that (y′.sub.i).sub.m′(i)−1=((y.sub.i).sub.v(m′(i)−1), (y.sub.i).sub.v(m′(i)−1)+1, . . . , (y.sub.i).sub.m(i)−1, 0, . . . , 0) ∈F.sup.v holds. The checksum generation unit 215 obtains a checksum c.sub.i=Σ.sub.0≤j<m′(i)−1{(y′.sub.i).sub.jr.sub.i.sup.j+1}+(y′.sub.i).sub.m′(i)−1r.sub.i.sup.m′(i)+1 ∈F.sup.v corresponding to each share SS.sub.i using the members y.sub.0, . . . , y.sub.N−1 and the arbitrary values r.sub.0, . . . , r.sub.N−1 and outputs the checksum c.sub.i (Step S215).

(38) The members y.sub.0, . . . , y.sub.N−1 output from the division unit 113, the seeds s.sub.0, . . . , s.sub.N−1 output from the seed generation unit 111, the arbitrary values r.sub.0, . . . , r.sub.N−1 output from the arbitrary value generation unit 214, and the checksums c.sub.0, . . . , c.sub.N−1 output from the checksum generation unit 215 are input to the share generation unit 216. The share generation unit 216 assigns a member y.sub.i, N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, N−1 arbitrary values r.sub.d, where d ∈{0, . . . , N−1} and d≠i, and a checksum c.sub.i−1 mod N to each share converting device 22-A.sub.i (i=0, . . . , N−1), and obtains information containing the member y.sub.i, the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, the N−1 arbitrary values r.sub.d, where d ∈{0, . . . , N−1} and d≠i, and the checksum c.sub.i−1 mod N as a share SS.sub.i of the plaintext x in secret sharing and outputs the share SS.sub.i. Each share SS.sub.i is a share of each share converting device 22-A.sub.i (i=0, . . . , N−1). Each share SS.sub.i may contain other information, but does not contain a member y.sub.d, where d ∈{0, . . . , N−1} and d≠i, a seed s.sub.i, an arbitrary value r.sub.i, and checksums of c.sub.0, . . . , c.sub.N−1 other than c.sub.i−1 mod N. The size of the seeds s.sub.1, . . . , s.sub.N−1, N, and v do not depend on m. In (2, N)-Shamir's secret sharing, the order of magnitude of the total share size that relates to the data size m of the plaintext x is O(Nm); in the present embodiment, the order of magnitude of the total share size that relates to the data size in of the plaintext x is just O(m). The size of each share is O(m/N). For example, the total amount of data of shares SS.sub.0, . . . , SS.sub.N−1 is less than N times the amount of data of the plaintext x. For instance, the amount of data of each share SS.sub.i is smaller than the amount of data of the plaintext x (Step S216).

(39) Each share SS.sub.i obtained in the share generation unit 216 is input to the communication unit 117. The communication unit 117 outputs each share SS.sub.i to each share converting device 22-A.sub.i (i=0, . . . , N−1). Each output share SS.sub.i is transmitted to each share converting device 22-A.sub.i through the network. That is, the share SS.sub.0 is transmitted to the share converting device 22-A.sub.0, the share SS.sub.i is transmitted to the share converting device 22-A.sub.1, . . . , and the share SS.sub.N−1 is transmitted to the share converting device 22-A.sub.N−1 (Step S217).

(40) <Share Conversion Method>

(41) A share generation method which is performed by each share converting device 22-A.sub.i of the present embodiment will be described using FIG. 5.

(42) The share SS.sub.i output from the share generating device 21 and containing the member y.sub.i, the N−1 seeds s.sub.d, where d ∈{0, . . . , N−1} and d≠i, the N−1 arbitrary values r.sub.d, where d ∈{0, . . . , N−1} and d≠i, and the checksum c.sub.i−1 mod N is received (accepted) by the communication unit 1201-A.sub.i (the first input unit) of the share converting device 22-A.sub.i (FIG. 3). The received share SS.sub.i is stored in the storage 1210-A.sub.i (Step S2201-A.sub.i).

(43) Next, in place of each share converting device 12-A.sub.i, each share converting device 22-A.sub.i executes the processing in Steps S1202-A.sub.i and S1203-A.sub.i described in the first embodiment.

(44) The arbitrary values r.sub.d contained in the share SS.sub.i and the shares [y.sub.d].sub.i (d ∈{0, . . . , N−1} and d≠i) received by the communication unit 1201-A.sub.i (Step S1203-A.sub.i) are input to the share generation unit 2204-A.sub.i (a second share generation unit). The share generation unit 2204-A.sub.i obtains a share [c.sub.d].sub.i of a checksum c.sub.d=Σ.sub.0≤j<m′(d)−1 {(y′.sub.d).sub.jr.sub.d.sup.j+1}+(y′.sub.d).sub.m′(d)−1r.sub.d.sup.m′(d)+1∈F.sup.v in accordance with Shamir's secret sharing scheme by secure computation (public value multiplication and addition by secure computation) using the arbitrary values r.sub.d and the shares [y.sub.d].sub.i and outputs the share [c.sub.d].sub.i. As described earlier, the member y.sub.d can be divided into m(d) sub-members (y.sub.d).sub.0, . . . , (y.sub.i).sub.m(d)−1. (y′.sub.d).sub.j is ((y.sub.d).sub.vj, (y.sub.d).sub.vj+1, . . . , (y.sub.d).sub.v(j+1)−1)∈F.sup.v belonging to the set F.sup.v, and m′(d) is ceil(m(d)/v). Moreover, for j=m′(i)−1, if the number of (y.sub.d).sub.v(m′(d)−1), (y.sub.d).sub.v(m′(d)−1)+1, . . . , (y.sub.d).sub.vm′(d)−1 is less than v, it is assumed that (y′.sub.d).sub.m′(d)−1=((y.sub.d).sub.v(m′(d)−1), (y.sub.d).sub.v(m′(d)−1)+1, . . . , (y.sub.d).sub.m(d)−1, 0, . . . , 0) ∈ F.sup.v. A method of performing public value multiplication and addition by secure computation using shares in accordance with Shamir's secret sharing scheme is described in, for example, Reference Literature 2 (Lemma on page 3) (Step S2204-A.sub.i).

(45) The share [c.sub.d].sub.i is input to the communication unit 1201-A.sub.i. The communication unit 1201-A.sub.i (a second output unit) outputs the share [c.sub.d].sub.i (d ∈{0, . . . , N−1} and d≠i) to another share converting device 22-A.sub.d+1 mod N. The output share [c.sub.d].sub.i is transmitted to the share converting device 22-A.sub.d+1 mod N via the network, received by a communication unit 1201-A.sub.d+1 mod N of the share converting device 22-A.sub.d+1 mod N, and stored in a storage 1210-A.sub.d+1 mod N. The share [c.sub.d].sub.i, a share [c.sub.d].sub.d+1 mod N generated by a share generation unit 2204-A.sub.d+1 mod N, and the checksum c.sub.d contained in a share SS.sub.d+1 mod N are input to a verification unit 2205-A.sub.d+1 mod N. The verification unit 2205-A.sub.d+1 mod N verifies whether the checksum c.sub.d and the share [c.sub.d].sub.i have a right relationship. The verification unit 2205-A.sub.d+1 mod N of the present embodiment verifies whether the checksum c.sub.d and N shares [c.sub.d].sub.0, . . . , [c.sub.d].sub.N−1 have a right relationship. For instance, the verification unit 2205-A.sub.d+1 mod N verifies whether or not there is consistency among the input N shares [c.sub.d].sub.0, . . . , [c.sub.d].sub.N−1 (Verification 1: consistency verification) and verifies whether a value reconstructed from any two shares [c.sub.d].sub.i′ and [c.sub.d].sub.i″ (i′, i″ ∈ {0, . . . , N−1} and i′≠i″) of the input N shares [c.sub.d].sub.0, . . . , [c.sub.d].sub.N−1 (Shamir's secret sharing scheme of the embodiment is a 2-out-of-N threshold sharing scheme) and the checksum c.sub.d are identical with each other (Verification 2: identicalness verification). Consistency verification is, for example, calculating another share [c.sub.d].sub.i′″ (i′″ ∈{0, . . . , N−1}, i′″≠i″, and i′″≠i′) from any two shares [c.sub.d].sub.i′ and [c.sub.d].sub.i″ using Lagrange's interpolation formula and, by using the result of calculation as [b.sub.d].sub.i′″, verifying whether [b.sub.d].sub.i′″ and [c.sub.d].sub.i′″ in the N shares [c.sub.d].sub.0, . . . , [c.sub.d].sub.N−1 input to the verification unit 2205-A.sub.d+1 mod N are identical with each other. Consistency is verified by consistency verification if [b.sub.d].sub.i′″=[c.sub.d].sub.i′″ holds for all i′″, otherwise consistency is not verified by consistency verification. Moreover, in identicalness verification, identicalness is verified by identicalness verification if the value reconstructed from the two shares [c.sub.d].sub.i′ and [c.sub.d].sub.i″ and the checksum c.sub.d are identical with each other, otherwise identicalness is not verified by identicalness verification. A right relationship is verified if consistency is verified by consistency verification and identicalness is verified by identicalness verification, otherwise a right relationship is not verified.

(46) Likewise, a share [c.sub.i−1 mod N].sub.d output from another share converting device 22-A.sub.d is received (accepted) by the communication unit 1201-A.sub.i (the second input unit) and stored in the storage 1210-A.sub.i. The share [c.sub.i−1 mod N].sub.d output from the other share converting device 22-A.sub.d, a share [c.sub.i−1 mod N].sub.i generated by the share generation unit 2204-A.sub.i, and the checksum c.sub.i−1 mod N contained in the share SS.sub.i are input to the verification unit 2205-A.sub.i. The verification unit 2205-A.sub.i verifies whether the checksum c.sub.i−1 mod N and the share [c.sub.i−1 mod N].sub.d have a right relationship. The verification unit 2205-A.sub.i of the present embodiment verifies whether the input checksum c.sub.i−1 mod N, share [c.sub.i−1 mod N].sub.d, and share [c.sub.i−1 mod N].sub.i have a right relationship. For example, the verification unit 2205-A.sub.i verifies whether or not there is consistency among the input N shares [c.sub.i−1 mod N].sub.0, . . . , [c.sub.i−1 mod N].sub.N−1 (Verification 1: consistency verification) and verifies whether a value reconstructed from any two shares [c.sub.i−1 mod N].sub.i′ and [c.sub.i−1 mod N].sub.i″ (i′, i″ ∈{0, . . . , N−1} and i′≠i″) of the input N shares [c.sub.i−1 mod N].sub.0, . . . , [c.sub.i−1 mod N].sub.N−1 is identical with the checksum c.sub.i−1 mod N (Verification 2: identicalness verification). Consistency verification is, for example, calculating another share [c.sub.i−1 mod N].sub.i′″ (i′″ ∈{0, . . . , N−1}, i′″≠i″, and i′″≠i′) from any two shares [c.sub.i−1 mod N].sub.i′ and [c.sub.i−1 mod N].sub.i″ using Lagrange's interpolation formula and, by using the result of calculation as [b.sub.i−1 mod N].sub.i′″, verifying whether [b.sub.i−1 mod N].sub.i′″ and [c.sub.i−1 mod N].sub.i′″ in the N shares [c.sub.i−1 mod N].sub.0, . . . , [c.sub.i−1 mod N].sub.N−1 input to the verification unit 2205-A.sub.i are identical with each other. Consistency is verified by consistency verification if [b.sub.i−1 mod N].sub.i′″=[c.sub.i−1 mod N].sub.i′″ holds for all i′″, otherwise consistency is not verified by consistency verification. Moreover, in identicalness verification, identicalness is verified by identicalness verification if the value reconstructed from the two shares [c.sub.i−1 mod N].sub.i′ and [c.sub.i−1 mod N].sub.i″ and the checksum c.sub.i−1 mod N are identical with each other, otherwise identicalness is not verified by identicalness verification. A right relationship is verified if consistency is verified by consistency verification and identicalness is verified by identicalness verification, otherwise a right relationship is not verified (Step S2205-A.sub.i).

(47) If the verification unit 2205-A.sub.i determines that a right relationship is verified, in place of each share converting device 12-A.sub.i, each share converting device 22-A.sub.i executes the processing from Steps S1206-A.sub.i to S1209-A.sub.i described in the first embodiment and ends the processing. On the other hand, if the verification unit 2205-A.sub.i determines that a right relationship is not verified, the control unit 1211-A.sub.i makes the processing terminate with an error message (Step S2206-A.sub.i).

Features of the Present Embodiment

(48) Also in the present embodiment, it is possible to make the total amount of communication data smaller than that of shares in accordance with Shamir's secret sharing scheme. Moreover, each share converting device 22-A.sub.i can convert the share SS.sub.i into the share [x].sub.i in accordance with Shamir's secret sharing scheme. Furthermore, in the present embodiment, since the share SS.sub.i contains a checksum and verification processing is performed at the time of share conversion, it is possible to detect unauthorized processing performed in the share generating device 21 and/or the share converting device 22-A.sub.i.

(49) It is to be noted that the present invention is not limited to the foregoing embodiments. For example, the above-described various kinds of processing may be executed, in addition to being executed in chronological order in accordance with the descriptions, in parallel or individually depending on the processing power of a device that executes the processing or when necessary. In addition, it goes without saying that changes may be made as appropriate without departing from the spirit of the present invention. Moreover, the share generating device and/or the share converting device may be part of a secure computation device that performs secure computation or may be a device that is different from the secure computation device.

(50) The above-described each device is embodied by execution of a predetermined program by a general- or special-purpose computer having a processor (hardware processor) such as a central processing unit (CPU), memories such as random-access memory (RAM) and read-only memory (ROM), and the like, for example. The computer may have one processor and one memory or have multiple processors and memories. The program may be installed on the computer or pre-recorded on the ROM and the like. Also, some or all of the processing units may be embodied using an electronic circuit that implements processing functions without using programs, rather than an electronic circuit (circuitry) that implements functional components by loading of programs like a CPU. An electronic circuit constituting a single device may include multiple CPUs.

(51) When the above-described configurations are implemented by a computer, the processing details of the functions supposed to be provided in each device are described by a program. As a result of this program being executed by the computer, the above-described processing functions are implemented on the computer. The program describing the processing details can be recorded on 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 include a magnetic recording device, an optical disk, a magneto-optical recording medium, and semiconductor memory.

(52) The distribution of this program is performed by, for example, selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM on which the program is recorded. Furthermore, a configuration may be adopted in which this program is distributed by storing the program in a storage device of a server computer and transferring the program to other computers from the server computer via a network.

(53) The computer that executes such a program first, for example, temporarily stores the program recorded on the portable recording medium or the program transferred from the server computer in a storage device thereof. At the time of execution of processing, the computer reads the program stored in the storage device thereof and executes the processing in accordance with the read program. As another mode of execution of this program, the computer may read the program directly from the portable recording medium and execute the processing in accordance with the program and, furthermore, every time the program is transferred to the computer from the server computer, the computer may sequentially execute the processing in accordance with the received program. A configuration may be adopted in which the transfer of a program to the computer from the server computer is not performed and the above-described processing is executed by so-called application service provider (ASP)-type service by which the processing functions are implemented only by an instruction for execution thereof and result acquisition.

(54) Instead of executing a predetermined program on the computer to implement the processing functions of the present devices, at least some of the processing functions may be implemented by hardware.

(55) The inventions of the “share generation method” and the “share conversion method” fall under the category of “the invention of a process for producing a product” under Article 2, paragraph (3), item (iii) of the Patent Act. Moreover, shares which are obtained by the “share generation method” and the “share conversion method” fall under the category of a “computer program, etc.” under Article 2, paragraph (4) of the Patent Act. For example, a header, an extension, or the like is added to such shares for subsequent processing, and a computer that processes these shares executes processing using each share while referring to the header, the extension, or the like added to the share.

DESCRIPTION OF REFERENCE NUMERALS

(56) 1, 2 secure computation system 11, 21 share generating device 12-A.sub.i, 22-A.sub.i share converting device