Secret sharing device, method, and program

• US 8,074,068 B2
• Filed: 05/02/2008
• Issued: 12/06/2011
• Est. Priority Date: 06/26/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, Hosaka, Norikazu, Tada, Minako, Kato, Takehisa
• Primary Examiner(s): Colin, Carl
• Assistant Examiner(s): AUGER, PHILLIP R
• Application Number:
  US12/114,237
• Publication Number:
  US 20090144543A1
• Time in Patent Office: 1,313 Days
• Field of Search: 380/28, 380/277
• US Class Current: 713/160
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A secret sharing device of (k, n) threshold scheme creates a generator matrix G, first divided secret data, and random number data, calculates shared partial data based on the product of matrices with the random number data, the divided secret data, and the generator matrix G, and delivers the shared information formed by the shared partial data and the header information individually to the storage units. The secret sharing device calculates a recovery matrix and multiplies the shared information by the recovery matrix, hence to recover the secret information.

Claims

1. A secret sharing device of (k, n) threshold scheme (where 2≦

k≦

n) which individually delivers n items of shared information D(1), . . . , D(n), created by dividing secret information S, to n storage units and recovers the secret information S from any k items of shared information, of the n items of shared information, comprising;

a generator matrix creating device configured to create a generator matrix G of GF(2) (where size of the generator matrix G is k(n−

1) rows×

n(n−

1) columns and the GF(2) is a finite field of order 2) which is formed by n column vectors each including k(n−

1) rows×

(n−

1) columns and formed by any k column vectors that become full rank, of the n column vectors;

a storage device which temporarily stores the secret information S before the shared information D(1) to D(n) is delivered;

a divided secret data creating device configured to create n−

1 items of first divided secret data K(1), . . . , K(j), . . . , K(n−

1) of the same size by dividing the secret information S into n−

1 items and assigning row number j (where 1≦

j≦

n−

1) from 1 to n−

1 to the divided result;

a random number data creating device configured to create (k−

1)(n−

1) items of random number data R(1), . . . , R((k−

1)(n−

1)) having the same size as that of said each divided secret data;

a shared partial data calculating device configured to calculate a product of matrices with the random number data, the divided secret data (R(1), . . . , R((k−

1)(n−

1)), K(1), . . . , K(j), . . . , K(n−

1)), and the generator matrix G, assign the calculation result in (j×

(n−

1)+i)^th column to the shared partial data D(j, i), and calculate n(n−

1) items of shared partial data D(j, i) (where 1≦

j≦

n and 1≦

i≦

n−

1);

a header information creating device configured to assign the row number j to n−

1 items of shared partial data D(j, 1) to D(j, n−

1) having the same row number j, of said each shared partial data, hence to create n items of header information H(1), . . . , H(j), . . . , H(n);

a shared information delivering device configured to individually deliver the n items of shared information D(1), . . . , D(j), D(n), each formed by the header information H(j) and the shared partial data D(j, 1) to D(j, n−

1) having the same row number j and the n column vectors, to the n storage units;

a recovery matrix calculating device configured to form a partial matrix G′

of k(n−

1) rows×

k(n−

1) columns in the generator matrix G from k column vectors included in any k items of shared information of the delivered n items of shared information D(1), . . . , D(j),. . . , D(n) and multiply a basic matrix B⁽¹⁾, . . . , B<sup>(k−

1)</sup> recursively by the partial matrix G′

, G<sup>(k−

2)</sup> so that random number components from the first row to the (k−

1)^th row become zero in every matrix unit obtained by dividing the partial matrix G′

by (n−

1) rows×

(n−

1) columns, hence to create a basic matrix B^(k) by using an inverse matrix of the components in the k^th row and the k^th column in the divided unit of the partial matrix G<sup>(k−

1)</sup> obtained by last multiplication and calculate a recovery matrix B⁽¹⁾ . . . B<sup>(k−

1)</sup>B^(k) by multiplication of all the basic matrices; and

a recovering device configured to recover the secret information by multiplying the k items of shared information by the recovery matrix.

2. A secret sharing method performed by the secret sharing device according to claim 1, the method comprising:

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

creating, by the generator matrix creating device, a matrix E′

of n rows×

(n−

1) columns by adding a zero matrix of one row×

(n−

1) columns to the final row of a unit matrix E of (n−

1) rows×

(n−

1) columns;

executing, by the generator matrix creating device, a cyclic shift process of creating a matrix E′

((i−

1)(j−

1)) by cyclically shifting the matrix E′

of n rows×

(n−

1) columns in a vertical direction (i−

1)(j−

1) times;

executing, by the generator matrix creating device, an assignment process of obtaining a matrix E((i−

1)(j−

1)) of (n−

1) rows×

(n−

1) columns resulting from deleting the final row from the matrix E′

((i−

1)(j−

1) and assigning the matrix E to the block of i rows by j columns, when dividing the matrix by the unit of (n−

1) rows×

(n−

1) columns, based on the division number n and the threshold k within the storage device; and

as a result, by the generator matrix creating device, having created the generator matrix G by having performed the cyclic shift process and the assignment process on all the blocks of i rows by j columns (1≦

i≦

k, 1≦

j≦

n).

3. The secret sharing method according to claim 2, further comprising:

creating, by the recovery matrix calculating device, a basic matrix B⁽¹⁾ for zeroing all components in the first row resulting from dividing a partial matrix G′

=(g(D(i_1), . . . , D(i_k))=(U_(1,1), . . . , U_(i,j), . . . , U_(k,k)) (where U_(i,j)=E(<sub>(i−

1)(j−

1)</sub>) of the generator matrix G by the unit of (n−

1) rows×

(n−

1) columns;

obtaining, by the recovery matrix calculating device, a partial matrix G⁽¹⁾=G′

B⁽¹⁾ by multiplying the partial matrix G′

by the basic matrix B⁽¹⁾ to zero all the components in the above first row;

executing, by the recovery matrix calculating device, a basic matrix creating process of creating a basic matrix B^(d) for zeroing all the components in the d^th row resulting from dividing a partial matrix G<sup>(d−

1)</sup> by the unit of (n−

1) rows×

(n−

1) columns, when the obtained partial matrix is defined as the partial matrix G<sup>(d−

1)</sup>;

executing, by the recovery matrix calculating device, a partial matrix creating process of obtaining a partial matrix G^(d)=G<sup>(d−

1)</sup>B^(d) by multiplying the partial matrix G<sup>(d−

1)</sup> by the basic matrix B^(d) to zero all the components in the above d^th row;

obtaining, by the recovery matrix calculating device, a partial matrix G<sup>(k−

1)</sup>=G<sup>(k−

2)</sup>B<sup>(k−

1)</sup> by recursively performing the basic matrix creating process and the partial matrix creating process up to (d=k−

1)^th row;

calculating, by the recovery matrix calculating device, a basic matrix B^(k) by arranging an inverse matrix U_(k,k)<sup>−

1</sup> of a matrix U_(k,k) in the k^th row and k^th column in the partial matrix G<sup>(k−

1)</sup>, for the component in the k^th row and the k^th column and arranging a zero matrix for the other components; and

creating, by the recovery matrix calculating device, a recovery matrix B⁽¹⁾ . . . B<sup>(k−

1)</sup>B^(k) by multiplication of all the basic matrices B⁽¹⁾, . . . , B<sup>(k−

1)</sup>, B^(k).

4. A secret sharing device of (n, n) threshold scheme (where 2≦

n) which individually delivers n items of shared information D(1), . . . , D(n), created by dividing secret information S, to n storage units and recovers the secret information S from the n items of shared information, comprising;

a generator matrix creating device configured to create a generator matrix G of GF(2) (where size of the generator matrix G is n(n−

1) rows×

n(n−

1) columns and the GF(2) is a finite field of order 2) which is formed by n column vectors each including n(n−

1) rows×

(n−

1) columns and formed by the n column vectors that become full rank;

a storage device which temporarily stores the secret information S before the shared information D(1) to D(n) is delivered;

a divided secret data creating device configured to create n−

1 items of first divided secret data K(1), . . . , K(j), . . . , K(n−

1) of the same size by dividing the secret information S into n−

1 items and assigning row number j (where 1≦

j≦

n−

1) from 1 to n−

1 to the divided result;

a random number data creating device configured to create (n−

1)² items of random number data R(1), . . . , R((n−

1)²) having the same size as that of said each divided secret data;

a shared partial data calculating device configured to calculate a product of matrices with the random number data, the divided secret data (R(1), . . . , R((n−

1)²), K(1), . . . , K(j), . . . , K(n−

1)), and the inverse matrix G<sup>−

1</sup> of the generator matrix G, assign the calculation result in (j×

(n−

1)+i)^th column to the shared partial data D(j, i), and calculate n(n−

1) items of shared partial data D(j, i) (where 1≦

j≦

n and 1≦

i≦

n−

1);

a header information creating device configured to assign row number j to n−

1 items of shared partial data D(j, 1) to D(j, n−

1) having the same row number j, of said each shared partial data, and to create n items of header information H(1), . . . , H(j), . . . H(n) (where 1≦

j≦

n);

a shared information delivering device configured to individually deliver the header information H(j) and the shared partial data D(j, 1) to D(j, n−

1) having the same row number j and the n items of shared information D(1), . . . , D(j), . . . , D(n) each formed by the n column vectors to the n storage units; and

a recovering device configured to recover the secret information by multiplying the delivered n items of shared information D(1), . . . , D(j), . . . , D(n) by the generator matrix G.

5. A secret sharing method performed by the secret sharing device according to claim 4, the method comprising:

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

creating, by the generator matrix creating device, a matrix E′

of n rows×

(n−

1) columns by adding a zero matrix of one row×

(n−

1) columns to the final row of a unit matrix E of (n−

1) rows×

(n−

1) columns;

executing, by the generator matrix creating device, a cyclic shift process of creating a matrix E′

((i−

1)(j−

1)) by cyclically shifting the matrix E′

of n rows×

(n−

1) columns in a vertical direction (i−

1)(j−

1) times;

executing, by the generator matrix creating device, an assignment process of obtaining a matrix E((i−

1)(j−

1)) of (n−

1) rows×

(n−

1) columns resulting from deleting the final row from the matrix E′

((i−

1)(j−

1) and assigning the matrix E to the block of i rows by j columns, when dividing the matrix by the unit of (n−

1) rows×

(n−

1) columns, based on the division number n and the threshold n within the storage device; and

as a result, by the generator matrix creating device, having created the generator matrix G by having performed the cyclic shift process and the assignment process on all the blocks of i rows by j columns (1≦

i≦

n, 1≦

j≦

n).

6. A non-transitory computer-readable storage medium that stores a program for use in a secret sharing device of (k, n) threshold scheme (where 2≦

k≦

n) which individually delivers n items of shared information D(1), . . . , D(n), created by dividing secret information S, to n storage units and recovers the secret information S from any k items of shared information, of the n items of shared information, the program, when executed, causes the secret sharing device to execute a method comprising;

performing processing of creating a generator matrix G of GF(2) (where size of the generator matrix G is k(n−

1) rows×

n(n−

1) columns and the GF(2) is a finite field of order 2) which is formed by n column vectors each including k(n−

1) rows×

(n−

1) columns and formed by any k column vectors that become full rank, of the n column vectors;

performing processing of temporarily storing the secret information S in the storage unit of the secret sharing device before the shared information D(1) to D(n) is delivered;

performing processing of creating n−

1 items of first divided secret data K(1), . . . , K(j), . . . , K(n−

1) of the same size by dividing the secret information S into n−

1 items and assigning row number j (where 1≦

j≦

n−

1) from 1 to n−

1 to the divided result;

performing processing of creating (k−

1)(n−

1) items of random number data R(1), . . . , R((k−

1)(n−

1)) having the same size as that of said each divided secret data;

performing processing of calculating a product of matrices (calculation on GF(2)) with the random number data, the divided secret data (R(1), . . . , R((k−

1)(n−

1)), K(1), . . . , K(j), . . . , K(n−

1)), and the generator matrix G, assigning the calculation result in (j×

(n−

1)+i)^th column to the shared partial data D(j, i), and calculating n(n−

1) items of shared partial data D(j, i) (where 1≦

j≦

n and 1≦

i≦

n−

1);

performing processing of assigning row number j to n−

1 items of shared partial data D(j, 1) to D(j, n−

1) having the same row number j, of said each shared partial data, hence to create n items of header information H(1), . . . , H(j), . . . , H(n);

performing processing of individually delivering the n items of shared information D(1), . . . , D(j), . . . , D(n), each formed by the header information H(j) and the shared partial data D(j, 1) to D(j, n−

1) having the same row number j and the n column vectors, to the n storage units;

performing processing of forming a partial matrix G′

of k(n−

1) rows×

k(n−

1) columns in the generator matrix G from k column vectors included in any k items of shared information of the delivered n items of shared information D(1), . . . , D(j), . . . , D(n) and multiplying a basic matrix B⁽¹⁾, . . . , B<sup>(k−

1)</sup> recursively by the partial matrix G′

, . . . , G<sup>(k−

2)</sup> so that random number components from the first row to the (k−

1)^th row become zero in every matrix unit obtained by dividing the partial matrix G′

by (n−

1) rows×

(n−

1) columns, hence to create a basic matrix B^(k) by using an inverse matrix of the components in the k^th row and the k^th column in the divided unit of the partial matrix G<sup>(k−

1)</sup> obtained by last multiplication and calculate a recovery matrix B⁽¹⁾ . . . B<sup>(k−

1)</sup>B^(k) by multiplication of all the basic matrices; and

performing processing of recovering the secret information by multiplying the k items of shared information by the recovery matrix.

7. A non-transitory computer-readable storage medium that stores a program for use in a secret sharing device of (n, n) threshold scheme (where 2≦

n) which individually delivers n items of shared information D(1), . . . , D(n), created by dividing secret information S, to n storage units and recovers the secret information S from the n items of shared information, the program, when executed, causes the secret sharing device to execute a method comprising;

performing processing of creating a generator matrix G of GF(2) (where size of the generator matrix G is n(n−

1) rows×

n(n−

1) columns and the GF(2) is a finite field of order 2) which is formed by n column vectors each including n(n−

1) rows×

(n−

1) columns and formed by the n column vectors that become full rank;

performing processing of temporarily storing the secret information S in the storage unit of the secret sharing device before the shared information D(1) to D(n) is delivered;

performing processing of creating n−

1 items of first divided secret data K(1), . . . , K(j), . . . , K(n−

1) of the same size by dividing the secret information S within the storage unit into n−

1 items and assigning row number j (where 1≦

j≦

n−

1) from 1 to n−

1 to the divided result;

performing processing of creating (n−

1)² items of random number data R(1), . . . , R((n−

1)²) having the same size as that of said each divided secret data;

performing processing of calculating a product of matrices (calculation on GF(2)) with the random number data, the divided secret data (R(1), . . . , R((n−

1)²), K(1), . . . , K(j), . . . , K(n−

1)), and the inverse matrix G<sup>−

1</sup> of the generator matrix G, assigning the calculation result in (j×

(n−

1)+i)^th column to the shared partial data D(j, i), and calculating n(n−

1) items of shared partial data D(j, i) (where 1≦

j≦

n and 1≦

i≦

n−

1);

performing processing of assigning row number j to n−

1 items of shared partial data D(j, 1) to D(j, n−

1) having the same row number j, of said each shared partial data, hence to create n items of header information H(1), . . . , H(j), . . . , H(n);

performing processing of individually delivering the n items of shared information D(1), . . . , D(j),. . . , D(n), each formed by the header information H(j) and the shared partial data D(j, 1) to D(j, n−

1) having the same row number j and the n column vectors, to the n storage units; and

performing processing of recovering the secret information by multiplying the delivered n items of shared information D(1), . . . , D(j), . . . , D(n) by the generator matrix G.