A segment storage apparatus (100 n) of N segment storage apparatuses (100 1,..., 100 N) which respectively record secret-key segments sk 1,..., sk N obtained by segmenting a secret key SK corresponding to a public key PK, in a segmented secret-key storage system, the relationship Dec C, SK = Dec C, g sk 1,..., sk N = f Dec C, sk 1,..., Dec C, sk N being satisfied, where N is an integer not less than 2, n is an integer greater than or equal to 1 and less than or equal to N, Dec(C, SK) is a symbol representing decryption of the ciphertext C with the secret key SK, g(sk 1,..., sk N) is a function of sk 1,..., sk N, and f(m 1,..., m N) is a function of m 1,..., m N; the segment storage apparatuses (100 n) comprising: a decryption unit (110 n) adapted to use the secret-key segment sk n recorded in the segment storage apparatus to obtain a plaintext segment m n given by m n = Dec(C, sk n) and send the plaintext segment m n to a combining device; and a secret-key segment changing unit (120 n) adapted to change the secret-key segment sk n to sk n ' such that a set of secret-key segments (sk 1 ',..., sk N ') is obtained that satisfies Dec C, SK = Dec C, g sk 1 ',..., sk N ' = f Dec C, sk 1 ',..., Dec C, sk N ' and differs from (sk 1,..., sk N), characterized in that the secret-key segment changing unit (120 n) is adapted to change, periodically or under a predetermined condition, the secret-key segments sk n to sk n '; the relationship C = C 1, C 2 = G ∧ r, MH ∧ r M = Dec C, x = C 2 / C 1 ∧ x is satisfied, where {G, H} is the public key PK, x is the secret key SK and an integer greater than or equal to 0 and less than or equal to q-1, H = G^x, r is a random number and an integer greater than or equal to 0 and less than or equal to q-1, q is the order of a cyclic group, G is the generator of the cyclic group, M is a plaintext and an element of the cyclic group, C is the ciphertext and an element of the cyclic group, and ^ is a symbol representing a power; and the functions g and f are defined as g sk 1,..., sk N = sk 1 +... + sk N mod q f Dec C, sk 1,..., Dec C, sk N = Dec C, sk 1 ×... × Dec C, sk N / C 2 ∧ N − 1. a decryption unit (110 n) adapted to use the secret-key segment sk n recorded in the segment storage apparatus to obtain a plaintext segment m n given by m n = Dec(C, sk n) and send the plaintext segment m n to a combining device; and a secret-key segment changing unit (120 n) adapted to change the secret-key segment sk n to sk n ' such that a set of secret-key segments (sk 1 ',..., sk N ') is obtained that satisfies Dec C, SK = Dec C, g sk 1 ',..., sk N ' = f Dec C, sk 1 ',..., Dec C, sk N ' and differs from (sk 1,..., sk N), characterized in that the secret-key segment changing unit (120 n) is adapted to change, periodically or under a predetermined condition, the secret-key segments sk n to sk n '; the relationship C = C 1, C 2 = G ∧ r, MH ∧ r M = Dec C, x = C 2 / C 1 ∧ x is satisfied, where {G, H} is the public key PK, x is the secret key SK and an integer greater than or equal to 0 and less than or equal to q-1, H = G^x, r is a random number and an integer greater than or equal to 0 and less than or equal to q-1, q is the order of a cyclic group, G is the generator of the cyclic group, M is a plaintext and an element of the cyclic group, C is the ciphertext and an element of the cyclic group, and ^ is a symbol representing a power; and the functions g and f are defined as g sk 1,..., sk N = sk 1 +... + sk N mod q f Dec C, sk 1,..., Dec C, sk N = Dec C, sk 1 ×... × Dec C, sk N / C 2 ∧ N − 1.