Patent ID: 7421080
Filing Date: 2008-09-02
Classification: H04L

Abstract:
1. A shared secret reconstruction apparatus for reconstructing a secret, used for a case where n first shares are generated from original secret information, n being an integer equal to or greater than two, by using a first threshold secret sharing scheme, in which the original secret information can be reconstructed by a collection of at least any k members from a group having n members (2≦k≦n), and the n shares are distributed to the n members, t members collected from the n members separately possessing the shared secret reconstruction apparatus, t being an integer equal to or greater than k, the shared secret reconstruction apparatus thus operating together with t −1 other shared secret reconstruction apparatuses, the shared secret reconstruction apparatus comprising: a secret sharing operation unit, when t members are collected from the n members, generating second shares from a first share held by the shared secret reconstruction apparatus by using a (t, t) threshold secret sharing scheme, in which original secret information can be reconstructed by a collection of t members from the collected t members, and distributing the second shares to the t shared secret reconstruction apparatuses of the collected t members including itself; and a secret reconstruction operation unit calculating an intermediate result for reconstructing the original secret information in a distributed computation by use of the output from the secret sharing operation unit and the second shares received from the t−1 other shared secret reconstruction apparatuses and transmitting the intermediate result; wherein the secret sharing operation unit generates third shares from member ID held by the shared secret reconstruction apparatus by using a secret sharing scheme and distributes them to the t−1 other shared secret reconstruction apparatuses, the secret reconstruction operation unit thereby calculating an intermediate result for the secret reconstruction in the distributed computation by use of the second and third shares output from the secret sharing operation unit and received from the t−1 other shared secret reconstruction apparatuses; wherein the secret reconstruction operation unit comprises: a term calculation unit performing a distributed multiplication on the result of a distributed computation performed on a coefficient calculated from the third share to the second share and on this second share by use of the second and third shares output from the secret sharing operation unit and received from the t−1 other shared secret reconstruction apparatuses; and an adder summing all the outputs from the term calculation unit; and wherein the term calculation unit comprises: a difference operation unit calculating differences between the different third shares; a first multiple term distributed multiplication unit performing a distributed multiplication on the outputs from the difference operation unit; a distributed inverse element calculation unit performing a distributed computation on the inverse element of the output from the first multiple term distributed multiplication unit; a second multiple term distributed multiplication unit performing a distributed multiplication on the third shares; and a pair of two term distributed multiplication units performing a distributed multiplication on the output from the distributed inverse element calculation unit, the output from the second multiple term distributed multiplication unit and the corresponding second share.