Signature processing system, key generation device, signature device, verification device, signature processing method, and signature processing program
First Claim
Patent Images
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 includesa 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, anda 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 includesa 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, anda 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, andwherein the verification device includesa 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, anda 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 σ
.
1 Assignment
0 Petitions
Accused Products
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.
11 Citations
10 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 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, anda 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, anda 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, andwherein 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, anda 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 σ
. - View Dependent Claims (2, 3)
-
-
4. 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 Bt 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;
=(xt,i) (i=1, . . . , nt where nt 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, . . . , 2nt) of the basis B*t, anda 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,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;
=(vi,i′
)(i′
=1, . . . , nt);
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 α
iMi based on Mi 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→
,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;
=(vi,i′
)(i′
=1, . . . , nt);
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 α
iMi based on Mi 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=2nt+1, 2nt+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 ξ
1, 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/(vi·
xt) 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, anda 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, andwherein 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→
T;
=(s1, . . . , sL)T;
=M·
f→
T 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;
=(s1′
, . . . , sL′
)T;
=M·
(f→
′
)T based on the matrix M and a vector f→
1 having r pieces of elements and satisfying s0=h→
·
(f→
′
)T where s0=h→
·
f→
T,a verification element 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, θ
i′
, θ
i″
, and σ
i for each integer i=1, . . . , L, generates a verification element ci including a vector indicated in Formula 12, when the variable ρ
(i) is a positive tuple (t, v→
i), using a basis vector bt,i′
(i=1, . . . , 2nt+2) of the basis Bt indicated by identification information t of the positive tuple, and generates a verification element ci including a vector indicated in Formula 13, when the variable ρ
(i) is a negative tuple (t, v→
i), using a basis vector bt,i (i=1, . . . , 2nt+2) indicated by identification information t of the negative tuple, anda pairing operation part which verifies an authenticity of the signature data σ
by conducting a pairing operation Π
i=1Le(ci,s*i) for the verification element ci generated by the verification element generation part, and the signature element s*i included in the signature data σ
, - View Dependent Claims (5, 6)
-
-
7. A signature processing method of executing 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), 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;
=(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 step of, with the key generation device, generating 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 step of, with the key generation device, generating 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 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 δ
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*0 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→
i;
=(vi,i′
)(i′
=1, . . . , nt);
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 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 α
iMi based on Mi 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*0 including the key element k*0 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*0 generated in the signature element 0 generation step;
the signature element s*i 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 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 step of, with the verification device, 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 a acquired in the data acquisition step, and a predetermined number θ
i for each integer i=1, . . . , L, generating 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 generating 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 step of, with the verification device, generating a verification element 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; anda pairing operation step of, with the verification device, verifying an authenticity of the signature data σ
by conducting a pairing operation Π
i=0L+1e(ci,s*i) for the verification element c0 generated in the verification element 0 generation step, the verification element ci generated in the verification element i generation step, the verification element cL+1 generated in the verification element L+1 generation step, and the signature elements s*0, s*i, and s*L+1 included in the signature data σ
.
-
-
8. 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 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 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;
=(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 process of generating 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 process of generating 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 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+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, anda signing key transmission process of transmitting, to a signature device, a signing key skΓ
including;
the key element k*0 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;
=(vi,i′
)(i′
=1, . . . , nt);
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 α
iMi based on Mi 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*0 including the key element k*0 included in the signing key skΓ
,a signature element i generation process of 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 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,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, anda signature data transmission process of transmitting, to a verification device, signature data σ
including;
the signature element s*0 generated in the signature element 0 generation process;
the signature element s*i 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, andwherein 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 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 process of, for each integer i=1, . . . , L and using a column vector s→
T;
=(s1, . . . , sL)T;
=M·
fT 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 θ
i for each integer i=1, . . . L, generating 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 generating a verification element ci, when the variable ρ
(i) is a negative tuple (t, v→
i), by setting (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 process of generating 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,2, and by setting the predetermined value θ
L+1, as a coefficient for a basis vector bd+1,2, anda pairing operation process of verifying an authenticity of the signature data σ
by conducting a pairing operation Π
0L+1e(ci,s*i) for the verification element c0 generated in the verification element 0 generation process, the verification element ci generated in the verification element i generation process, the verification element cL+1 generated in the verification element L+1 generation process, and the signature elements s*0, s*i, and s*L+1 included in the signature data σ
.
-
-
9. A signature processing method of executing a signature process using a basis Bt 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;
=(xt,i) (i=1, . . . , nt) 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, . . . , 2nt) 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;
=(vi,i′
)(i′
=1, . . . , nt);
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 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 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 α
iMi based on Mi 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=2nt+1, 2nt+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 ξ
1, 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/(vi·
xt) 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 a transmitted in the signature data transmission step; a vector generation step of, with the verification device, generating a column vector s→
T;
=(s1, . . . , sL)T;
=M·
f→
T 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;
=(s1′
, . . . , sL)T;
=M·
(f→
′
)T based on the matrix M and a vector f→
′
having r pieces of elements and satisfying s0=h→
·
(f→
′
)T where s0=h→
·
f→
T;a verification element generation step of, with the verification device, for each integer i=1, . . . , L and based on the column vector s→
T and the column vector (s→
′
)T which are generated in the vector generation step, and predetermined values θ
i, θ
i′
, θ
i″
, and σ
i for each integer i=1, . . . , L, generating a verification element ci including a vector indicated in Formula 26, when the variable ρ
(i) is a positive tuple (t, v→
i), using a basis vector bt,i′
(i′
=1, . . . , 2nt+2) of the basis Bt indicated by identification information t of the positive tuple, and generating a verification element ci including a vector indicated in Formula 27, when the variable ρ
(i) is a negative tuple (t, v→
i), using a basis vector bt,i (i′
=1, . . . , 2nt+2) indicated by identification information t of the negative tuple; anda pairing operation step of, with the verification device, verifying an authenticity of the signature data σ
by conducting a pairing operation Π
i=1Le(ci,s*i) for the verification element ci generated in the verification element generation step and the signature element s*i included in the signature data σ
,
-
-
10. A non-transitory computer readable medium including 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 Bt 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;
=(xt,i) (i=1, . . . , nt) 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, . . . , 2nt) of the basis B*t, anda 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;
=(vi,i′
) (i′
=1, . . . , nt);
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 xt 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→
i), 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 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 α
iMi based on Mi 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=2nt+1, 2nt+2) of the basis B*t, based on a key element kt,1 and a key element k*t,2 included in the signing key usk, predetermined values ξ
1, 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, anda 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, andwherein 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→
T;
=(s1, . . . , sL)T;
=M·
f→
T 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;
=(s1′
, . . . , sL′
)T;
=M·
(f→
′
)T based on the matrix M and a vector f→
′
having r pieces of elements and satisfying s0=h→
·
(f→
′
)T where s0=h→
·
f→
T,a verification element generation process of, for each integer i=1, . . . , L and based on the column vector s→
T 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 ci including a vector indicated in Formula 30, when the variable ρ
(i) is a positive tuple (t, v→
i), using a basis vector bt,i′
(i′
=1, . . . , 2nt+2) of the basis Bt indicated by identification information t of the positive tuple, and generating a verification element ci including a vector indicated in Formula 31, when the variable ρ
(i) is a negative tuple (t, v→
i), using a basis vector bt,i (i=1, . . . , 2nt+2) indicated by identification information t of the negative tuple, anda pairing operation process of verifying an authenticity of the signature data σ
by conducting a pairing operation Π
i=1Le(ci,s*i) for the verification element ci generated in the verification element generation process, and the signature element s*i included in the signature data σ
,
-
Specification