Patent ID: 8077863
Filing Date: 2011-12-13
Classification: H04L

Abstract:
1. A secret sharing apparatus based on a (k,n)-threshold scheme and configured to individually distribute n (n≦k≦4) pieces of sharing information D(0), . . . , D(n−1) into which secret information S is divided, to n storage apparatuses and to restore the secret information S from any k of the n pieces of sharing information, the apparatus comprising: a generator matrix generating device configured to generate a generator matrix G of GF(2) comprising n column vectors each having a size of k(n−1) rows×(n−1) columns, any k of the n column vectors being at a full rank (the generator matrix G has a size of k(n−1) rows×n(n−1) columns and GF(2) is a finite field of order 2); a storage device configured to temporarily store the secret information S before the distribution of the sharing information D(0) to D(n−1); a divided secret data generating device configured to divide the secret information into n−1 pieces and to assign a row number j (1≦j≦n−1) varying from 1 to n−1 to a division result to generate n−1 first divided secret data K(1), . . . , K(j), . . . , K(n−1) having the same size; a random number data generating device configured to generate (k−1)(n−1) random numbers each of the same size as that of each of the divided secret data and to assign a row number h (0≦h≦k−2) and a column number g (1≦g≦n−1) to the random numbers to generate random number data U(0,1), . . . , U(h,g), . . . , U(k−1,n−1); a sharing partial data calculating device configured to calculate a product of matrixes of the divided secret data and random number data (K(1), . . . , K(j), . . . , K(n−1), U(0,1), . . . , U(h,g), . . . , U(k−2,n−1)) and the generator matrix G (the calculation is performed on GF(2)) and to assign a j×(n−1)+ith column which is a calculation result to sharing partial data D(j,i) to calculate n(n−1) sharing partial data D(j,i) (0≦j≦n−1, 0≦i≦n−2); a header information generating device configured to assign the row number j to every n−1 sharing partial data D(j,0) to D(j,n−2) having the same row number j to generate n pieces of header information H(0), . . . , H(j), . . . , H(n−1); and a sharing information distributing device configured to individually distribute n pieces of sharing information D(0), . . . , D(j), . . . , D(n−1) comprising the header information H(j) and sharing partial data D(j,0) to D(j,n−2) having the same row number j, to the n storage apparatuses.