Patent ID: 8861717

Claim:
A verification device, said verification device comprising: a computer, wherein said computer: takes as shared secret information each n item of information that is generated from secret information by a (k, n) threshold secret-sharing scheme that uses a polynomial of the (k−1) th degree on a finite field based on power p of a prime number; takes as q a prime number that satisfies the relation q≧n*p, takes as r and t natural numbers that satisfy k≧t+r, takes as cheater identification information n items of information generated by means of a t-Cheater Identifiable secret-sharing scheme that uses a polynomial of the t th degree on finite field GF(q) so as to enable identification of any of up to t items of dishonest shared secret information included in n items of said shared secret information; and identifies dishonest shared information from any k items of shared information among n items of shared information that are pairs of shared secret information and cheater-identification information; said computer comprising: an input device that receives as input k items of shared information and said t; a subset generation unit that generates all subsets that are combinations that select, from said k items of shared information applied as input to said input means, r items of shared information where r≧t+2; a coherence checking unit that, by using each item of cheater-identification information that belongs to the subset and a polynomial of the t th degree, judges for each of said subsets that were generated by said subset generation unit whether dishonest shared information is contained in the subset; and a cheater unit that, based on the judgment result by said coherence checking unit and the shared information contained in each subset, identifies dishonest shared information.