Inconsistency detecting method, inconsistency detecting system, inconsistency detecting device, and program

1. An inconsistency detecting method, implemented by an inconsistency detecting system that includes n inconsistency detecting devices, wherein n and k are assumed to be integers that satisfy n≥2k−1, m is assumed to be an integer greater than or equal to 1, and i is assumed to be each of integers greater than or equal to 0 but smaller than n,

the inconsistency detecting method comprising:

storing shares [a 0 ] i , . . . , [a m−1 ] i obtained by dividing m electronic plain text values a 0 , . . . , a m−1 by (k, n)-secret sharing in storages of the n inconsistency detecting devices p i which are connected to each other via a communications network, where an original plain text value based on a combination of the values a 0 , . . . , a m−1 is only reconstructed when at least arbitrary k shares of the shares [a 0 ] i , . . . , [a m−1 ] i are provided by the inconsistency detecting devices p i ,

generating, by circuitry of the n inconsistency detecting devices p i , random numbers s i and making the random numbers s i public;

generating, by circuitry of the n inconsistency detecting devices p i a common random number s which is a sum total of the random numbers s 0 , . . . , s n−1 ;

calculating, by circuitry of the n inconsistency detecting devices p i shares [c] i =Σ j<m−1 s j+1 [a j ] i +s m+1 [a m−1 ] i by using the common random number s and the shares [a 0 ] i , . . . , [a m−1 ] i ;

generating, by circuitry of the n inconsistency detecting devices p i shares [r] i , each of which becomes a random number r by reconstruction when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p 0 , . . . , p n−1 ;

calculating, by circuitry of the n inconsistency detecting devices p i shares [d] i =[c−r] i , each of which becomes a judgment value d by reconstruction when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a 0 ] i , . . . , [a m−1 ] i ;

receiving, by circuitry of one inconsistency detecting device p 0 n−1 shares [d] 1 , . . . , [d] n−1 from circuitry of n−1 inconsistency detecting devices p 1 , . . . , p n−1 ;

restoring, by circuitry of the inconsistency detecting device p 0 n−k shares [d]′ k , . . . , [d]′ n−1 from k shares [d] 0 , . . . , [d] k−1 ; and

judging, by circuitry of the inconsistency detecting device p 0 for j=k, . . . , n−1, whether or not the share [d] j and the share [d]′ j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a 0 ] i , . . . , [a m−1 ] i for i=0, . . . , n are consistent while concealing the electronic plain text values a 0 , . . . , a m−1 from all of the n inconsistency detecting devices by secret sharing.

2. The inconsistency detecting method according to claim 1 , wherein

j is assumed to be an integer greater than or equal to 0 but smaller than m,

the inconsistency detecting method further includes:

dividing the shares [a 0 ] i , . . . , [a m−1 ] i into a plurality of groups;

performing a processing which includes:

detecting a presence or absence of an inconsistency in each group; and

dividing a group on which a judgment that an inconsistency has occurred therein is made into a plurality of groups; and

repeating the processing until a number of shares included in a group becomes one to identify a share [a j ] i in which an inconsistency has occurred.

3. An inconsistency detecting system that includes n inconsistency detecting devices p 0 , . . . , p n−1 , wherein

n and k are assumed to be integers that satisfy n≥2k−1, m is assumed to be an integer greater than or equal to 1, i is assumed to be each of integers greater than or equal to 0 but smaller than n, and i′ is assumed to be each of integers that satisfy i≠ i′ and are greater than or equal to 0 but smaller than n, and

each of the inconsistency detecting devices p i comprising:

circuitry configured to:

store shares [a 0 ] i , . . . , [a m−1 ] i obtained by dividing m electronic plain text values a 0 , . . . , a m−1 by (k, n)-secret sharing in a storage, the n inconsistency detecting devices being connected to each other via a communications network, where an original plain text value based on a combination of the values a 0 , . . . , a m−1 is only reconstructed if at least arbitrary k shares of the shares [a 0 ] i , . . . , [a m−1 ] i are provided by the inconsistency detecting devices p i ;

generate a random number s i and make the random number s i public;

generate a common random number s which is a sum total of the random numbers s 0 , . . . , s n−1 ;

calculate a share [c] i =Σ j<m−1 s j+1 [a j ] i +s m+1 [a m−1 ] i by using the common random number s and the shares [a 0 ] i , . . . , [a m−1 ] i ;

generate a share [r] i which becomes a random number r when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p 0 , . . . , p n−1 ;

calculate a share [d] i =[c−r] i which becomes a judgment value d

when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a 0 ] i , . . . , [a m−1 ] i ;

receive n−1 shares [d] i′ from other n−1 inconsistency detecting devices p i ;

restore n−k shares [d]′ k , . . . , [d]′ n−1 from k shares [d] 0 , . . . , [d] k−1 ; and

judge, for j=k, . . . , n−1, whether or not the share [d] j and the share [d]′ j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a 0 ] i , . . . , [a m−1 ] i for i=0, . . . , n are consistent while concealing the electronic plain text values a 0 , . . . , a m−1 from all of the n inconsistency detecting devices by secret sharing.

4. An inconsistency detecting device in an inconsistency detecting system that includes n inconsistency detecting devices, wherein

n and k are assumed to be integers that satisfy n≥2k−1, m is assumed to be an integer greater than or equal to 1, i is assumed to be an integer greater than or equal to 0 but smaller than n, and i′ is assumed to be each of integers that satisfy i≠i′ and are greater than or equal to 0 but smaller than n, and

the inconsistency detecting device comprising:

circuitry configured to:

store shares [a 0 ] i , . . . , [a m−1 ] i obtained by dividing electronic plain text values a 0 , . . . , a m−1 by (k, n)-secret sharing in a storage, the n inconsistency detecting devices being connected to each other via a communications network, where an original plain text value based on a combination of the values a 0 , . . . , a m−1 is only reconstructed if at least arbitrary k shares of the shares [a 0 ] i , . . . , [a m−1 ] i are provided by the inconsistency detecting devices p i ;

generate a random number s i and makes the random number s i public;

generate a common random number s which is a sum total of the random numbers s 0 , . . . , s n−1 ;

calculate a share [c] i =Σ j<m−1 s j+1 [a j ] i +s m+1 [a m−1 ] i by using the common random number s and the shares [a 0 ] i , . . . , [a m−1 ] i ;

generate a share [r] i which becomes a random number r when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p 0 , . . . , p n−1 ;

calculate a share [d] i =[c−r] i which becomes a judgment value d when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a 0 ] i , . . . , [a m−1 ] i ;

receive n−1 shares [d] i′ from circuitry of other n−1 inconsistency detecting devices p i′ ;

restore n−k shares [d]′ k , . . . , [d]′ n−1 from k shares [d] 0 , . . . , [d] k−1 ; and

judge, for j=k, . . . , n−1, whether or not the share [d] j and the share [d]′ j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a 0 ] i , . . . , [a m−1 ] i for i=0, . . . , n are consistent while concealing the electronic plain text values a 0 , . . . , a m−1 from all of the n inconsistency detecting devices by secret sharing computation.

5. A non-transitory computer readable medium including computer executable instructions that make an inconsistency detecting device in an inconsistency detecting system that includes n inconsistency detecting devices, wherein

n and k are assumed to be integers that satisfy n≥2k−1, m is assumed to be an integer greater than or equal to 1, i is assumed to be an integer greater than or equal to 0 but smaller than n, and i′ is assumed to be each of integers that satisfy i≠i′ and are greater than or equal to 0 but smaller than n,

perform a method comprising:

storing shares [a 0 ] i , . . . , [a m−1 ] i obtained by dividing m electronic plain text values a 0 , . . . , a m−1 by (k, n)-secret sharing in a storage, the n inconsistency detecting devices being connected to each other via a communications network, where an original plain text value based on a combination of the values a 0 , . . . , a m−1 is only reconstructed if at least arbitrary k shares of the shares [a 0 ] i , . . . , [a m−1 ] i are provided by the inconsistency detecting devices p i ;

generating a random number s i and making the random number s i public;

generating a common random number s which is a sum total of the random numbers s 0 , . . . , s n−1 ;

calculating a share [c] i =Σ j<m−1 s j+1 [a j ] i +s m+1 [a m−1 ] i by using the common random number s and the shares [a 0 ] i , . . . , [a m−1 ] i ;

generating a share [r] i which becomes a random number r when reconstructed by (k, n)-secret sharing, wherein the random number r is concealed by any of the n inconsistency detecting devices p 0 , . . . , p n−1 ;

calculating a share [d] i =[c−r] i which becomes a judgment value d when reconstructed by (k, n)-secret sharing, wherein the judgment value d indicates that there is no inconsistency in the shares [a 0 ] i , . . . , [a m−1 ] i ;

receiving n−1 shares [d] i′ from circuitry of other n−1 inconsistency detecting devices p i′ ;

restoring n−k shares [d]′ k , . . . , [d]′ n−1 from k shares [d] 0 , . . . , [d] k−1 ; and

judging, for j=k, . . . , n−1, whether or not the share [d] j and the share [d]′ j coincide with each other,

wherein the inconsistency detecting device is configured to detect an inconsistency by determining whether or not the shares [a 0 ] i , . . . , [a m−1 ] i for i=0, . . . , n are consistent while concealing the electronic plain text values a 0 , . . . , a m−1 from all of the n inconsistency detecting devices by secret sharing.