Patent ID: 8897442

Claim:
An encryption device comprising: a random number generating unit that generates a random number r; a first encryption unit that generates 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 function calculating unit that generates S max function values H S (r, C 2 ), where S=1, . . . , S max and S max ≧1, 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 ; a common key generating unit that generates a common key K, the common key being an element of a cyclic group G T ; a second encryption unit that encrypts the random number r by common key encryption using the common key K to generate ciphertext C(Ψ+1); and a third encryption unit that generates a ciphertext C 1 including C(0)=υ·b 1 (0)+Σ ι=2 I υ ι (0)·b ι (0), C(λ)=υ·Σ κ=1 n(λ) w ι (λ)·b ι (λ)+Σ ι=n(λ)+1 n(λ)+ι(λ) υ(λ)·b ι (λ) and the ciphertext C(Ψ+1); 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(0)+ζ(0), e φ is a nondegenerate bilinear map that outputs one element of the cyclic group G T in response to input of n(φ)+ζ(φ) elements γ β (β=1, . . . , n(φ)+ζ(φ) of a cyclic group G 1 and n(φ)+ζ(φ) elements γ β *(β=1, . . . , n(φ)+ζ(φ)) of a cyclic group G 2 , i is an integer greater than or equal to 1 and less than or equal to n(φ)+ζ(φ), b i (φ) 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 τ′, w(λ) → =(w 1 (λ), . . . , w n(λ) (λ)) are n(λ)-dimensional vectors each consisting of w 1 (λ), . . . , w n (λ)(λ), and at least some of the values of υ, υ 2 (0), . . . , υ I (0), υ n(λ)+1 (λ), . . . , υ n(λ)+ζ(λ) (λ) correspond to at least some of the function values H S (r, C 2 ).