A cryptographic processing system comprising a key generation device, an encryption device, and a decryption device, and serving to execute a cryptographic process using a basis B t and a basis B* t for each integer t = 0,..., d (d is an integer of 1 or more), wherein the key generation device includes a first information input part which takes as input, a variable p(i) for each integer i = 1,..., L (L is an integer of 1 or more), which variable p(i) is either one of a positive tuple (t, v → i) and a negative tuple ¬(t, v → i) of identification information t (t is any one integer of t = 1,..., d) and an attribute vector v → i:= (v i,i') (i' = 1,..., n t where n t is an integer of 1 or more), and a predetermined matrix M having L rows and r columns (r is an integer of 1 or more), and a decryption key generation part which generates an element k* 0, and an element k* i for each integer i = 1..., L, based on a column vector s →T:= (s 1,..., s L) T:= M·f →T generated based on a vector f → and a vector w →, each having r pieces of elements, and the matrix M inputted by the first information input part; a value s 0:= w → ·f →; and a predetermined value θ i (i = 1,..., L), the decryption key generation part being configured to generate the element k* 0 by setting a value -s 0 as a coefficient for a basis vector b* 0,p (p is a predetermined value) of the basis B* 0 and by setting a predetermined value κ as a coefficient for a basis vector b* 0,q (q is a predetermined value different from prescribed p), and to generate the element k* i for each integer i = 1,..., L, when the variable p(i) is a positive tuple (t, v → i), by setting s i + θ i v i,1 as a coefficient for a basis vector b* t,1 of the basis B* t indicated by identification information t of the positive tuple, and by setting θ i v i,i' as a coefficient for a basis vector b* t,i' indicated by the identification information t and each integer i' = 2,..., n t, and when the variable p(i) is a negative tuple ¬(t, v → i), by setting s i v i,i' as a coefficient for the basis vector b* t,j' indicated by the identification information t of the negative tuple and by each integer i' = 1,..., n t, wherein the encryption device includes a second information input part which takes as input, an attribute set Γ having the identification information t and an attribute vector x → t:= (x t,i') (i' = 1,..., n t where n t is an integer of 1 or more) for at least one integer t = 1,..., d, and an encrypted data generation part which generates an element c 0, and an element c t concerning each identification information t included in the attribute set Γ, based on the attribute set Γ inputted by the second information input part, the encrypted data generation part being configured to generate the element c 0 where a random value δ is set as a coefficient for a basis vector b 0,p (p is prescribed p) of a basis B 0, and where a predetermined value ζ is set as a coefficient for a basis vector b 0,q (q is prescribed q) of a basis B 0, and to generate the element c t where x t,i' multiplied by the random value δ is set as a coefficient for a basis vector b t,i' (i' = 1,..., n t) of the basis B t for each identification information t included in the attribute set Γ, and wherein the decryption device includes a data acquisition part which acquires encrypted data c including the elements c 0 and c t and the attribute set Γ, the elements c 0 and c t being generated by the encrypted data generation part, a decryption key acquisition part which acquires a decryption key sk s including the elements k* 0 and k* i and the variable number p(i), the elements k* 0 and k* i being generated by the decryption key generation part, a complementary coefficient calculation part which, based on the attribute set Γ included in the encrypted data c acquired by the data acquisition part, and the variable ρ(i) included in the decryption key sk s acquired by the decryption key acquisition part, specifies, among integers i = 1,..., L, a set I of an integer i for which the variable ρ(i) is a positive tuple (t, v → i) and with which an inner-product of v → i of the positive tuple and x → t included in Γ indicated by identification information t of the positive tuple becomes 0, and an integer i for which the variable ρ(i) is a negative tuple ¬(t, v → i) and with which an inner-product of v → i of the negative tuple and x → t included in Γ indicated by identification information t of the negative tuple does not become 0; and calculates a complementary coefficient α i with which a total of α i S i for i included in the set I specified becomes s 0, and a pairing operation part which calculates a value K = g T ζχ by conducting a pairing operation indicated in Formula 1 for the elements c 0 and c t included in the encrypted data c and the elements k* 0 and k* i included in the decryption key sk s, based on the set I specified by the complementary coefficient calculation part and on the complementary coefficient α i calculated by the complementary coefficient calculation part. K: = e c 0, k 0 * ⋅ ∏ i ∈ I ∧ ρ i = t, v → i e c t, k i * α i ⋅ ∏ i ∈ I ∧ ρ i = ¬ t, v → i e c t, k i * α i / v → i ⋅ x → i