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

A secure computation system for secure communication, 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, u=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set Fm whose members are sequences of m elements of field F,
• the secure computation system includes
• a share generating device, and
• N share converting devices A0, . . . , AN−1,
• the share generating device includes processing circuitry configured to:
• obtain N seeds s0, . . . , sN−1,
• obtain a function value y=g(x, e)∈Fm of plaintext x∈Fm and a function value e, where P(s0), . . . , P(sN−1)∈Fm are function values of the seeds s0, . . . , sN−1 and e=f(P(s0), . . . , P(sN−1))∈Fm is a function value of the function values P(s0), . . . , P(sN−1)∈Fm, and
• obtain information containing a member yi∈Fm(i) and N−1 seeds sd, where d∈{0, . . . , N−1} and d≠i, as a share SSi of the plaintext x in secret sharing and outputs the share SSi, where the function value y is expressed by members y0∈Fm(0), . . . , yN−1∈Fm(N−1) which satisfy m=m(0)+ . . . +m(N−1), and
• a share converting device Ai included in the share converting devices A0, . . . , AN−1 includes processing circuitry configured to:
• accept the share SSi,
• possess an arbitrary value tj∈Fm(i) jointly with another share converting device Ai−1 mod N,
• obtain a share [yk]u∈Fm(i) of each share converting device Au by secret-sharing the member yi in accordance with Shamir's secret sharing scheme on an assumption that the arbitrary value ti is a share [yi]i−1 mod N of the share converting device Ai−1 mod N and outputs the share [yi]u,
• accept shares [yd]i output from other share converting devices Ad,
• obtain function values P(sd)∈Fm of the seeds sd,
• a set SETi of the N−1 function values P(sd), where d∈{0, . . . , N−1} and d≠i, which is a share of the function value e=f(P(s0), . . . , P(sN−1))∈Fm with respect to the function values P(s0), . . . , P(sN−1) of the N seeds s0, . . . , sN−1, into a share [e]i of the function value e in accordance with Shamir's secret sharing scheme, and
• obtain a share [x]i of x=g−1(y, e) in accordance with Shamir's secret sharing scheme by secure computation using a share [y]i and the share [e]i, where the share [y]i which is expressed by shares [y0]i, . . . , [yN−1]j is a share of the function value y=g(x, e)∈Fm with respect to the plaintext x and the function value e,
• wherein each share SSi is a share that is transmitted respectively to each of the plurality of share converting devices Ai, and each share converting device Ai converts each respective share SSi, 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]i in accordance with Shamir's secret sharing scheme.

A share conversion method for secure communication of a share converting device Ai included in N share converting 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, i=0, . . . , N−1 holds, u=0, . . . , N−1 holds, P is a function, and a range of the function P belongs to a set Fm whose members are sequences of in elements of field F, and
• the share conversion method includes
• a first input step in which a first input unit accepts a share SSi containing N−1 seeds sd, where d∈{0, . . . , N−1} and d≠i, and a member yi∈Fm(i) belonging to a set Fm(i),
• a joint possession step in which a joint possession unit possesses an arbitrary value tj∈Fm(i) jointly with another share converting device Ai−1 mod N,
• a secret sharing step in which a secret sharing unit obtains a share [yi]u∈Fm(i) of each share converting device Au by secret-sharing the member yj in accordance with Shamir's secret sharing scheme on an assumption that the arbitrary value ti is a share [yi]i−1 mod N of the share converting device Ai−1 mod N and outputs the share [yi]u,
• a second input step in which a second input unit accepts shares [yd]i,
• an arithmetic step in which an arithmetic unit obtains function values P(sd)∈Fm of the seeds sd,
• a Shamir conversion step in which a Shamir conversion unit converts a set SETi of the N−1 function values P(sd), where d∈{0, . . . , N−1} and d≠i, which is a share of a function value e=f(P(s0), . . . , P(sN−1))∈Fm with respect to function values P(s0), . . . , P(sN−1) of N seeds s0, . . . , sN−1, into a share [e]i of the function value e in accordance with Shamir's secret sharing scheme, and
• a first share generation step in which a share [y]i which is expressed by shares [y0]i, . . . , [yN−1]i is a share of a function value y=g(x, e)∈Fm with respect to plaintext x and the function value e, and a first share generation unit obtains a share [x]i of x=g−1(y, e) in accordance with Shamir's secret sharing scheme by secure computation using the share [y]i and the share [e]i,
• wherein each share SSi is a share that is transmitted respectively to each of the plurality of share converting devices Ai, and each share converting device Ai converts each respective share SSi, 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]i in accordance with Shamir's secret sharing scheme.