Computational complexity is reduced in accordance with given k and n. A random number generation unit 12 generates random numbers r0 to rk−2 ϵGF(xq). A share generation unit 14 generates shares b0 to bn−1 by calculating a product of a vector a=(r0, . . . , rk−2, s), having the random numbers r0 to rk−2 and plaintext s ϵGF(xq) as its elements, and a matrix A. A share selection unit 15 generates a vector b′=(bp0, . . . , bpk−1) having, as its elements, k shares bp0 to bpk−1 selected from the shares b0 to bn−1. An inverse-matrix generation unit 16 generates an inverse matrix A′−1 of a k-degree square matrix having the p0-th to pk−1-th rows of the matrix A. A plaintext calculation unit 17 restores the plaintext s by multiplying the k-th row of the inverse matrix A′−1 and the vector b′.