A share generation apparatus (100) generates check data corresponding to a secret and random number, shares and encodes the secret and random number in accordance with a predetermined access structure, and stores them in storage devices (300—1 to 300—n). A reconstruction apparatus (200) reads out the shared/encoded secret and random number from the storage devices corresponding to members of the access structure, and reconstructs them. If the check data correspond to the reconstructed secret and random number, it is determined that the reconstructed secret is correct. If not, it is determined that cheating has occurred. Cheating of forging some shares by referring to (n−1) shares can be detected regardless of a distribution used to select a secret.