Secret sharing apparatus, method, and program

• US 8,077,863 B2
• Filed: 03/19/2008
• Issued: 12/13/2011
• Est. Priority Date: 03/23/2007
• Status: Active Grant

• Current Assignee: Toshiba Solutions Corporation (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation), Toshiba Solutions Corporation (Toshiba Corporation)
• Inventors: Fujii, Yoshihiro, Kato, Takehisa, Hosaka, Norikazu, Tada, Minako
• Primary Examiner(s): Colin, Carl
• Assistant Examiner(s): AUGER, PHILLIP R
• Application Number:
  US12/051,524
• Publication Number:
  US 20080232580A1
• Time in Patent Office: 1,364 Days
• Field of Search: 380/28, 380/277
• US Class Current: 380/28
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

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 but is still operational with a threshold of at least 2. 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.

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); 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.

2. The secret distributing apparatus according to claim 1, wherein the sharing information distributing device individually places the n column vectors in the n pieces of sharing information D(0), . . . , D(n−

1), and

the secret sharing apparatus further comprises;

a device configured to obtain k column vectors from k pieces of sharing information collected from any k of the n storage apparatuses;

a device configured to form a submatrix of the generator matrix from the k column vectors and to calculate an inverse matrix of the submatrix,

a device configured to calculate a product of matrixes of the collected k pieces of sharing information and the inverse matrix (the calculation is performed on GF(2)) to obtain the divided secret data K(1), . . . , K(j), . . . , K(n−

1); and

a device configured to restore the secret information S from the resulting divided secret data K(1), . . . , K(j), . . . , K(n−

1).

3. A secret sharing method performed by the secret sharing apparatus according to claim 1, the method comprising:

storing an input sharing number n and an input threshold k in the storage device;

generating, by the generator matrix generating device, a first minor matrix of n rows×

(n−

1) columns in which (n−

1) rows×

(n−

1) columns under the 0th row have a laterally symmetrical relationship with a unit matrix;

executing, by the generator matrix generating device, a first adjacency process of cyclically shifting each of the columns of a leftmost first minor matrix upward once to obtain a new first minor matrix of n rows×

(n−

1) columns and placing the first minor matrix on a left side of and adjacent to the first minor matrix not subjected to the cyclic shift yet;

executing, by the generator matrix generating device, the first adjacency process n−

1 times to generate a first submatrix of n rows×

n(n−

1) columns;

executing, by the generator matrix generating device, a first submatrix assigning process of assigning a 1st row to an n−

1th row of the first submatrix to a 0th row to an n−

2th row of the generator matrix G to generate a submatrix corresponding to the 0th to n−

2th rows of the generator matrix G;

executing, by the generator matrix generating device, a process of generating a second minor matrix of n rows×

(n−

1) columns in which a 0th row is a zero vector and in which (n−

1) rows×

(n−

1) columns under the 0th row correspond to a unit matrix;

executing, by the generator matrix generating device, a second adjacency process of cyclically shifting each of the columns of a leftmost second minor matrix downward j times to obtain a new second minor matrix of n rows×

(n−

1) columns and placing the second minor matrix on the right side of and adjacent to the second minor matrix not subjected to the cyclic shift yet (j=0, 1, . . . , k−

2);

executing, by the generator matrix generating device, a second submatrix generating process of executing the second adjacency process n−

1 times to generate a second submatrix of n rows×

n(n−

1) columns;

executing, by the generator matrix generating device, a second submatrix assigning process of assigning a 1st row to an n−

1th row of the second submatrix to an (n−

1)(j+1)th row to an (n−

1)(j+1)+n−

2th row of the generator matrix G to generate a submatrix corresponding to the (n−

1)(j+1)th to (n−

1)(j+1)+n−

2th rows of the generator matrix G (j=0, 1, . . . , k−

2);

executing, by the generator matrix generating device, a process of, with a value of j for the second adjacency process and the second submatrix assigning process varied from an initial value 0 to a final value k−

2, executing the second adjacency process, the second submatrix generating process, and the second submatrix assigning process k−

1 times while increasing a value of j by one every time the second submatrix generating process and the second submatrix assigning process are executed; and

executing, by the generator matrix generating device, a process of generating the generator matrix G of k(n−

1) rows×

n(n−

1) columns of whose 0th to n−

2th rows are a result from the assignment of the first submatrix assigning process and whose n−

1th to (n−

1)(k−

1)+n−

2th rows are a result from the assignment of the second submatrix assigning process repeated k−

1 times.

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); 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 HO) and sharing partial data D(j,0) to D(j,n−

2) having the same row number j, to the n storage apparatuses.

5. The secret distributing apparatus according to claim 4, wherein the sharing information distributing device individually places the n column vectors in the n pieces of sharing information D(0), . . . , D(n−

1), and

the secret sharing apparatus further comprises;

a device configured to obtain k column vectors from k pieces of sharing information collected from any k of the n storage apparatuses;

a device configured to form a submatrix of the generator matrix from the k column vectors and to calculate an inverse matrix of the submatrix,

a device configured to calculate a product of matrixes of the collected k pieces of sharing information and the inverse matrix (the calculation is performed on GF(2)) to obtain the divided secret data K(1), . . . , K(j), . . . , K(n−

1); and

a device configured to restore the secret information S from the resulting divided secret data K(1), . . . , K(j), . . . , K(n−

1).

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 (n−

1)(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 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); and

a 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.

7. A non-transitory computer-readable medium storing computer readable instructions thereon for a computer in a secret sharing apparatus based on a (k,n)-threshold scheme, the instructions when executed by the computer performing a method comprising:

individually distributing n (n≧

k≧

4) pieces of sharing information D(0), . . . , D(n−

1) into which secret information S is divided, to n storage apparatuses;

restoring the secret information S from any k of the n pieces of sharing information;

sequentially executing 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);

executing 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);

sequentially executing 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;

sequentially executing 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 numbers to generate random number data U(0,1), . . . , U(h,g), . . . , U(k−

1,n−

1);

sequentially executing 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);

sequentially executing 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); and

sequentially executing 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.

8. The non-transitory computer-readable medium according to claim 7, wherein the step of executing a process of distributing includes a procedure of individually placing the n column vectors in the n pieces of sharing information D(0), . . . , D(n−

1), and

further comprising;

sequentially executing a process of obtaining k column vectors from k pieces of sharing information collected from any k of the n storage apparatuses;

sequentially executing a process of forming a submatrix of the generator matrix from the k column vectors and to calculate an inverse matrix of the submatrix,

sequentially executing a process of calculating a product of matrixes of the collected k pieces of sharing information and the inverse matrix (the calculation is performed on GF(2)) to obtain the divided secret data K(1), . . . , K(j), . . . , K(n−

1); and

sequentially executing a process of restoring the secret information S from the resulting divided secret data K(1), . . . , K(j), . . . , K(n−

1).

9. A non-transitory computer-readable medium storing computer readable instructions thereon for a computer in a secret sharing apparatus based on a (k,n)-threshold scheme, the instructions when executed by the computer performing a method comprising:

individually distributing n (n≧

k≧

4) pieces of sharing information D(0), . . . , D(n−

1) into which secret information S is divided, to n storage apparatuses;

restoring the secret information S from any k of the n pieces of sharing information;

sequentially executing 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);

sequentially executing a process of dividing the secret information into n−

1 pieces and assigning 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;

sequentially executing 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);

sequentially executing 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);

sequentially executing a process of generating (n−

1)(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);

sequentially executing 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);

sequentially executing 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);

sequentially executing 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); and

sequentially executing 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.