SIGNATURE PROCESSING SYSTEM, KEY GENERATION DEVICE, SIGNATURE DEVICE, VERIFICATION DEVICE, SIGNATURE PROCESSING METHOD, AND SIGNATURE PROCESSING PROGRAM

• US 20130322627A1
• Filed: 12/08/2011
• Published: 12/05/2013
• Est. Priority Date: 01/25/2011
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Corporation, Nippon Telegraph and Telephone Corporation
• Original Assignee: Mitsubishi Electric Corporation, Nippon Telegraph and Telephone Corporation
• Inventors: Takashima, Katsuyuki, Okamoto, Tatsuaki
• Granted Patent: US 9,106,408 B2
• Time in Patent Office: Days
• US Class Current: 380/255
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

The object is to provide an attribute-based signature scheme which is flexible in the design and which supports a non-monotone predicate. An access structure is constituted by applying the inner-product of the attribute vectors to a non-monotone span program. This access structure is flexible in the design of the span program and in the design of the attribute vectors, providing high flexibility in the design of access control. By incorporating the concept of secret distribution in the access structure, the attribute-based signature scheme which supports the non-monotone predicate is realized.

Claims

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 B_t 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;

=(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,

a key element 0 generation part which generates a key element k*₀ where a predetermined value δ

is set as a coefficient for a basis vector b*_0,1 of a basis B*₀,

a key element t generation part which generates a key element k*_t where δ

x_t,i (i=1, . . . n_t) 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, . . . , n_t) 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+t, and

a signing key transmission part which transmits, to the signature device, a signing key sk_Γ

including;

the key element k*₀ 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 Γ

;

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 second information input part which takes as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m,

a signing key acquisition part which acquires the signing key sk_Γ

transmitted by the signing key transmission part,

a complementary coefficient calculation part which, based on the variable ρ

(i) inputted by the second information input part and the attribute set Γ

included in the signing key sk_Γ

acquired by the signing 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 the attribute set Γ

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 the attribute set Γ

indicated by 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 α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted by the second information input part becomes a predetermined vector h^→

,

a signature element 0 generation part which generates a signature element s*₀ including the key element k*₀ 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 y_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*₀ 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 c₀ by setting, as a coefficient for a basis vector b_0,1 of a basis B₀, −

s₀−

s_L+1 calculated from a value s₀;

=h^→

·

f^→

and a predetermined value s_L+1, the value s₀;

=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<sup>→

T</sup>;

=(x₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> 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 c_i, when the variable ρ

(i) is a positive tuple (t, v^→

_i), by setting s_i+θ

_iv_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 θ

_iv_i,i′

(i′

=2, . . . , n_t) as a coefficient for a basis vector b_t,i′

(i′

=2, . . . , n_t), and generates a verification element c_i, when the variable ρ

(i) is a negative tuple (t, v^→

_i), by setting s_iv_i,i′

(i′

=1, . . . , n_t) as a coefficient for the basis vector b_t,i′

(i′

=1, . . . , n_t) indicated by identification information t of the negative tuple,

a verification element L+1 generation part which generates a verification element c_L+1 by setting s_L+1−

θ

_L+1m′

calculated from the predetermined value s_L+1, the value m′

, and a predetermined value θ

_L+1 as a coefficient for a basis vector b_d+1,1 of a basis B_d+1, and by setting the predetermined value θ

_L+1 as a coefficient for a basis vector b_d+1,2, and

a pairing operation part which verifies an authenticity of the signature data σ

by conducting a pairing operation Π

_i=0^L+1e(c_i,s*_i) for the verification element c₀ generated by the verification element 0 generation part, the verification element c_i generated by the verification element i generation part, the verification element c_L+1 generated by the verification element L+1 generation part, and the signature elements s*₀, s*_i, and s*_L+1 included in the signature data σ

.

2. The signature processing system according to claim 1, which executes the signature process using

a basis B₀ having at least the basis vector b_t,i (i=1, . . . , 1+u₀, . . . , 1+u₀+w₀, . . . , 1+u₀+w₀+z₀),

the basis B_t (t=1, . . . , d) having at least the basis vector b_t,i (i=1, . . . , n_t, . . . , n_t+u_t, . . . , n_t+u_t+w_t, . . . , n_t+u_t+w_t+z_t) (u_t, w_t, and z_t are each an integer of 1 or more),

the basis B_d+1 having at least the basis vector (i=1, 2, . . . , 2+u_d+1, . . . , 2+u_d+1+w_d+1, . . . , 2+u_d+1+w_d+1+z_d+1),

the basis B*₀ having at least a basis vector b*_t,i (i=1, . . . , 1+u₀, . . . , 1+i₀+w₀, . . . , 1+u₀+w₀+z₀),

the basis B*_t (t=1, . . . , d) having at least the basis vector b*_t,i (i=1, . . . , n_t, . . . , n_t+u_t, . . . n_t+u_t+w_t, . . . , n_t+u_t+w_t+z_t) (u_t, w_t, and z_t are each an integer of 1 or more), and

the basis B*_d+1 having at least the basis vector b*_t,i (i=1, 2, . . . , 2+u_d+1, . . . , 2+u_d+1+w_d+1, . . . , 2+u_d+1+w_d+1+z_d+1),

wherein, in the key generation device,

the key element 0 generation part generates the key element k*₀ indicated in Formula 1 based on a random number δ

and a random number φ

_0,i (i=1, . . . , w₀),

the key element t generation part generates the key element k*_i indicated in Formula 2 for each identification information t included in the attribute set Γ

based on the random number δ and

a random number φ

_i,i (i=1, . . . , w_t), and

the key element d+1 generation part generates the key element k*_d+1,1 and the key element k*_d+1,2 which are indicated in Formula 3 based on the random number δ

, a random number φ

_d+1,1,i (i=1, . . . , w_d+1), and a random number φ

_d+1,2,i (i=1, . . . , w_d+1),

wherein, in the signature device,

the signature element 0 generation part generates the signature element s*₀ indicated in Formula 4 based on a random number ξ

,

the signature element i generation part generates the signature element s*_i indicated in Formula 5 for each integer i=1, . . . , L based on the random number ξ

, and

the signature element L+1 generation part generates the signature element s*_L+1 indicated in Formula 6 based on the random number ξ and

the value m′

, and

wherein, in the verification device,

the verification element 0 generation part generates the verification element c₀ indicated in Formula 7 based on the value s₀, the random number s_L+1, and a random number η

_0,i (i=1, . . . , z₀),

the verification element i generation part generates the verification element c_i indicated in Formula 8 for each integer i=1, . . . , L based on the column vector s<sup>→

T</sup>, the random number θ

_i, and a random number η

_i,i′

(i=1, . . . , L;

i′

=1., . . . , z_t), and

the verification element L+1 generation part generates the element c_L+1 indicated in Formula 9 based on the random number S_L+1 the random number θ

_L+1, a random number η

<sub>L+1,i′

(i′

=</sub>1, . . . , z_d+1), and the value m′

.

3. The signature processing system according to claim 1,

wherein, in the signature device,

the signature element L+1 generation part generates the signature element s*_L+1 using a hash value obtained upon input of the message m, the matrix M, and the variable ρ

(i) for each integer i=1, . . . , L, as the value m′

, and

wherein, in the verification device,

the verification element L+1 generation part generates the verification element c_L+1 using the hash value as the value m′

.

4. A key generation device which generates a signing key sk_Γ

, in a signature processing system which executes a signature process using a basis B_t and a basis B*_t for each integer t=0, . . . , d+1 (d is an integer of 1 or more), the key generation device comprising;

a first information input part which takes as input an attribute set Γ

including identification information t and attribute information 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;

a key element 0 generation part which generates a key element k*₀ where a predetermined value δ

is set as a coefficient for a basis vector b*_0,1 of a basis B*₀;

a key element t generation part which generates a key element k*_t where δ

x_t,i (i=1, . . . , n_t) 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, . . . , n_t) 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 S 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 a signature device, the signing key sk_Γ

including;

the key element k*₀ 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 Γ

;

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 Γ

.

5. A signature device which generates signature data σ

, in a signature processing system which executes a signature process using a basis B_t and a basis B*_t for each integer t=0, . . . , d+1 (d is an integer of 1 or more), the signature device comprising;

a signing key acquisition part which acquires, as a signing key sk_Γ

,

an attribute set Γ

including identification information t and attribute information 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,

a key element k*₀ where a predetermined value δ

is set as a coefficient for a basis vector b*_0,1 of a basis B*₀,

a key element k*_t where δ

x_t,i (i=1, . . . , n_t) 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, . . . , n_t) of the basis B*_t, concerning each identification information t included in the attribute set Γ

,

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;

a second information input part which takes as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m;

a complementary coefficient calculation part which, based on the variable ρ

(i) inputted by the second information input part and the attribute set Γ

included in the signing key sk_Γ

acquired by the signing 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 the attribute set Γ

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 the attribute set Γ

indicated by 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 α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted by the second information input part becomes a predetermined vector h^→

;

a signature element 0 generation part which generates a signature element s*₀ including the key element k*₀ 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 a verification device, the signature data σ

including;

the signature element s*₀ generated by the signature element 0 generation part;

the signature element s*, 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.

6. A verification device which verifies signature data σ

, in a signature processing system which executes a signature process using a basis B_t and a basis B*_t for each integer t=0, . . . , d+1 (d is an integer of 1 or more), the verification device comprising;

a data acquisition part which acquires the signature data σ

including;

a signature element s*₀;

a signature element s*, for each integer i=1, . . . , L;

a signature element s*_L+1;

a message m;

a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i′

=1, . . . , n_t); and

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more);

a verification element 0 generation part which generates a verification element c₀ by setting, as a coefficient for a basis vector b_0,1 of a basis B₀, −

s₀−

δ

_L+1 calculated from a value s₀;

=h^→

·

f^→

and a predetermined value s_L+1, the value s₀;

=h^→

·

f^→

being generated using a vector f^→

having r pieces of elements, and a vector h^→

having r pieces of elements;

a verification element i generation part which, for each integer i=1, . . . , L and using a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> 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 c_i, when the variable ρ

(i) is a positive tuple (t, v^→

_i), by setting s_i+θ

_iv_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 θ

_iv_i,i′

(i′

=2, . . . , n_t) as a coefficient for a basis vector b_t,i′

(i′

=2, . . . , n_t), and generates a verification element c_i, when the variable ρ

(i) is a negative tuple (t, v^→

_i), by setting s_tv<sub>i,i′

) (i′

=</sub>1, . . . , n_t) as a coefficient for the basis vector b_t,i′

(i′

=1, . . . , n_t) indicated by identification information t of the negative tuple;

a verification element L+1 generation part which generates a verification element c_L+1 by setting s_L+1−

θ

_L+1m′

calculated from the predetermined value s_L+1, a value m′

calculated from the message m, and a predetermined value θ

_L+1, as a coefficient for a basis vector b_d+1,1 of a basis B_d+1, and by setting the predetermined value θ

_L+1 as a coefficient for a basis vector b_d+1,2; and

a pairing operation part which verifies an authenticity of the signature data σ

by conducting a pairing operation Π

_i=0^L+1e(c_i,s*_i) for the verification element c₀ generated by the verification element 0 generation part, the verification element c_i generated by the verification element i generation part, the verification element c_L+1 generated by the verification element L+1 generation part, and the signature elements s*₀, s*_i, and s*_L+1 included in the signature data σ

.

7. A signature processing system comprising d (d is an integer of 1 or more) units of key generation devices, a signature device, and a verification device, and serving to execute a signature process using a basis B_t and a basis B*_t for at least one integer t=0, . . . , d,

wherein each 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) (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 of the key generation devices,

a key element generation part which, for the integer t and each integer j=1, 2, generates a key element k*_t,j including a vector indicated in Formula 10 based on the attribute information x^→

_t inputted by the first information input part, a predetermined value δ

_j, and a basis vector b*_t,i (i=1, . . . , 2n_t) of the basis B*_t, and

a signing key transmission part which transmits, to the signature device, a signing key usk including;

the key element k*_t,j generated by the key element generation part; and

the attribute information x^→

_t,

wherein the signature device includes

a second information input part which takes as input a variable ρ

(i) for each integer i=1, . . . , L (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^→

_t) of the identification information t (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m,

a signing key acquisition part which acquires the signing key usk transmitted by the signing key transmission part of at least one key generation device among the d units of key generation devices,

a complementary coefficient calculation part which, based on the variable ρ

(i) inputted by the second information input part and the attribute information x^→

_t included in the signing key usk acquired by the signing 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), the signing key usk including x^→

_t indicated by identification information t of the positive tuple being acquired by the signing key acquisition 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 signing key usk including x^→

_t indicated by identification information t of the negative tuple being acquired by the signing key acquisition 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 α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted by the second information input part becomes a predetermined vector h^→

,

a signature element generation part which generates, for each integer i=1, . . . , L, a signature element s*_i including a vector indicated in Formula 11 using the basis vector b*_t,i (i=2n_t+1, 2n_t+2) of the basis B*_t, based on a key element k*_t,1 and a key element k*_t,2 included in the signing key usk, predetermined values ξ

₁, E, and μ

, and a value m′

calculated from the message m, by setting a 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 y_i;

=0 when the integer i is not included in the set I, and

a signature data transmission part which transmits, to the verification device, signature data σ

including;

the signature element s*_i generated for each integer i=1, . . . , L by the signature element 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 vector generation part which generates a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> based on a vector f^→

having r pieces of elements and the matrix M included in the signature data σ

acquired by the data acquisition part, and generates a column vector (s^→

′

)^T;

=(s₁′

, . . . , s_L′

)^T;

=M·

(f<sup>→

T</sup>′

) based on the matrix M and a vector f^→

′

having r pieces of elements and satisfying s₀=h′

·

(f^→

′

)^T where s₀=h^→

·

f<sup>→

T</sup>,

a verification element generation part which, for each integer i=1, . . . , L and based on the column vector s<sup>→

T</sup> and the column vector (s^→

′

)^T which are generated by the vector generation part, and predetermined values θ

_i, θ

_i′

, θ

_i″

, and σ

_i for each integer i=1, . . . , L, generates a verification element c_i including a vector indicated in Formula 12, when the variable ρ

(i) is a positive tuple (t, v^→

_i), using a basis vector b_t,i′

(i=1, . . . , 2n_t+2) of the basis B_t indicated by identification information t of the positive tuple, and generates a verification element c_i including a vector indicated in Formula 13, when the variable ρ

(i) is a negative tuple (t, v^→

_i), using a basis vector b_t,i (i=1, . . . , 2n_t+2) indicated by identification information t of the negative tuple, and

a pairing operation part which verifies an authenticity of the signature data σ

by conducting a pairing operation Π

_i=1^Le(c_i,s*_i) for the verification element c_i generated by the verification element generation part, and the signature element s*_i included in the signature data σ

.

8. The signature processing system according to claim 7, which executes the signature process using, for at least one integer t=1, . . . , d, the basis B_t having at least the basis vector b_t,i (i=1, . . . , 2n_t+2, 2n_t+2+u_t, . . . , 2n_t+2+u_t+w_t, . . . , 2n_t+2+u_t+w_t+z_t) (where u_t, wi_t, and z_t are each an integer of 1 or more), and the basis B*_t having at least the basis vector b*_t,i (i=1, . . . , 2n_t+2, . . . , 2n_t+2+u_t, . . . , 2n_t+2+u_t+w_t, . . . , 2n_t+2+u_t+w_t+z_t),

wherein, in the key generation device,

the key element k*_t,j indicated in Formula 14 is generated for the integer t and each integer j=1, 2 based on the attribute information x^→

_t, the predetermined values δ and

Δ

, and a random number φ

_t,j,i (j=1, 2;

i=1, . . . , w_t),

wherein, in the signature device,

the signature element generation part generates, for each integer i=1, . . . , L, the signature element s*_i indicated in Formula 16 using r*_i, γ

_i, y^→

_i;

=(y_i,i) (i=1, . . . , n_t), and y′

^→

_i;

=(y′

_i,i) (i=1, . . . , n_t) indicated in Formula 15, based on the key element k*_t,1 and the key element k*_t,2, random numbers ξ

₁ and ξ

₂, predetermined values E, π

, π

′

, and μ

, and the value m′

, and

wherein, in the verification device,

the verification element generation part, for each integer i=1, . . . , L and based on the column vector s<sup>→

T</sup> and the column vector (s^→

′

)^T, random numbers θ

_i, θ

_i′

, and θ

_i″

, the predetermined value σ

_i, and a random number η

_i,i′

(i=1, . . . , L;

=1, . . . , z_t), generates the verification element c_i indicated in Formula 17 when the variable ρ

(i) is a positive tuple (t, v^→

_i), and generates the verification element c_i indicate in Formula 18 when the variable ρ

(i) is a negative tuple (t, v^→

_i).

9. The signature processing system according to claim 7,

wherein, in the signature device,

the signature element generation part generates the signature element s*_i using a hash value obtained upon input of the message m, the matrix M, and the variable ρ

(i) for each integer i=1, . . . , L, as the value m′

, and

wherein, in the verification device,

the verification element generation part generates the verification element c_i using the hash value as the value m′

.

10. A key generation device which generates a signing key usk, in a signature processing system which executes a signature process using a basis B_t and a basis B*_t for at least one integer t=1, . . . , d, the key generation device comprising:

a first information input part which takes as input attribute information x^→

_t;

=(x_t,i) (i=1, . . . , n_t) for a predetermined integer t among integers t=1, . . . , d;

a key element generation part which, for the integer t and each integer h=1, 2, generates a key element k*_t,j including a vector indicated in Formula 19, based on the attribute information x^→

_t inputted by the first information input part, a predetermined value δ

_j, and a basis vector b*_t,i (i=1, . . . , 2n_t) of the basis B*_t; and

a signing key transmission part which transmits the signing key usk including;

the key elements k*_t,j generated by the key element generation part; and

the attribute information x^→

_t, to a signature device.

11. A signature device which generates signature data σ

, in a signature processing system which executes a signature process using a basis B_t and a basis B*_t for at least one integer t=1, . . . , d, the signature device comprising;

a signing key acquisition part which, for at least some one of integers t of t=1, . . . , d, and each integer j=1, 2 and based on attribute information x^→

_t;

=(x_t,i) (i=1, . . . , n_t), a predetermined value δ

_j, and a basis vector b*_t,i (i=1, . . . , 2n_t) of the basis B*_t, acquires a signing key usk including;

a key element k*_t,j generated to include a vector indicated in Formula 20; and

the attribute information x^→

_t;

a second information input part which takes as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m;

a complementary coefficient calculation part which, based on the variable ρ

(i) inputted by the second information input part and the attribute information x^→

_t included in the signing key usk acquired by the signing 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), the signing key usk including x^→

_t indicated by identification information t of the positive tuple being acquired by the signing key acquisition 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 signing key usk including x^→

_t indicated by identification information t of the negative tuple being acquired by the signing key acquisition 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 v^→

_i and x^→

_t are is not equal; and

calculates, concerning i included in the set I specified, a complementary coefficient α

_i with which a total of α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted by the second information input part becomes a predetermined vector h^→

;

a signature element generation part which generates, for each integer i=1, . . . , L, a signature element s*, including a vector indicated in Formula 21 using the basis vector b*_t,i (i=2n_t+1, 2n_t+2) of the basis B*_t, based on a key element k*_t,1 and a key element k*_t,2 included in the signing key usk, predetermined values ξ

₁, E, and μ

, and a value m′

calculated from the message m, by setting a 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; and

a signature data transmission part which transmits, to a verification device, the signature data σ

including;

the signature element s*_i generated for each integer i=1, . . . , L by the signature element generation part;

the message m;

the variable ρ

(i); and

the matrix M.

12. A verification device which verifies signature data σ

, in a signature processing system which executes a signature process using a basis B_t and a basis B*_t for at least one integer t=1, . . . , d, the verification device comprising;

a data acquisition part which acquires the signature data σ

including;

a signature element s*, for each integer i=1, . . . , L;

a message m;

a variable ρ

(i) for each integer i=1, L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i′

=1, . . . , n_t); and

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more);

a vector generation part which generates a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> based on a vector f^→

having r pieces of elements and the matrix M included in the signature data σ

acquired by the data acquisition part, and generates a column vector (s^→

′

)^T;

=(s₁′

, . . . , s_L′

)^T;

=M·

(f^→

′

)^T based on the matrix M and a vector f^→

′

having r pieces of elements and satisfying s₀=h^→

·

(f^→

′

)^T where s₀=h^→

·

f<sup>→

T</sup>;

a verification element generation part which, for each integer i=1, . . . , L and based on the column vector s<sup>→

T</sup> and the column vector (s^→

′

)^T which are generated by the vector generation part, and predetermined values θ

_i, θ

_i′

, θ

_i″

, and σ

_i for each integer i=1, . . . , L, generates a verification element c_i including a vector indicated in Formula 22, when the variable ρ

(i) is a positive tuple (t, v^→

_i), using a basis vector b_t,i′

(i′

=1, . . . , 2n_t+2) of the basis B_t indicated by identification information t of the positive tuple, and generates a verification element c_i including a vector indicated in Formula 23, when the variable ρ

(i) is a negative tuple (t, v^→

_i), using a basis vector b_t,i (i=1, . . . , 2n_t+2) indicated by identification information t of the negative tuple; and

a pairing operation part which verifies an authenticity of the signature data σ

by conducting a pairing operation Π

_i=1^Le(c_i,s*_i) for the verification element c_i generated by the verification element generation part, and the signature element s*_i included in the signature data σ

.

13. A signature processing method of executing a signature process using a basis B_t and a basis B*_t for each integer t=0, . . . , d+1 (d is an integer of 1 or more), comprising:

a first information input step of, with a key generation device, taking as input an attribute set Γ

including identification information t and attribute information 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;

a key element 0 generation step of, with the key generation device, generating a key element k*₀ where a predetermined value δ

is set as a coefficient for a basis vector b*_0,1 of a basis B*₀;

a key element t generation step of, with the key generation device, generating a key element k*_t where δ

x_t,i (i=1, . . . , n_t) 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, . . . , n_t) of the basis B*_t, concerning each identification information t included in the attribute set Γ

inputted in the first information input step;

a key element d+1 generation step of, with the key generation device, generating 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 S is set as a coefficient for a basis vector b*_d+1,2 of the basis B*_d+1;

a signing key transmission step of, with the key generation device, transmitting, to a signature device, a signing key sk_Γ

including;

the key element k*₀ generated in the key element 0 generation step;

the key element k*_t generated in the key element t generation step concerning each identification information t included in the attribute set Γ

;

the key element k*_d+1,1 and the key element k*_d+1,2 which are generated in the key element d+1 generation step; and

the attribute set Γ

;

a second information input step of, with the signature device, taking as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

;

=(v_i,i′

) (i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m;

a signing key acquisition step of, with the signature device, acquiring the signing key sk_Γ

transmitted in the signing key transmission step;

a complementary coefficient calculation step of, with the signature device, based on the variable ρ

(i) inputted in the second information input step and the attribute set Γ

included in the signing key sk_Γ

acquired in the signing key acquisition step, specifying, 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 the positive tuple and x^→

_t included in the attribute set Γ

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 the attribute set Γ

indicated by identification information t of the negative tuple does not become 0; and

calculating, concerning i included in the set I specified, a complementary coefficient α

_i with which a total of α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted in the second information input step becomes a predetermined vector h^→

;

a signature element 0 generation step of, with the signature device, generating a signature element s*₀ including the key element k*₀ included in the signing key sk_Γ

;

a signature element i generation step of, with the signature device, generating, 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 in the complementary coefficient calculation step 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 step of, with the signature device, generating 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;

a signature data transmission step of with the signature device, transmitting, to a verification device, signature data σ

including;

the signature element s*₀ generated in the signature element 0 generation step;

the signature element s*, generated for each integer i=1, L in the signature element i generation step;

the signature element s*_L+1 generated in the signature element L+1 generation step;

the message m;

the variable ρ

(i); and

the matrix M;

a data acquisition step of, with the verification device, acquiring the signature data σ

transmitted in the signature data transmission step;

a verification element 0 generation step of, with the verification device, generating a verification element c₀ by setting, as a coefficient for a basis vector b_0,1 of a basis B₀, −

s₀−

s_L+1 calculated from a value s₀;

=h^→

·

f^→

and a predetermined value s_L+1, the value s₀;

=h^→

·

f^→

being generated using a vector f^→

having r pieces of elements, and the vector h^→

;

a verification element i generation step of with the verification device, for each integer i=1, . . . , L and using a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> generated based on the vector f^→

and the matrix M which is included in the signature data σ

acquired in the data acquisition step, and a predetermined number θ

_i for each integer i=1, . . . , L, generating a verification element c_i, when the variable ρ

(i) is a positive tuple (t, v^→

_i) by setting s_i+θ

_iv_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 θ

_iv_i,i′

(i′

=2, . . . , n_t) as a coefficient for a basis vector b_t,i′

(i′

=2, . . . , n_t), and generating a verification element c when the variable ρ

(i) is a negative tuple (t, v^→

_i), by setting s_iv_i,i′

(i′

=1, . . . , n_t) as a coefficient for the basis vector b_t,i′

(i′

=1, . . . , n_t) indicated by identification information t of the negative tuple;

a verification element L+1 generation step of, with the verification device, generating a verification element c_L+1 by setting s_L+1−

θ

_L+1m′

calculated from the predetermined value s_L+1, the value m′

, and a predetermined value θ

_L+1 as a coefficient for a basis vector b_d+1,1 of a basis B_d+1, and by setting the predetermined value θ

_L+1 as a coefficient for a basis vector b_d+1,2; and

a pairing operation step of, with the verification device, verifying an authenticity of the signature data σ

by conducting a pairing operation Π

_i=0^L+1e(c_is*_i) for the verification element c₀ generated in the verification element 0 generation step, the verification element c_i generated in the verification element i generation step, the verification element c_L+1 generated in the verification element L+1 generation step, and the signature elements s*₀, s*_i, and s*_L+1 included in the signature data σ

.

14. A non-transitory computer readable medium including a signature processing program comprising a key generation program to run on a key generation device, a signature program to run on a signature device, and a verification program to run on a verification device, and serving to execute a signature process using a basis B_t and a basis B*_t for each integer t=0, . . . , d+1 (d is an integer of 1 or more),

wherein the key generation program causes a computer to execute

a first information input process of taking as input an attribute set Γ

including identification information t and attribute information 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,

a key element 0 generation process of generating a key element k*₀ where a predetermined value δ

is set as a coefficient for a basis vector b*_0,1 of a basis B*₀,

a key element t generation process of generating a key element k*_t where δ

x_t,i (i=1, . . . , n_t) 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, . . . , n_t) of the basis B*_t, concerning each identification information t included in the attribute set Γ

inputted in the first information input process,

a key element d+1 generation process of generating 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+t, 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 process of transmitting, to a signature device, a signing key sk_Γ

including;

the key element k*₀ generated in the key element 0 generation process;

the key element k*_t generated in the key element t generation process concerning each identification information t included in the attribute set Γ

;

the key element k*_d+1,1 and the key element k*_d+1,2 which are generated in the key element d+1 generation process; and

the attribute set Γ

,

wherein the signature program causes the computer to execute

a second information input process of taking as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m,

a signing key acquisition process of acquiring the signing key sk_Γ

transmitted in the signing key transmission process,

a complementary coefficient calculation process of, based on the variable ρ

(i) inputted in the second information input process and the attribute set Γ

included in the signing key sk_Γ

acquired in the signing key acquisition process, specifying, 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 the attribute set Γ

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 the attribute set Γ

indicated by identification information t of the negative tuple does not become 0; and

calculating, concerning i included in the set I specified, a complementary coefficient α

_i with which a total of α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted in the second information input process becomes a predetermined vector h^→

,

a signature element 0 generation process of generating a signature element s*₀ including the key element k*₀ included in the signing key sk_Γ

,

a signature element i generation process of generating, for each integer i=1, . . . , L, a signature element s*, 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 in the complementary coefficient calculation process and the variable ρ

(i) is a positive tuple (t, v^→

_i);

by setting the value γ

_i to satisfy y_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 process of generating 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 process of transmitting, to a verification device, signature data σ

including;

the signature element s*₀ generated in the signature element 0 generation process;

the signature element s*, generated for each integer i=1, . . . , L in the signature element i generation process;

the signature element s*_L+1 generated in the signature element L+1 generation process;

the message m;

the variable ρ

(i); and

the matrix M, and

wherein the verification program causes the computer to execute

a data acquisition process of acquiring the signature data σ

transmitted in the signature data transmission process,

a verification element 0 generation process of generating a verification element c₀ by setting, as a coefficient for a basis vector b_0,1 of a basis B₀, −

s₀−

s_L+1 calculated from a value s₀;

=h^→

·

f^→

and a predetermined value s_L+1, the value s₀;

=h^→

·

f^→

being generated using a vector f^→

having r pieces of elements, and the vector h^→

,

a verification element i generation process of, for each integer i=1, . . . , L and using a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> generated based on the vector f^→

and the matrix M which is included in the signature data σ

acquired in the data acquisition process, and a predetermined number θ

, for each integer i=1, . . . , L, generating a verification element c_i, when the variable ρ

(i) is a positive tuple (t, v^→

_i), by setting s_i+θ

_iv_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 θ

_iv_i,i′

(i′

=2, . . . , n_t) as a coefficient for a basis vector b_t,i′

(i′

=2, . . . , n_t), and generating a verification element c_i when the variable ρ

(i) is a negative tuple (t, v^→

_i), by setting s_iv_i,i′

. (i′

=1, . . . , n_t) as a coefficient for the basis vector b_t,i′

(i′

=1, . . . , n_t) indicated by identification information t of the negative tuple,

a verification element L+1 generation process of generating a verification element c_L+1 by setting s_L+1−

θ

_L+1m′

calculated from the predetermined value s_L+1, the value m′

, and a predetermined value θ

_L+1 as a coefficient for a basis vector b_d+1,1 of a basis B_d+1, and by setting the predetermined value θ

_L+1, as a coefficient for a basis vector b_d+1,2, and

a pairing operation process of verifying an authenticity of the signature data σ

by conducting a pairing operation Π

_i=0^L+1e(c_i,s*_i) for the verification element c₀ generated in the verification element 0 generation process, the verification element c_i generated in the verification element i generation process, the verification element c_L+1 generated in the verification element L+1 generation process, and the signature elements s*₀, s*_i, and s*_L+1 included in the signature data σ

.

15. A signature processing method of executing a signature process using a basis B_t and a basis B*_t for at least one integer t=0, . . . , d (d is an integer of 1 or more), the signature processing method including:

a first information input step of, with at least one key generation device among d units of key generation devices, taking as input attribute information x^→

_t;

=(x_t,i) (i=1, . . . , n_t) for an integer t among t=1, . . . , d which is predetermined for each of the key generation devices;

a key element generation step of with the at least one key generation device, for the integer t and each integer j=1, 2, generating a key element k*_t,j including a vector indicated in Formula 24 based on the attribute information x^→

_t inputted in the first information input step, a predetermined value δ

_j, and a basis vector b*_t,i (i=1, . . . , 2110 of the basis B*_t;

a signing key transmission step of, with the at least one key generation device, transmitting, to a signature device, a signing key usk including;

the key element k*_t,j generated in the key element generation step; and

the attribute information x^→

_t;

a second information input step of, with the signature device, taking as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m;

a signing key acquisition step of, with the signature device, acquiring the signing key usk transmitted in the signing key transmission step of at least one key generation device among the d units of key generation devices;

a complementary coefficient calculation step of, with the signature device and based on the variable ρ

(i) inputted in the second information input step and the attribute information x^→

_t included in the signing key usk acquired in the signing key acquisition step, specifying, 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 signing key usk including x^→

_t indicated by identification information t of the positive tuple being acquired in the signing key acquisition step, and with which an inner-product of v^→

_i 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 signing key usk including x^→

_t indicated by the identification information t of the negative tuple being acquired in the signing key acquisition step, 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

calculating, concerning i included in the set I specified, a complementary coefficient α

_i with which a total of α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted in the second information input step becomes a predetermined vector h^→

;

a signature element generation step of, with the signature device, generating, for each integer i=1, . . . , L, a signature element s*_i including a vector indicated in Formula 25 using the basis vector b*_t,i (i=2n_t+1, 2n_t+2) of the basis B*_t, based on a key element k*_t,1 and a key element k*_t,2 included in the signing key usk, predetermined values ξ

₁, E, and μ

, and a value m′

calculated from the message m, by setting a value γ

_i to satisfy γ

_i;

=α

_i when the integer i is included in the set I specified in the complementary coefficient calculation step 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 data transmission step of, with the signature device, transmitting, to a verification device, signature data σ

including;

the signature element s*_i generated for each integer i=1, . . . , L in the signature element generation step;

the message m;

the variable ρ

(i); and

the matrix M;

a data acquisition step of, with the verification device, acquiring the signature data σ

transmitted in the signature data transmission step;

a vector generation step of, with the verification device, generating a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> based on a vector f^→

having r pieces of elements and the matrix M included in the signature data σ

acquired in the data acquisition step, and generating a column vector (s^→

′

)^T;

=(s₁′

, . . . , s_L′

)^T;

=M·

(f<sup>→

′

)T</sup> based on the matrix M and a vector f^→

′

having r pieces of elements and satisfying s₀=h^→

·

(f_→

′

)^T where s₀=h^→

·

f<sup>→

T</sup>;

a verification element generation step of, with the verification device, for each integer i=1, . . . , L and based on the column vector s<sup>→

T</sup> and the column vector (s^→

′

)^T which are generated in the vector generation step, and predetermined values θ

_i, θ

<sub>i′

, θ

i</sub>″

, and σ

_i for each integer i=1, . . . , L, generating a verification element c_i including a vector indicated in Formula 26, when the variable ρ

(i) is a positive tuple (t, v^→

_i), using a basis vector b_t,i′

(i′

=1, . . . , 2n_t+2) of the basis B_t indicated by identification information t of the positive tuple, and generating a verification element c_i including a vector indicated in Formula 27, when the variable ρ

(i) is a negative tuple (t, v^→

_i), using a basis vector b_t,i (i′

=1, . . . , 2n_t+2) indicated by identification information t of the negative tuple; and

a pairing operation step of, with the verification device, verifying an authenticity of the signature data σ

by conducting a pairing operation Π

_i=1^Le(c_i,s*_i) for the verification element c_i generated in the verification element generation step and the signature element s*_i included in the signature data σ

.

16. A signature processing program comprising a key generation program to run on d (d is an integer of 1 or more) units of key generation devices, a signature program to run on a signature device, and a verification program to run on a verification device, and serving to execute a signature process using a basis B_t and a basis B*_t for at least one integer t=0, . . . , d,

wherein the key generation program causes a computer to execute

a first information input process of taking as input attribute information x^→

_t;

=(i=1, . . . , n_t) for an integer t among integers t=1, . . . , d which is predetermined for each of the key generation devices,

a key element generation process of, for the integer t and each integer j=1, 2, generating a key element k*_t,j including a vector indicated in Formula 28 based on the attribute information x^→

_t inputted in the first information input process, a predetermined value δ

_j, and a basis vector b*_t,i (i=1, . . . , 2n_t) of the basis B*_t, and

a signing key transmission process of transmitting, to the signature device, a signing key usk including;

the key element k*_t,j generated in the key element generation process; and

the attribute information x^→

_t,

wherein the signature program causes the computer to execute

a second information input process of taking as input a variable ρ

(i) for each integer i=1, . . . , L (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 (t is any one integer of t=1, . . . , d) and attribute information v^→

_i;

=(v_i,i′

) (i′

=1, . . . , n_t);

a predetermined matrix M having L rows and r columns (r is an integer of 1 or more); and

a message m,

a signing key acquisition process of acquiring the signing key usk transmitted in the signing key transmission process of at least one key generation device among the d units of key generation devices,

a complementary coefficient calculation process of, based on the variable ρ

(i) inputted in the second information input process and the attribute information x_t included in the signing key usk acquired in the signing key acquisition process, specifying, among integers i=1, . . . , L, a set I of an integer i for which the variable ρ

(i) is a positive tuple (t, v^→

_t), the signing key usk including x^→

_t indicated by identification information t of the positive tuple being acquired in the signing key acquisition process, 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 signing key usk including x^→

_t indicated by identification information t of the negative tuple being acquired in the signing key acquisition process, and with which an inner-product of v^→

_i the negative tuple and the attribute information x^→

_t indicated by the identification information t of the negative tuple does not become 0; and

calculating, concerning i included in the set I specified, a complementary coefficient α

_i with which a total of α

_iM_i based on M_i which is an element on an i-th row of the matrix M inputted in the second information input process becomes a predetermined vector h^→

,

a signature element generation process of generating, for each integer i=1, . . . , L, a signature element s*_i including a vector indicated in Formula 29 using the basis vector b*_t,i (i=2n₁+1, 2n_t+2) of the basis B*_t, based on a key element k*_t,1 and a key element k*_t,2 included in the signing key usk, predetermined values ξ

₁, E, and μ

, and a value m′

calculated from the message m, by setting a value γ

_i to satisfy γ

_i;

=α

_i when the integer i is included in the set I specified in the complementary coefficient calculation process 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, and

a signature data transmission process of transmitting, to the verification device, signature data σ

including;

the signature element s*_i generated for each integer i=1, . . . , L in the signature element generation process;

the message m;

the variable ρ

(i); and

the matrix M, and

wherein the verification program causes the computer to execute

a data acquisition process of acquiring the signature data σ

transmitted in the signature data transmission process,

a vector generation process of generating a column vector s<sup>→

T</sup>;

=(s₁, . . . , s_L)^T;

=M·

f<sup>→

T</sup> based on a vector f^→

having r pieces of elements and the matrix M included in the signature data σ

acquired in the data acquisition process, and generating a column vector (s^→

′

)^T;

=(s₁′

, . . . s_L′

)^T;

=M·

(f<sup>→

1</sup>′

)^T based on the matrix M and a vector f^→

′

having r pieces of elements and satisfying s₀=h^→

·

(f^→

′

)^T where s₀=h^→

·

f<sup>→

T</sup>.

a verification element generation process of, for each integer i=1, . . . , L and based on the column vector s<sup>→

T</sup> and the column vector (s^→

′

)^T which are generated in the vector generation process, and predetermined values θ

_i, θ

_i′

, θ

_i″

, and σ

_i for each integer i=1, . . . , L, generating a verification element c_i including a vector indicated in Formula 30, when the variable ρ

(i) is a positive tuple (t, v^→

_i), using a basis vector b_t,i′

(i′

=1, . . . , 2n₁+2) of the basis B_t indicated by identification information t of the positive tuple, and generating a verification element c_i including a vector indicated in Formula 31, when the variable ρ

(i) is a negative tuple (t, v^→

_i), using a basis vector b_t,i (i=1, . . . , 2n_t+2) indicated by identification information t of the negative tuple, and

a pairing operation process of verifying an authenticity of the signature data σ

by conducting a pairing operation Π

_i=1^Le(c_i,s*_i) for the verification element c_i generated in the verification element generation process, and the signature element s*_i included in the signature data σ

.0