SECRET SHARING APPARATUS, METHOD, AND PROGRAM
First Claim
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.
5 Assignments
0 Petitions
Accused Products
Abstract
A secret sharing apparatus according to the present invention is based on a (k,n)-threshold scheme with a threshold of at least 4. The secret sharing apparatus generates a generator matrix (G) of GF(2) in which any k of n column vectors are at a full rank, divides secret information into n−1 pieces to generate divided secret data (K(1), . . . , K(n−1)), generates random data (U(0,1), . . . , U(k−2,n−1)), calculates the product of matrixes of the divided secret data, the random data, and the generator matrix (G), assigns the j×(n−1)+ith column of the calculation result to sharing partial data (D(j,i)) to calculate sharing partial data (D(j,1)), generates header information (H(j)), and individually distributes n pieces of sharing information (D(0), . . . , D(n−1)) made up of the header information (H(j)) and sharing partial data (D(j,i)) to n storage apparatuses.
-
Citations
9 Claims
-
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); anda 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. - View Dependent Claims (2, 3)
- k≧
-
4. 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 random number data and the divided secret data (U(0,1), . . . , U(h,g), . . . , U(k−
2,n−
1), K(1), . . . , K(j), . . . , K(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); anda 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. - View Dependent Claims (5)
- k≧
-
6. 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 storage device configured to temporarily store the secret information S before the distribution of the sharing information D(0) to D(n−
1);a first 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 second divided secret data generating device configured to create a zero value of the same size as that of each of the divided secret data and to assign the row number j=0 to a creation result to generate second divided secret data K(0); a first random number data generating device configured to create k−
1 zero value data each of the same size as that of each divided secret data and to assign a row number h (0≦
h≦
k−
2) and a column number g=0 to the zero value data to generate random number data U(0,0), . . . , U(h,
0), . . . , U(k−
2,0);a second random number data generating device configured to generate k−
1 random numbers each of the same size as that of each divided secret data and to assign the row number h (0≦
h≦
k−
2) and the column number g (1≦
g≦
n−
1) to the random numbers to generate random number data U(0,1), . . . , U(h, g), . . . , U(k−
2,n−
1);a random number data calculating device configured to calculate n(n−
1) random number data 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 program comprising;a first program code allowing a computer to sequentially execute a process of generating 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 second program code allowing the computer to execute a process of temporarily writing the secret information S to a memory in the computer before the distribution of the sharing information D(0) to D(n−
1);a third program code allowing the computer to sequentially execute a process of dividing the secret information in the memory 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 divided secret data K(1), . . . , K(j), . . . , K(n−
1) having the same size;a fourth program code allowing the computer to sequentially execute a process of generating (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 R(j,i)=U (0, h×
j+i+1(mod n)) (+) . . . (+)U (h, h×
j+i+1(mod n)) (+) . . . (+)U (k−
1, h×
j+i+1(mod n)) on the basis of the random number data U(0,0), . . . , U(h, g), . . . , U(k−
2,n−
1) ((+) is a symbol representing exclusive OR);a sharing partial data calculating device configured to calculate n(n−
1) sharing partial data D(j,i)=K(j−
1(mod n))(+)R(j,i) on the basis of the sharing partial data K(0), K(1), . . . , K(j), . . . , K(n−
1) and the random number data R(0,0), . . . , R(i,j), . . . , R(n−
1,n−
2);a header information generating device configured to assign the row number j to every n−
1 pieces of sharing partial data D(j,0) to D(j,n−
2) which are included in the generated sharing partial data and which have the same row number j, to generate n pieces of header information H(0), . . . , H(j), . . . , H(n−
1); anda sharing information distributing device configured to individually distribute the 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.
- k≧
-
7. A program stored in a computer-readable storage medium used for a computer in a secret sharing apparatus based on a (k,n)-threshold scheme and configured to individually distribute n (n≧
- k≧
4) pieces numbers to generate random number data U(0,1), U(h,g), . . . , U(k−
1,n−
1);a fifth program code allowing the computer to sequentially execute a process of calculating 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 sixth program code allowing the computer to sequentially execute a process of assigning 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); anda seventh program code allowing the computer to sequentially execute a process of individually distributing 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. - View Dependent Claims (8)
- k≧
-
9. A program stored in a computer-readable storage medium used for a computer in 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 program comprising;a first program code allowing a computer to sequentially execute a process of temporarily writing the secret information S to a memory in the computer before the distribution of the sharing information D(0) to D(n−
1);a second program code allowing the computer to sequentially execute a process of dividing the secret information into n−
1 pieces and assigning a row number j (i≦
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 third program code allowing the computer to sequentially execute a process of creating a zero value of the same size as that of each of the divided secret data and assigning the row number j=0 to a creation result to generate second divided secret data K(0); a fourth program code allowing the computer to sequentially execute a process of creating k−
1 zero value data each of the same size as that of each divided secret data and assigning a row number h (0≦
h≦
k−
2) and a column number g=0 to the zero value data to generate random number data U(0,0), . . . , U(h,
0), . . . , U(k−
2,0);a fifth program code allowing the computer to sequentially execute a process of generating k−
1 random numbers each of the same size as that of each divided secret data and assigning the row number h (0≦
h≦
k−
2) and the column number g (1≦
g≦
n−
1) to the random numbers to generate random number data U(0,1), . . . , U(h, g), . . . , U(k−
2,n−
1);a sixth program code allowing the computer to sequentially execute a process of calculating n(n−
1) random number data R(j,i)=U (0, h×
j+i+1(mod n)) (+) . . . (+)U (h, h×
j+i+1(mod n)) (+) . . . (+)U (k−
1, h×
j+i+1(mod n)) on the basis of the random number data U(0,0), U(h, g), . . . , U(k−
2,n−
1) ((+) is a symbol representing exclusive OR);a seventh program code allowing the computer to sequentially execute a process of calculating n(n−
1) sharing partial data D(j,i)=K(j−
1(mod n))(+)R(j,i) on the basis of the sharing partial data K(0), K(1), K(j), . . . , K(n−
1) and the random number data R(0,0), . . . , R(i,j), . . . , R(n−
1,n−
2);an eighth program code allowing the computer to sequentially execute a process of assigning the row number j to every n−
1 pieces of sharing partial data D(j,0) to D(j,n−
2) which are included in the generated sharing partial data and which have the same row number j, to generate n pieces of header information H(0), . . . , H(j), . . . , H(n−
1); anda tenth program code allowing the computer to sequentially execute a process of individually distributing the 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.
- k≧
Specification