Patent ID: 8483386

Claim:
A share generation apparatus comprising: a processing unit comprising at least one central unit (CPU); a secret sharing unit, executed by the processing unit, that shares and encodes a secret in accordance with an access structure of a secret sharing scheme; a random number sharing unit, executed by the processing unit, that shares and encodes a random number in accordance with the access structure of the secret sharing scheme; and a check data generation unit, executed by the processing unit, that generates check data corresponding to the secret and the random number, wherein for a secret s=(s_ 1 , s_ 2 , . . . , s_N) serving as a member of a field having a number p^N of elements, a random number r=(r_ 1 , r_ 1 , . . . , r_[k−1]) serving as a member of a field having a number p^[k−1] of elements, and a predetermined constant c, said check data generation unit selects at random n members (e_[ 10 ], e_[ 11 ]), (e_[ 20 ], e_[ 21 ]) . . . (e_[n 0 ], e_[n 1 ]) of GF(p)^2 that satisfy e_[i 0 ]+s_ 1 *e_[i 1 ]+s_ 2 *e_[i 1 ]^2+ . . . +s_N*e_[i 1 ]^N+r_ 1 *e_[i 1 ]^[N+1]+r_ 2 *e_[i 1 ]^[N+2]+ . . . +r_[k−1]*e_[i 1 ]^[N+k−1]=c where p is a prime, and k is a maximum number of shares necessary to reconstruct a secret.