1. A signature processing system comprising:

a key generation device, a signature device, and a verification device, and serving to execute a signature process using a

basis Bt and a basis B*t for each integer t=0, . . . , d+1 (d is an integer of 1 or more),

wherein the key generation device includes

a first information input part which takes as input an attribute set ? including identification information t and attribute

information x?t:=(xt,i) (i=1, . . . , nt where nt is an integer of 1 or more) for at least one integer t=1, . . . , d,

a key element 0 generation part which generates a key element k*0 where a predetermined value ? is set as a coefficient for a basis vector b*0,1 of a basis B*0,

a key element t generation part which generates a key element k*t where ?xt,i (i=1, . . . , nt) obtained by multiplying the attribute information x?t by the predetermined value ? is set as a coefficient for a basis vector b*t,i (i=1, . . . , nt) of the basis B*t, concerning each identification information t included in the attribute set ? inputted by the first information input part,

a key element d+1 generation part which generates a key element k*d+1,1 where the predetermined value ? is set as a coefficient for a basis vector b*d+1,1 of a basis B*d+1, and a key element k*d+1,2 where the predetermined value ? is set as a coefficient for a basis vector b*d+1,2 of the basis B*d+1, and

a signing key transmission part which transmits, to the signature device, a signing key sk? including: the key element k*0 generated by the key element 0 generation part; the key element k*t generated by the key element t generation part concerning each identification information t included in the attribute set

F; the key element k*d+1,1 and the key element k*d+1,2 which are generated by the key element d+1 generation part; and the attribute set ?,

wherein the signature device includes

a signature element 0 generation part which generates a signature element s*0 including the key element k*0 included in the signing key sk?,

a signature element i generation part which generates, for each integer i=1 . . . , L, a signature element s*i including ?ik*t obtained by multiplying the key element k*t included in the signing key sk? by a value ?i, by setting the value ?i to satisfy ?i:=?i when the integer i is included in the set I specified by the complementary coefficient calculation part and the variable ?(i)

is a positive tuple (t, v?i); by setting the value ?i to satisfy ?i:=?i/(v?iÂ·x?t) when the integer i is included in the set I and the variable ?(i) is a negative tuple (t, v?i); and by setting the value ?i to satisfy ?i:=0 when the integer i is not included in the set I,

a signature element L+1 generation part which generates a signature element s*L+1 including a sum of the key element k*d+1,1 included in the signing key sk? and m?Â·k*d+1,2 obtained by multiplying the key element k*d+1,2 by a value m? generated using the message m, and

a signature data transmission part which transmits, to the verification device, signature data ? including: the signature

element s*0 generated by the signature element 0 generation part; the signature element s*i generated for each integer i=1, . . . , L by the signature element i generation part; the signature element s*L+1 generated by the signature element L+1 generation part; the message m; the variable ?(i); and the matrix M, and

wherein the verification device includes

a data acquisition part which acquires the signature data ? transmitted by the signature data transmission part,

a verification element 0 generation part which generates a verification element c0 by setting, as a coefficient for a basis vector b0,1 of a basis B0, ?s0?sL+1 calculated from a value s0:=h?Â·f? and a predetermined value sL+1, the value s0:=h?Â·f? being generated using a vector f? having r pieces of elements, and the vector h?,

a verification element i generation part which, for each integer i=1, . . . ,L and using a column vector s?T:=(s1, . . . , sL)T:=MÂ·f?T generated based on the vector f? and the matrix M which is included in the signature data ? acquired by the data acquisition part, and a predetermined number

?i for each integer i=1, . . . , L, generates a verification element ci, when the variable ?(i) is a positive tuple (t, v?i), by setting si+?ivi,1 as a coefficient for a basis vector bt,1 of the basis Bt indicated by identification information t of the positive tuple and by setting ?ivi,i? (i?=2, . . . , nt) as a coefficient for a basis vector bt,i? (i?=2, . . . , nt), and generates a verification element ci, when the variable ? (i) is a negative tuple (t, v?i), by setting sivi,i? (i?=1, . . . , nt) as a coefficient for the basis vector bt,i? (i?=1, . . . , nt) indicated by identification information t of the negative tuple,

a verification element L+1 generation part which generates a verification element cL+1 by setting sL+1??L+1m? calculated from the predetermined value sL+1, the value m?, and a predetermined value ?L+1 as a coefficient for a basis vector bd+1,1 of a basis Bd+1, and by setting the predetermined value ?L+1 as a coefficient for a basis vector bd+1,2, and

a pairing operation part which verifies an authenticity of the signature data a by conducting a pairing operation ?i=0L+1e(ci,s*i) for the verification element c0 generated by the verification element 0 generation part, the verification element ci generated by the verification element i generation part, the verification element cL+1 generated by the verification element L+1 generation part, and the signature elements s*0, s*i, and s*L+1 included in the signature data ?.