An encryption device comprising: a random number generating unit adapted to generate a random number r; a first encryption unit adapted to generate a ciphertext C 2, the ciphertext C 2 being an exclusive OR of a binary sequence dependent on the random number r and a plaintext M, the plaintext M being a binary sequence; a common key generating unit adapted to generate a common key K, the common key being an element of a cyclic group G T; a second encryption unit adapted to encrypt the random number r by common key encryption using the common key K to generate ciphertext C(Ψ + 1); and a third encryption unit adapted to generate a ciphertext C 1 including C 0 = υ ⋅ b 1 0 + ∑ i = 2 I υ ι 0 ⋅ b ι 0, C λ = υ ⋅ ∑ ι = 1 n λ w ι λ ⋅ b ι λ + ∑ ι = n λ + 1 n λ + ζ λ υ ι λ ⋅ b ι λ and the ciphertext C(Ψ + 1); wherein λ = 1,..., Ψ and wherein Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, I is a constant greater than or equal to 2 and less than or equal to n + ζ, e φ is a nondegenerate bilinear map that outputs one element of the cyclic group G T in response to input of η(φ)+ζ(φ) elements γ β of a cyclic group G 1 and n(φ)+ζ(φ) elements γ β * of a cyclic group G 2 where β = 1,..., n(φ) + ζ(φ), i is an integer greater than or equal to 1 and less than or equal to n(φ) + ζ(φ), bi(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ) + ζ(φ) elements of the cyclic group G 1, b i *(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ) + ζ(φ) elements of the cyclic group G 2, δ(i, j) is a Kronecker delta function, e φ (b i (φ), b j *(φ)) = g T τ·τ'·δ(i, j) is satisfied for a generator g T of the cyclic group G T and constants τ and τ', and w(λ) → = (w 1 (λ),..., w n(λ) (λ)) are n(λ)-dimensional vectors consisting of w 1 (λ),..., W n(λ) (λ); the encryption device further comprises a function calculating unit adapted to generate S max function values H S (r, C 2) where S max is a positive integer constant and S = 1,..., S max, each of the function values H S (r, C 2) being obtained by inputting a pair of the random number r and the ciphertext C 2 in each of collision-resistant functions H S where S = 1,..., S max, and at least some of the collision-resistant functions H S are random functions; and at least some of the values of u, υ 2,..., υ ι, υ n(λ)+1 (λ),..., υ n(λ)+ζ(λ) (λ) correspond to at least some of the function values H S (r, C 2) where S = 1,..., S max. a random number generating unit adapted to generate a random number r; a first encryption unit adapted to generate a ciphertext C 2, the ciphertext C 2 being an exclusive OR of a binary sequence dependent on the random number r and a plaintext M, the plaintext M being a binary sequence; a common key generating unit adapted to generate a common key K, the common key being an element of a cyclic group G T; a second encryption unit adapted to encrypt the random number r by common key encryption using the common key K to generate ciphertext C(Ψ + 1); and a third encryption unit adapted to generate a ciphertext C 1 including C 0 = υ ⋅ b 1 0 + ∑ i = 2 I υ ι 0 ⋅ b ι 0, C λ = υ ⋅ ∑ ι = 1 n λ w ι λ ⋅ b ι λ + ∑ ι = n λ + 1 n λ + ζ λ υ ι λ ⋅ b ι λ and the ciphertext C(Ψ + 1); wherein λ = 1,..., Ψ and wherein Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, I is a constant greater than or equal to 2 and less than or equal to n + ζ, e φ is a nondegenerate bilinear map that outputs one element of the cyclic group G T in response to input of η(φ)+ζ(φ) elements γ β of a cyclic group G 1 and n(φ)+ζ(φ) elements γ β * of a cyclic group G 2 where β = 1,..., n(φ) + ζ(φ), i is an integer greater than or equal to 1 and less than or equal to n(φ) + ζ(φ), bi(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ) + ζ(φ) elements of the cyclic group G 1, b i *(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ) + ζ(φ) elements of the cyclic group G 2, δ(i, j) is a Kronecker delta function, e φ (b i (φ), b j *(φ)) = g T τ·τ'·δ(i, j) is satisfied for a generator g T of the cyclic group G T and constants τ and τ', and w(λ) → = (w 1 (λ),..., w n(λ) (λ)) are n(λ)-dimensional vectors consisting of w 1 (λ),..., W n(λ) (λ); the encryption device further comprises a function calculating unit adapted to generate S max function values H S (r, C 2) where S max is a positive integer constant and S = 1,..., S max, each of the function values H S (r, C 2) being obtained by inputting a pair of the random number r and the ciphertext C 2 in each of collision-resistant functions H S where S = 1,..., S max, and at least some of the collision-resistant functions H S are random functions; and at least some of the values of u, υ 2,..., υ ι, υ n(λ)+1 (λ),..., υ n(λ)+ζ(λ) (λ) correspond to at least some of the function values H S (r, C 2) where S = 1,..., S max.