Secret sharing system, data distribution apparatus, distributed data transform apparatus, secret sharing method and program

1. A secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses,

the data distribution apparatus comprising:

circuitry configured to:

receive an electronic information file a=(a 1 , . . . , a L )εR L as an input;

divide the electronic information file a into N shares f a (n) by using an arbitrary homomorphic ramp secret sharing scheme S 1 ;

each of the distributed data transform apparatuses comprising:

another circuitry configured to:

generate a random number vector r i =(r i,1 , . . . , r i,L ) whose elements are L random numbers r i,1 , . . . , r i,L εR;

divide the random number vector r i into N shares f n (n) by using the ramp secret sharing scheme S 1 ;

divide each of the random numbers r i,1 , . . . , r i,L into N shares g ri,1 (n), . . . , g ri,L (n) by using an arbitrary homomorphic secret sharing scheme S 2 ;

generate a share U i by using a share f a (i) included in the shares f a (n) and K shares f rλ (i);

reconstruct L pieces of disturbance information c 1 , . . . , c L from K shares U λ by using the ramp secret sharing scheme S 1 ;

divide each of the pieces of disturbance information c 1 , . . . , c L into N by using the secret sharing scheme S 2 to generate shares g c1 (n), . . . , g cL (n); and

generate shares g a1 (i), . . . , g aL (i) of the electronic information file a by using L shares g c1 (i), . . . , g cL (i) included in the shares g c1 (n), . . . , g cL (n), and L×K shares g rλ,1 (i), . . . , g rλ,L (i),

wherein N, K, and L are integers greater than or equal to 2, N≧K>L, n=1, . . . , N,λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, f x (n) represents N shares of an electronic information file x, and R is a ring, and

wherein at least K distributed data transform apparatuses are configured to reproduce the electronic information file a when at least K reconstructed values U i are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the electronic information file a can be obtained when less than the K reconstructed values U i are reconstructed by less than the K distributed data transform apparatuses.

2. The secret sharing system according to claim 1 , wherein the another circuitry is configured to:

add a sum of the shares f rλ (i) to the share f a (i) to generate the share U i , and

subtract a sum of the shares g rλ,j (i) from the share g cj (i) to generate the share g aj (i) for j=1, . . . , L.

3. The secret sharing system according to claim 1 ,

wherein the secret sharing scheme S 2 is Shamir's secret sharing scheme.

4. A distributed data transform apparatus, in a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, wherein the data distribution apparatus receives an electronic information file a =(a 1 , . . . , a L )εR L as an input and divides the electronic information file a into N shares f a (n) by using an arbitrary homomorphic ramp secret sharing scheme S 1 , the distributed data transform apparatus comprising:

circuitry configured to:

generate a random number vector r i =(r i,1 , . . . , r i,L ) whose elements are L random numbers r i,1 , . . . , r i,L εR;

divide the random number vector r i into N shares f n (n) by using the ramp secret sharing scheme S 1 ;

divide each of the random numbers r i,1 , . . . , r i,L into N shares g ri,1 (n), . . . , g ri,L , (n) by using an arbitrary homomorphic secret sharing scheme S 2 ;

generate a share U i by using a share f a (i) included in the N shares f a (n) into which the electronic information file a is divided by using the ramp secret sharing scheme S 1 and K shares f rλ (i);

reconstruct L pieces of disturbance information c 1 , . . . , c L from K shares U λ by using the ramp secret sharing scheme S 1 ;

divide each of the pieces of disturbance information c 1 , . . . , c L , into N by using the secret sharing scheme S 2 to generate shares g c1 (n), . . . , g cL (n); and

generate shares g a1 (i), . . . , g aL (i) of the electronic information file a by using L shares g c1 (i) ), . . . , g cL (i) included in the shares g c1 (n), . . . , g cL (n), and L×K shares g rλ,1 (i), . . . , g rλ,L (i),

wherein N, K, and L are integers greater than or equal to 2, N≧K>L, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, f x (n), represents N shares of an electronic information file x, and R is a ring, and

wherein at least K distributed data transform apparatuses are configured to reproduce the electronic information file a when at least K reconstructed values U i are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the electronic information file a can be obtained when less than the K reconstructed values U i are reconstructed by less than the K distributed data transform apparatuses.

5. A secret sharing method, implemented by a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, comprising:

receiving, by circuitry of the data distribution apparatus, an electronic information file a=(a 1 , . . . , a L )εR L as an input;

dividing, by the circuitry of the data distribution apparatus, the electronic information file a into N shares f a (n) by using an arbitrary homomorphic ramp secret sharing scheme S 1 ;

generating, by another circuitry of each of the distributed data transform apparatuses, a random number vector r i =(r i,1 , . . . , r i,L ) whose elements are L random numbers r i,1 , . . . , r i,L εR;

dividing, by the another circuitry of each of the distributed data transform apparatuses, the random number vector r i into N shares f n (n)using the ramp secret sharing scheme S 1 ;

dividing, by the another circuitry of each of the distributed data transform apparatuses, each of the random numbers r i,1 , . . . , r i,L into N shares g ri,1 (n), . . . , g ri,L (n) by using an arbitrary homomorphic secret sharing scheme S 2 ;

generating, by the another circuitry of each of the distributed data transform apparatuses, a share U i by using a share f a (i) included in the shares f a (n) and K shares f rλ (i),

reconstructing, by the another circuitry of each of the distributed data transform apparatuses, L pieces of disturbance information c 1 , . . . , c L from K shares U λ by using the ramp secret sharing scheme S 1 ;

dividing, by the another circuitry of each of the distributed data transform apparatuses, each of the pieces of disturbance information c 1 , . . . , c L into N by using the secret sharing scheme S 2 to generate shares g c1 (n), . . . , g cL (n); and

generating, by the another circuitry of each of the distributed data transform apparatuses, shares g a1 (i), . . . , g aL (i) of the electronic information file a by using L shares g c1 (i), . . . , g cL (i) included in the shares g c1 (n), . . . , g cL (n), and L×K shares g rλ,1 (i), . . . , g rλ,L (i),

wherein N, K, and L are integers greater than or equal to 2, N≧K>L, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, f x (n) represents N shares of an electronic information file x, and R is a ring, and

wherein at least K distributed data transform apparatuses are configured to reproduce the electronic information file a when at least K reconstructed values U i are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the electronic information file a can be obtained when less than the K reconstructed values U i are reconstructed by less than the K distributed data transform apparatuses.

6. A non-transitory computer readable medium including computer executable instructions that make a distributed data transform apparatus, in a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, wherein the data distribution apparatus receives an electronic information file a =(a 1 , . . . , a L ) εR L as an input and divides the electronic information file a into N shares f a (n) by using an arbitrary homomorphic ramp secret sharing scheme S 1 , perform a method comprising:

generating a random number vector r i =(r i,1 , . . . , r i,L ) whose elements are L random numbers r i,1 , . . . , r i,L εR;

dividing the random number vector r i into N shares f n (n) by using the ramp secret sharing scheme S 1 ;

dividing each of the random numbers r i,1 , . . . , r i,L into N shares g ri,1 (n), . . . , g ri,L (n) by using an arbitrary homomorphic secret sharing scheme S 2 ;

generating a share U i by using a share f a (i) included in the N shares f a (n) into which the electronic information file a is divided by using the ramp secret sharing scheme S 1 and K shares f rλ (i);

reconstructing L pieces of disturbance information c 1 , . . . , c L from K shares U λ by using the ramp secret sharing scheme S 1 ;

dividing each of the pieces of disturbance information c 1 , . . . , c L into N by using the secret sharing scheme S 2 to generate shares g c1 (n), . . . , g cL (n); and

generating shares g a1 (i), . . . , g aL (i) of the electronic information file a by using L shares g c1 , . . . , g cL (i) included in the shares g c1 (n), . . . , g cL (n), and L×K shares g rλ,1 (i), . . . , rλ,L (i),

wherein N, K, and L are integers greater than or equal to 2, N≧K>L, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, f x (n) represents N shares of an electronic information file x, and R is a ring, and

wherein at least K distributed data transform apparatuses are configured to reproduce the electronic information file a when at least K reconstructed values U i are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the electronic information file a can be obtained when less than the K reconstructed values U i are reconstructed by less than the K distributed data transform apparatuses.