Patent ID: 8397142
Filing Date: 2013-03-12
Classification: H04L

Abstract:
1. A secret information sharing system for splitting secret information into a plurality of secret information shares according to a (k,n)-threshold secret sharing scheme and managing the secret information shares, comprising: a shared information generating apparatus including a processor and a non-transitory computer-readable medium storing a program executable by the processor and that generates n secret information shares Vi(i=1, 2, . . . , n) from said secret information according to the (k,n)-threshold secret sharing scheme, and generates cheater identifying information Ai(i=1, 2, . . . , n), which makes it possible to detect and correct the errors according to a Reed-Solomon error-correcting process if t or less secret information shares of arbitrary k secret information shares V{i_j} (j=1, 2, . . . , k) have errors, in association with said n secret information shares Vi, using the generated n secret information shares Vi and random t-th polynomials where t represents an assumed number of cheated secret information shares which satisfies prescribed condition associated with a threshold value k; and a recovering apparatus including a processor and a non-transitory computer-readable medium storing a program executable by the processor and that performs the Reed-Solomon error-correcting process on the arbitrary k secret information shares V{i_j} (j=1, 2, . . . , k) of the secret information shares generated by said shared information generating apparatus and k cheater identifying information Ai{i_j} (j=1, 2, . . . , k) corresponding thereto, determines whether each of said secret information shares V{i_j} is a cheated secret information share or not, and recovers said secret information from the k secret information shares V{i_j} if no cheated secret information share is detected, wherein said shared information generating apparatus comprises: a secret information sharing device that is supplied with said secret information, said threshold value k, a total number n of secret information shares, and an assumed number t of cheated secret information shares, and outputs said n secret information shares Vi which allow said secret information to be uniquely recovered from said arbitrary k secret information shares; and a cheater identifying information generating device that is supplied with said n secret information shares Vi output from said secret information sharing device, generates values xi which are uniquely determined from the secret information shares Vi according to a process h which assures that h(Vi)≠h(Vj) is satisfied if Vi≠Vj where vi, vj represent arbitrary values, and outputs C(xi) (i=1, 2, . . . , n) produced by assigning the generated values xi to random t-th polynomials C, as cheater identifying information Ai corresponding to the secret information shares Vi; and wherein said recovering apparatus comprises: a cheater identifying device that detects errors according to the Reed-Solomon error-correcting process and decodes said t-th polynomials C, by using the k secret information shares V{i_j} (j=1, 2, . . . , k) of the secret information shares generated by said secret information sharing device and the k cheater identifying information Ai{i_j} (j=1, 2, . . . , k) generated by said cheater identifying information generating device and corresponding to the k secret information shares {i_j}; and a secret information recovering device that recovers said secret information by using the k secret information shares V{i_j} (j=1, 2, . . . , k) if said cheater identifying device detects no errors.