A threshold secret sharing apparatus, a threshold secret sharing scheme, a secret information recovery apparatus a secret information recovery method, and a program thereof are provided using XOR computation, thereby offering a general (k,n) threshold secret sharing scheme with high computation speed. Secret information K is divided into (np−1) divided pieces of secret information Kq (np is a prime number which is equal to or greater than a secret distribution number n). Furthermore, dummy secret information K0 is generated. Moreover, random numbers R, which are pairwise independent are generated. Then, pieces of shares are created using exclusive-OR (XOR) operations based upon the dummy secret information K0, the divided piece of secret information Kq, and the random numbers R. The pieces of shares thus generated are concatenated so as to generate n shares Si, thereby providing a (k,n) threshold secret sharing scheme.