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

An inconsistency detecting system that includes n inconsistency detecting devices p0, . . . pn−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 pi comprising:
• circuitry configured to:
• store shares [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in a storage;
• generate a random number si and make the random number si public;
• generate a common random number s which is a sum total of the random numbers s0, . . . , sn−1;
• calculate a share [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]i, . . . , [am−1]i;
• generate a share [r]i which would become a random number r by reconstruction;
• calculate a share [d]i=[c−r]i which would become a judgment value d by reconstruction;
• receive n−1 shares [d]i′ from other n−1 inconsistency detecting devices pi′;
• 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.

An inconsistency detecting device, wherein

• n and k are assumed to be integers that satisfy n≧2k−1, in 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 [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in a storage;
• generate a random number si and makes the random number si public;
• generate a common random numbers which is a sum total of the random numbers s0, . . . , sn−1;
• calculate a share [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]i, . . . , [am−1]i;
• generate a share [r]i which would become a random number r by reconstruction;
• calculate a share [d]i=[c−r]i which would become a judgment value d by reconstruction;
• receive n−1 shares [d]i′ from circuitry of other n−1 inconsistency detecting devices pi′;
• 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.

A non-transitory computer readable medium including computer executable instructions that make an inconsistency detecting device, 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 [a0]i, . . . , [am−1]i obtained by dividing m values a0, . . . , am−1 by (k, n)-secret sharing in a storage;
• generating a random number si and making the random number si public;
• generating a common random numbers which is a sum total of the random numbers s0, . . . , sn−1;
• calculating a share [c]i=Σj<m−1sj+1[aj]i+sm+1[am−1]i by using the common random number s and the shares [a0]i, . . . , [am−1]i;
• generating a share which would become a random number r by reconstruction;
• calculating a share [d]i=[c−r]i which would become a judgment value d by reconstruction;
• receiving n−1 shares [d]i′ from circuitry of other n−1 inconsistency detecting devices pi′;
• 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.