Disclosed is a distributed information generation apparatus which generates a polynomial F in which secret information s is embedded to output distributed secret information, generates a polynomial G in which an output when a fixed value t is entered into the polynomial F is embedded as the secret information, and generates distributed distributed secret information. The reconstruction apparatus receives k sets of the distributed secret information to generate a polynomial F′, and receives k sets of the distributed distributed secret information to generate a polynomial G′. When a value embedded in the polynomial G′ as the secret information and an output obtained by entering the fixed value into the polynomial F′ is equal, the distributed information generation apparatus outputs the embedded value. When the embedded value is not equal to the output, the distributed information generation apparatus outputs information indicating detection of cheating.