A cryptographic processing system comprising d, wherein d is an integer of 1 or more, units of key generation devices, 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 at least one integer t = 1,..., d, wherein each key generation device of the d units of key generation devices includes a first information input part which takes as input attribute information x → t:= (x t,i), wherein i = 1,..., n t where n t is an integer of 1 or more, for an integer t among integers t = 1,..., d which is predetermined for each key generation device, a key element generation part which generates a key element k* t including a vector indicated in Formula 1 based on the integer t, the attribute information x → t inputted by the first information input part, a predetermined value δ, and a basis vector b* t,i, with i = 1,..., 2n t, of the basis B* t, and a decryption key transmission part which transmits to the decryption device, a decryption key usk including the key element k* t generated by the key element generation part and the attribute information x → t, wherein the encryption device includes a second information input part which takes as input a variable ρ(i) for each integer i = 1,..., L, wherein L is an integer of 1 or more, which variable ρ(i) is either one of a positive tuple (t, v → i and a negative tuple ¬(t, v → i) of the identification information t, wherein t is any one integer of t = 1,..., d, and attribute information v → i:= (v i,i'), with i' = 1,..., n t; and a predetermined matrix M having L rows and r columns, wherein r is an integer of 1 or more, a vector generation part (232, 233) which generates a column vector s →T:= (s 1,..., s L) T:= M·f →T based on a vector f → having r pieces of elements and the matrix M inputted by the second information input part, and generates a column vector (s → ') T:= (s 1 ',..., s L ') T:= M·(f → ') T based on the matrix M and a vector f → ' having r pieces of elements and satisfying so = h → ·(f → ') T where s 0 = h → ·f →T, a cipher element c i generation part which, for each integer i = 1,..., L and based on the column vector s →T and the column vector (s → ') T which are generated by the vector generation part, and predetermined values θ i and θ i ' for each integer i = 1,..., L, generates a cipher element c i including a vector indicated in Formula 2, when the variable ρ(i) is a positive tuple (t, v → i), using a basis vector b t,i', with i' = 1,..., 2n t, of the basis B t indicated by identification information t of the positive tuple, and generates a cipher element c i including a vector indicated in Formula 3, when the variable ρ(i) is a negative tuple ¬(t, v → i), using a basis vector b t,i, with i = 1,..., 2n t, indicated by identification information t of the negative tuple, and a ciphertext transmission part which transmits to the decryption device, a ciphertext ct s including: the cipher element c i generated for each integer i = 1,..., L by the cipher element c i generation part; the variable ρ(i); and the matrix M, and wherein the decryption device includes a decryption key reception part which receives the decryption key usk transmitted by the decryption key transmission part of at least one key generation device among the d units of key generation devices, a data reception part which receives the ciphertext ct s transmitted by the ciphertext transmission part, a complementary coefficient calculation part which, based on the attribute information x → t included in the decryption key usk received by the decryption key reception part, and the variable ρ(i) included in the ciphertext ct s received by the data reception 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), the decryption key usk including x → t indicated by identification information t of the positive tuple being received by the decryption key reception part, and with which an inner-product of v → i of the positive tuple and the attribute information x → t indicated by the 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), the decryption key usk including x → t indicated by identification information t of the negative tuple being received by the decryption key reception part, and with which an inner-product of v → i of the negative tuple and the attribute information x → t indicated by the identification information t of the negative tuple does not become 0; and calculates, concerning i included in the set I specified, a complementary coefficient α i with which a total of α i M i based on M i which is an element on an i-th row of the matrix M included in the ciphertext ct s becomes the predetermined vector h →, and a pairing operation part which calculates predetermined information K by conducting a pairing operation indicated in Formula 4 for the cipher element c i included in the ciphertext ct s and the key element k* t included in the decryption key usk based on the set I and the complementary coefficient α i which are calculated by the complementary coefficient calculation part. δ + 1 x t, 1,..., δ + 1 x t, n t, { n t − δx t, 1,..., − δx t, n t, {, 0,..., 0 n t B t * s i + θ i v i, 1, θ i v i, 2,..., θ i v i, n t, { n t s i ′ + θ i, 1 ′, θ i ′ v i, 2,..., θ i ′ v i, n t {, 0,..., 0 n t B t s i v i, 1,..., s i v i, n t, { n t s t ′ v i, 1,..., s ′ v i, n t, { 0,..., 0 n t B t K: = ∏ i ∈ I ⋀ ρ i = t v → i e c i k t * α i ⋅ ∏ i ∈ I ⋀ ρ i = ¬ t v → i e c i k t * α i / v → i ⋅ x → t