1. A verification device, said verification device: taking 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) a ′ degree on a finite field based on power p of a prime number; taking as q a prime number that satisfies the relation q≧n*p, taking as r and t natural numbers that satisfy k≧t+r, taking 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 identifying 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 verification device comprising: input means that receives as input k items of shared information and said t; subset generation means 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; coherence judging means 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 means whether dishonest shared information is contained in the subset; and cheater-identification means that, based on the judgment result by said coherence-judging means and the shared information contained in each subset, identifies dishonest shared information.