An efficient share recovery technique for Shamir's secret sharing is provided. n share recovery apparatuses p0, . . . , pn−1 generate a share [r]i of a secretly shared value shared through Shamir's secret sharing, which becomes a random number r when restored. k share recovery apparatuses σ0, . . . , σk−1 calculate a share [b]i by subtracting the share [r]i from a share [a]i. The share recovery apparatus τk receives the shares [b]0, . . . , [b]k−1 from the share recovery apparatuses σ0, . . . , σk−1. The share recovery apparatus τk recovers shares [b]k, . . . , [b]k+m−1 using the shares [b]0, . . . , [b]k−1. m−1 share recovery apparatuses τk+1, . . . , τk+m−1 receive a share [b]j from the share recovery apparatus τk. m share recovery apparatuses τk, . . . , τk+m−1 calculate the share [a]j by adding the share [r]j to the share [b]j.