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(1), . . . , 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, 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; 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 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(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; andperforming processing of recovering the secret information by multiplying the k items of shared information by the recovery matrix.
- k≦
-
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)2 items of random number data R(1), . . . , R((n−
1)2) 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)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);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; andperforming 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, the program, when executed, causes the secret sharing device to execute a method comprising;
Specification