Share generating device, reconstructing device, secure computation system, share generation method, reconstruction method, program, and recording medium

A method implemented by a secure computation system that includes N share generating devices A0, . . . , AN−1, 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 and less than m, i=0, . . . , N−1 holds, j=0, . . . , N−1 holds, i(+)=i+1 mod N holds, i(−)=i−1 mod N holds, Pm(i) is a function, and a range of the function Pm(i) belongs to a set Fm(i) whose members are sequences of elements of m(i) fields F, a sum of a value which is obtained by multiplying a share [α]i in accordance with Shamir's secret sharing scheme by a Lagrange coefficient λ(i, i(−)) and a value which is obtained by multiplying a share [α]i(−) in accordance with the Shamir's secret sharing scheme by a Lagrange coefficient λ(i(−), i) is a reconstructed value α and a sum of a value which is obtained by multiplying the share [α]i by a Lagrange coefficient λ(i, i(+)) and a value which is obtained by multiplying a share [α]i(+) in accordance with the Shamir's secret sharing scheme by a Lagrange coefficient λ(i(+), i) is the reconstructed value α, a share [x]i∈Fm of plaintext x in accordance with the Shamir's secret sharing scheme is expressed by N shares [x0]i, . . . , [xN−1]i which satisfy m=m(0)+ . . . +m(N−1) and [xj]i∈Fm(j), the method comprising:

• performing, by processing circuitry of a share generating device Ai included in the N share generating devices A0, . . . , AN−1,
• storing the share [x]i of plaintext x, and each of the N share generating devices A0, . . . , AN−1 store a respective share [x]i of plaintext x, and the plaintext x cannot be reconstructed with only one share of the plaintext x,
• obtaining a function value ri=Pm(i(−))(si)∈Fm(i(−)) of an input seed si,
• obtaining a first calculated value ζi=λ(i, i(−))[xi(−)]i+ri∈Fm(i(−)) using the Lagrange coefficient λ(i, i(−)), a share [xi(−)]i, and the function value ri,
• outputting the first calculated value ζi to a share generating device Ai(−), through a network, among the N share generating devices A0, . . . , AN−1,
• accepting a second calculated value ζi(+)∈Fm(i)), from a share generating device Ai(+), through the network, among the N share generating devices A0, . . . , AN−1,
• obtaining a third calculated value zi=λ(i, i(+))[xi]i+ζi(+)∈Fm(i) using the Lagrange coefficient λ(i, i(+)), the share [xi]i, and the second calculated value ζi(+), and
• obtaining information containing the seed si and the third calculated value zi as a share SSi of the plaintext x in secret sharing and outputs the share SSi through the network, the total amount of data of the shares SS0, . . . , SSN−1 is less than N times the amount of data of the plaintext x,
• wherein the secure computation system further comprises
• a reconstructing device being configured to reconstruct the plaintext x using N shares SS0, . . . , SSN−1, wherein
• the method further comprising:
• performing, by processing circuitry of the reconstructing device
• accepting N shares SS0, . . . , SSN−1 through the network,
• obtaining a member xi=zi−Pm(i)(si(+))∈Fm(i) using the third calculated value zi∈Fm(i) contained in the share SSi and a seed si(+) contained in a share SSi(+), and
• obtaining a reconstructed value x∈Fm which is expressed by obtained members x0, . . . , xN−1.