A cryptographic system comprising: a key generation apparatus to generate, as a secret key for an input parameter Y, a secret key including a matrix e as a key element, wherein a product of the matrix e and a matrix A Y determined by the input parameter Y forms a matrix u j for a randomly selected value j in a set [N] including a plurality of values, the matrix u j being among a plurality of matrices u obtained from public parameters PP; an encryption apparatus to generate a ciphertext including cipher elements for respective values included in the set [N]; and a decryption apparatus to decrypt the ciphertext with using the secret key and the cipher element for the value j among cipher elements included in the ciphertext, wherein the matrix A Y is a matrix A v in which a predicate vector v being the input parameter Y is set, wherein the encryption apparatus generates a ciphertext that includes a cipher element in which an attribute vector w is set, in addition to the cipher elements for the respective values, and wherein the key generation apparatus generates the matrix e indicated in formula 1, as the key element, wherein the encryption apparatus generates c 0 indicated in formula 2, c i,γ indicated in formula 3, and c' i indicated in formula 4, as the cipher elements, and wherein the decryption apparatus decrypts the ciphertext by conducting calculation indicated in formula 5 A v ⋅ e = u j mod q , A v : = A ‖ C v ∈ Z q n × 2 m , A ∈ Z q n × m , C v : = ∑ i = 1 L ∑ γ = 0 k v i , γ A i , γ ∈ Z q n × m , v i = ∑ γ = 0 k v i , γ ⋅ 2 γ , v : = v 1 , ... , v L , where each ν i,γ is 0 or 1, where n is an integer not less than 1, m is an integer not less than n , q is an integer larger than 2, and L is an integer not less than 1 c 0 : = A T s + X , s ← U Z q n , X ← R φ ̅ α m , where φ is a probability distribution over Z q := Z / q Z c i , γ : = A i , γ + 2 γ w i B T s + R i , γ T X , w : = w 1 , ... , w L , B ← U Z q n × m , R i , γ T ∈ 0,1 m × m c i ′ : = u i T s + x + M ⋅ " q / 2 " ∈ Z q for i ∈ N , x ← R φ ̅ α , M ∈ 0,1 , where " q /2" is an integer that is the closest to q /2 c v : = ∑ i = 1 L ∑ γ = 0 k v i , γ c i , γ , c : = c 0 ‖ c v , z : = c j ′ − e T c mod q where each α is a positive real-number Gaussian parameter, in the above formulae. a key generation apparatus to generate, as a secret key for an input parameter Y, a secret key including a matrix e as a key element, wherein a product of the matrix e and a matrix A Y determined by the input parameter Y forms a matrix u j for a randomly selected value j in a set [N] including a plurality of values, the matrix u j being among a plurality of matrices u obtained from public parameters PP; an encryption apparatus to generate a ciphertext including cipher elements for respective values included in the set [N]; and a decryption apparatus to decrypt the ciphertext with using the secret key and the cipher element for the value j among cipher elements included in the ciphertext, wherein the matrix A Y is a matrix A v in which a predicate vector v being the input parameter Y is set, wherein the encryption apparatus generates a ciphertext that includes a cipher element in which an attribute vector w is set, in addition to the cipher elements for the respective values, and wherein the key generation apparatus generates the matrix e indicated in formula 1, as the key element, wherein the encryption apparatus generates c 0 indicated in formula 2, c i,γ indicated in formula 3, and c' i indicated in formula 4, as the cipher elements, and wherein the decryption apparatus decrypts the ciphertext by conducting calculation indicated in formula 5 where each ν i,γ is 0 or 1, where n is an integer not less than 1, m is an integer not less than n , q is an integer larger than 2, and L is an integer not less than 1 n is an integer not less than 1, m is an integer not less than n , q is an integer larger than 2, and L is an integer not less than 1 <EOS>