Secret sharing apparatus, method, and program

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.

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.

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.

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.