SECRET SHARING DEVICE, METHOD, AND PROGRAM
First Claim
Patent Images
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(1), . . . , B(k−
1) recursively by the partial matrix G′
, . . . , G(k−
2) 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 kth row and the kth column in the divided unit of the partial matrix G(k−
1) obtained by last multiplication and calculate a recovery matrix B(1) . . . B(k-1)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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
7 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(1), . . . , B(k−
1) recursively by the partial matrix G′
, . . . , G(k−
2) 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 kth row and the kth column in the divided unit of the partial matrix G(k−
1) obtained by last multiplication and calculate a recovery matrix B(1) . . . B(k-1)B(k) by multiplication of all the basic matrices; anda recovering device configured to recover the secret information by multiplying the k items of shared information by the recovery matrix. - View Dependent Claims (2, 3)
- 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)2 items of random number data R(1), . . . , R((n−
1)2) 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(i), . . . , R((n−
1)2), K(1), . . . , K(j), . . . , K(n−
1)), and the inverse matrix G−
1 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, hence to create n items of header information H(1), . . . , H(j), . . . H(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; anda 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. - View Dependent Claims (5)
- 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;
-
6. A program stored in a computer-readable storage medium 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, comprising;first program code which causes the secret sharing device to perform 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;second program code which causes the secret sharing device to perform 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; third program code which causes the secret sharing device to perform 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;fourth program code which causes the secret sharing device to perform 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;fifth program code which causes the secret sharing device to perform 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);is sixth program code which causes the secret sharing device to perform 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);seventh program code which causes the secret sharing device to perform 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;eighth program code which causes the secret sharing device to perform 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(1), . . . , B(k-1) recursively by the partial matrix G′
, . . . , G(k-2) 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 kth row and the kth column in the divided unit of the partial matrix G(k-1) obtained by last multiplication and calculate a recovery matrix B(1) . . . B(k-1)B(k) by multiplication of all the basic matrices; andninth program code which causes the secret sharing device to perform processing of recovering the secret information by multiplying the k items of shared information by the recovery matrix.
- k≦
-
7. A program stored in a computer-readable storage medium 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, comprising;
first program code which causes the secret sharing device to perform 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;second program code which causes the secret sharing device to perform 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; third program code which causes the secret sharing device to perform 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;fourth program code which causes the secret sharing device to perform processing of creating (n−
1)2 items of random number data R(1), . . . , R((n−
1)2) having the same size as that of said each divided secret data;fifth program code which causes the secret sharing device to perform 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)2), K(1), . . . , K(j), . . . , K(n−
1)), and the inverse matrix G−
1 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);sixth program code which causes the secret sharing device to perform 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);seventh program code which causes the secret sharing device to perform 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; andeighth program code which causes the secret sharing device to perform 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.
- 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;
Specification