Cryptographic processing system, key generation device, encryption device, decryption device, signature processing system, signature device, and verification device

A key generation device which generates a decryption key sks, in a cryptographic processing system which executes a cryptographic process using a basis Bt and a basis B*t for each integer t=0, . . . , d (d is an integer of 1 or more), the key generation device comprising:

• a first 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 is either one of a positive tuple (t, v→i) and a negative tuple (t, v→i) of identification information t (t is any one integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt where nt is an integer of 1 or more), and a predetermined matrix M having L rows and r columns (r is an integer of 1 or more);
• a decryption key generation part which generates an element k*0, and an element k*i for each integer i=1. . . , L, based on a column vector s→T:=(s1, . . . , sL)T:=M·f→T generated based on a vector f→ and a vector w→, each having r pieces of elements, and the matrix M inputted by the first information input part;
• a value s0:=w→·f→;
• and a predetermined value θi (i=1, . . . , L), the decryption key generation part being configured
• to generate the element k*0 by setting a value −s0 as a coefficient for a basis vector b*0,p (p is a predetermined value) of the basis B*0 and by setting a predetermined value κ as a coefficient for the basis vector b*0,q (q is a predetermined value different from prescribed p), and
• to generate the element k*i for each integer i=1, . . . , L, when the variable ρ(i) is a positive tuple (t, v→i), by setting si+θivi,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 θivi,i′ as a coefficient for a basis vector b*t,i′ indicated by the identification information t and each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i), by setting sivi,i′ as a coefficient for the basis vector b*t,i′ indicated by the identification information t of the negative tuple and by each integer i′=1, . . . , nt;
• and
• a key distribution part which distributes data including the variable ρ(i) inputted by the first information input part and the elements k*0 and k*i generated by the decryption key generation part, as the decryption key sks.

An encryption device which generates encrypted data c in a cryptographic processing system which executes a cryptographic encryption process using a basis Bt and a basis B*t for each integer t=0, . . . , d (1 is an integer of 1 or more), the encryption device comprising:

• a second information input part which takes as input, an attribute set Γ having the identification information t and an attribute vector x→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) for at least one integer t=1, . . . , d;
• an encrypted data generation part which generates an element c0, and an element ct concerning each identification information t included in the attribute set Γ, based on the attribute set Γ inputted by the second information input part, the encrypted data generation part being configured
• to generate the element c0 where a random value δ is set as a coefficient for a basis vector b0,p (p is prescribed p) of a basis B0, and where a predetermined value ζ is set as a coefficient for a basis vector B0,q (q is prescribed q) of a basis B0, and
• to generate the element ct where xt,i′ multiplied by the random value δ is set as a coefficient for a basis vector bt,i′ (i′=1, . . . , nt) of the basis Bt for each identification information t included in the attribute set;
• and
• a data output part which outputs the attribute set Γ inputted by the second information input part and the elements c0 and ct generated by the encrypted data generation part, as the encrypted data c.

A decryption device which decrypts encrypted data c with a decryption key sks in a cryptographic processing system which executes a cryptographic process using a basis Bt and a basis B*t for each integer t=0, . . . , d (d is an integer of 1 or more), the decryption device comprising:

• a data acquisition part which acquires
• an element c0 and an element ct (each integer included in the attribute set Γ) generated based on an attribute set Γ having identification information t and an attribute vector x→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) for at least one integer t=1, . . . , d, together with the attribute set Γ, as the encrypted data c,
• the element c0 being set with a random value δ as a coefficient for a basis vector b0,p (p is a predetermined value) of a basis B0 and being set with a predetermined value ζ as a coefficient for a basis vector b0,q (q is a predetermined value different from prescribed p) of the basis B0,
• the element ct being set with multiplied by the random value δ, as a coefficient for a basis vector bt,i′ (i′=1, . . . , nt) of a basis Bt, for each identification information t included in the attribute set Γ;
• a decryption key acquisition part which acquires
• an element k*0 and an element k*i (each integer i=1 . . . , L) generated based on a column vector s→T:=(s1, . . . , sL)T:=M·f→T generated based on a vector f→ and a vector w→ each having r (r is an integer of 1 or more) pieces of elements, and a predetermined matrix M having L rows and r columns;
• a value s0:=w→·f→;
• a predetermined value θi (i=1, . . . , L);
• and a variable ρ(i) for each integer i=1, . . . , L (L is an integer of 1 or more), together with the variable ρ(i), the variable ρ(i) being either one of a positive tuple (t, v→i) and a negative tuple (t, v→i), of the identification information t (t is any integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt, nt is an integer of 1 or more), as the decryption key sks,
• the element k*0 being set with the value −s0 as a coefficient for a basis vector b*0,p (p is prescribed p) of a basis B*0 and being set with a predetermined value κ as a coefficient for the basis vector b*0,q (q is prescribed q) of the basis B*0, and
• the element k*i for each integer i=1, . . . , L, when the variable ρ(i) is a positive tuple (t, v→i), being set with si+θivi,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 being set with θivi,i′ as a coefficient of a basis vector b*t,i′ indicated by the identification information t and by each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i), being set with sivi,i′ as a coefficient for the basis vector b*t,i′ indicated by the identification information t of the negative tuple and by each integer i′=1, . . . , nt;
• a complementary coefficient calculation part which, based on the attribute set Γ included in the encrypted data c acquired by the data acquisition part, and the variable ρ(i) included in the decryption key sks acquired by the decryption key acquisition part, specifies, among integers i=1, . . . , L, a set I of an integer i for which the variable ρ(i) is a positive tuple (t, v→i) and with which an inner-product of v→i of the positive tuple and x→t included in Γ indicated by identification information t of the positive tuple becomes 0, and an integer i for which the variable ρ(i) is a negative tuple (t, v→i) and with which an inner-product of v→i of the negative tuple and x→t included in Γ indicated by identification information t of the negative tuple does not become 0;
• and calculates a complementary coefficient αi with which a total of αisi for i included in the set I specified becomes s0;
• and
• a pairing operation part which calculates a value K=gTζχ by conducting a pairing operation indicated in Formula 7 for the elements c0 and ct included in the encrypted data c and the elements k*0 and k*i included in the decryption key sks, based on the set I specified by the complementary coefficient calculation part and on the complementary coefficient αi calculated by the complementary coefficient calculation part
• K
• :=
• e
• ⁡
• (
• c
• 0
• ,
• k
• 0
• *
• )
• ·
• ∏
• i
• ∈
• I
• ⋀
• ρ
• ⁡
• (
• i
• )
• =
• (
• t
• ,
• v
• →
• i
• )
• ⁢
• ⁢
• e
• ⁡
• (
• c
• t
• ,
• k
• i
• *
• )
• α
• i
• ·
• ∏
• i
• ∈
• I
• ⋀
• ρ
• ⁡
• (
• i
• )
• =
• ⫬
• (
• t
• ,
• v
• →
• i
• )
• ⁢
• e
• ⁡
• (
• c
• t
• ,
• k
• i
• *
• )
• α
• i
• /
• (
• v
• →
• i
• ·
• x
• →
• i
• )
• .
• [
• Formula
• ⁢
• ⁢
• 7
• ]

A cryptographic processing system comprising a key generation device, an encryption device, and a decryption device, and serving to execute a cryptographic process using a basis Bt and a basis B*t for each integer t=0, . . . , d (d is an integer of 1 or more),

• wherein the key generation device includes
• a first information input part which takes as input, an attribute set Γ having identification information t and an attribute vector x→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) for at least one integer t=1, . . . , d, and
• a decryption key generation part which generates an element k*0, and an element k*t concerning each identification information t included in the attribute set Γ, based on the attribute set Γ inputted by the first information input part, the decryption key generation part being configured
• to generate the element k*0 where a random value δ is set as a coefficient for a basis vector b*0,p (p is a predetermined value) of a basis B*0, and where a predetermined value κ is set as a coefficient for a basis vector b*0,q (q is a predetermined value different from prescribed p), and
• to generate the element k*t where xt,i′ multiplied by the random value δ is set as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of the basis B*t, for each identification information t included in the attribute set Γ,
• wherein the encryption 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 is either one of a positive tuple (t, v→i) and a negative tuple (t, v→i) of identification information t (t is any one integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt where nt is an integer of 1 or more), and a predetermined matrix M having L rows and r columns (r is an integer of 1 or more), and
• a encrypted data generation part which generates an element c0, and an element ci for each integer i=1 . . . , L, based on a column vector s→T:=(s1, . . . , sL)T:=M·f→T generated based on a vector f→ and a vector w→ each having r pieces of elements, and the matrix M inputted by the second information input part;
• a value s0:=w→·f→;
• and a predetermined value θi (i=1, . . . , L), the encrypted data generation part being configured
• to generate the element c0 by setting the value −s0 as a coefficient for a basis vector b0,p (p is prescribed p) of the basis B0 and by setting a predetermined value ζ as a coefficient for the basis vector b0,q (q is prescribed q), and
• to generate the element ci for each integer i=1, . . . , L, 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′ as a coefficient for a basis vector bt,i′ indicated by the identification information t and each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i), by setting sivi,i′ as a coefficient for the basis vector bt,i′ indicated by the identification information t of the negative tuple and by each integer i′=1, . . . , nt, and
• wherein the decryption device includes
• a data acquisition part which acquires encrypted data c including the elements c0 and ct and the variable ρ(i), the elements c0 and ct being generated by the encrypted data generation part,
• a decryption key acquisition part which acquires the decryption key skΓ including the elements k*0 and k*i and the attribute set Γ, the elements k*0 and k*i being generated by the decryption key generation part,
• a complementary coefficient calculation part which, based on the variable ρ(i) concerning each integer i=1, . . . , L included in the encrypted data c acquired by the data acquisition part and the attribute set Γ included in the decryption key skΓ acquired by the decryption key acquisition part, specifies, among integers i=1, . . . , L, a set I of an integer i for which the variable ρ(i) is a positive tuple (t, v→i) and with which an inner-product of v→i of the positive tuple and x→t included in Γ indicated by 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) and with which an inner-product of v→i of the negative tuple and x→t included in Γ indicated by the identification information t of the negative tuple does not become 0;
• and calculates a complementary coefficient αi with which a total of αisi for i included in the set I specified becomes s0, and
• a pairing operation part which calculates a value K=gTζχ by conducting a pairing operation indicated in Formula 8 for the elements c0 and ct included in the encrypted data c and the elements k*0 and k*i included in the decryption key skΓ, based on the set I specified by the complementary coefficient calculation part and the complementary coefficient αi calculated by the complementary coefficient calculation part
• K
• :=
• e
• ⁡
• (
• c
• 0
• ,
• k
• 0
• *
• )
• ·
• ∏
• i
• ∈
• I
• ⋀
• ρ
• ⁡
• (
• i
• )
• =
• (
• t
• ,
• v
• →
• i
• )
• ⁢
• ⁢
• e
• ⁡
• (
• c
• i
• ,
• k
• t
• *
• )
• α
• i
• ·
• ∏
• i
• ∈
• I
• ⋀
• ρ
• ⁡
• (
• i
• )
• =
• ⫬
• (
• t
• ,
• v
• →
• i
• )
• ⁢
• e
• ⁡
• (
• c
• i
• ,
• k
• t
• *
• )
• α
• i
• /
• (
• v
• →
• i
• ·
• x
• →
• t
• )
• .
• [
• Formula
• ⁢
• ⁢
• 8
• ]

A key generation device which generates a decryption key skΓ in a cryptographic processing system which executes a cryptographic process using a basis Bt and a basis B*t for each integer t=0, . . . , d (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 Γ having identification information t and an attribute vector 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 decryption key generation part which generates an element k*0, and an element k*t concerning each identification information t included in the attribute set Γ, based on the attribute set Γ inputted by the first information input part, the decryption key generation part being configured
• to generate the element k*0 where a random value δ is set as a coefficient for a basis vector b*0,p (p is a predetermined value) of a basis B*0, and where a predetermined value κ is set as a coefficient for a basis vector b*0,q (q is a predetermined value different from prescribed p), and
• to generate the element k*t where xt,i′ multiplied by the random value δ is set as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of the basis B*t, for each identification information t included in the attribute set Γ;
• and
• a key distribution part which distributes data including the attribute set Γ inputted by the first information input part and the elements k*0 and k*i generated by the decryption key generation part, as the decryption key sks.

An encryption device which generates encrypted data c in a cryptographic processing system which executes a cryptographic process using a basis Bt and a basis B*t for each integer t=0, . . . , d (d is an integer of 1 or more), the encryption device comprising:

• 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 is either one of a positive tuple (t, v→i) and a negative tuple (t, v→i) of identification information t (t is any one integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt where nt is an integer of 1 or more), and a predetermined matrix M having L rows and r columns (r is an integer of 1 or more);
• an encrypted data generation part which generates an element c0, and an element ci for each integer i=1 . . . , L, based on a column vector s→T:=(s1, . . . , sL)T:=M·f→T generated based on a vector f→ and a vector w→ each having r pieces of elements, and the matrix M inputted by the second information input part;
• a value s0:=w→·f→;
• and a predetermined value θi (i=1, . . . , L), the encrypted data generation part being configured
• to generate the element c0 by setting a value −s0 as a coefficient for a basis vector b*0,p (p is prescribed p) of a basis B0 and by setting a predetermined value ζ as a coefficient for a basis vector b0,q (q is prescribed q), and
• to generate the element ci for each integer i=1, . . . , L, 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′ as a coefficient for a basis vector bt,i′ indicated by the identification information t and each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i), by setting sivi,i′ as a coefficient for the basis vector bt,i′ indicated by the identification information t of the negative tuple and by each integer i′=1, . . . , nt;
• and
• a data output part which outputs the variable ρ(i) inputted by the second information input part and the elements c0 and ct generated by the encrypted data generation part, as the encrypted data c.

A decryption device which decrypts encrypted data c with a decryption key skΓ in a cryptographic processing system which executes a cryptographic process using a basis Bt and a basis B*t for each integer t=0, . . . , d (d is an integer of 1 or more), the decryption device comprising:

• a data acquisition part which acquires
• an element c0 and an element ci (for each integer i=1 . . . , L) generated based on a column vector s→T:=(s1, . . . , sL)T:=M·f→T generated based on a vector f→ and a vector w→ each having r (r is an integer of 1 or more) pieces of elements, and a predetermined matrix M having L rows and r columns;
• a value s0:=w→·f→;
• a predetermined value θi (i=1, . . . , L);
• and a variable ρ(i) for each integer i=1, . . . , L (L is an integer of 1 or more), together with the variable ρ(i), the variable ρ(i) being either one of a positive tuple (t, v→i) and a negative tuple (t, v→i), of identification information t (t is any integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt, nt is an integer of 1 or more), as the encrypted data c,
• the element c0 being set with a value −s0 as a coefficient for a basis vector b0,p (p is a predetermined value) of a basis B0 and being set with a predetermined value ζ as a coefficient for a basis vector b0,q (q is a predetermined value different from prescribed p) of the basis B0, and
• the element ci for each integer i=1, . . . , L, when the variable ρ(i) is a positive tuple (t, v→i), being set with 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 being set with θivi,i′ as a coefficient for a basis vector bt,i′ indicated by the identification information t and by each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i), being set with sivi,i′ as a coefficient for the basis vector bt,i′ indicated by the identification information t of the negative tuple and by each integer i′=1, . . . , nt;
• a decryption key acquisition part which acquires
• an element k*0 generated based on an attribute set Γ having identification information t and an attribute vector x→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) for at least one integer t=1, . . . , d, and an element k*t (t is each integer included in the attribute set Γ), as the decryption key skΓ together with the attribute set Γ,
• the element k*0 being set with a random value δ as a coefficient for a basis vector b*0,p (p is prescribed p) of a basis B*0 and being set with a predetermined value κ as a coefficient for a basis vector b*0,q (q is prescribed q) of the basis B*0,
• the element k*t being set with xt,i′ multiplied by the random value δ, as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of a basis B*t, for each identification information t included in the attribute set Γ;
• a complementary coefficient calculation part which, based on the variable ρ(i) included in the encrypted data c acquired by the data acquisition part, and the attribute set Γ included in the decryption key sks acquired by the decryption key acquisition part, specifies, among integers i=1, . . . , L, a set I of an integer i for which the variable ρ(i) is a positive tuple (t, v→i) and with which an inner-product of v→i of the positive tuple and x→t included in Γ indicated by identification information t of the positive tuple becomes 0, and an integer i for which the variable ρ(i) is a negative tuple (t, v→i)and with which an inner-product of v→i of the negative tuple and x→t included in Γ indicated by identification information t of the negative tuple does not become 0;
• and calculates a complementary coefficient αi with which a total of αisi for i included in the set I specified becomes s0;
• and
• a pairing operation part which calculates a value K=gTζχ by conducting a pairing operation indicated in Formula 14 for the elements c0 and ct included in the encrypted data c and the elements k*0 and k*i included in the decryption key sks, based on the set I specified by the complementary coefficient calculation part and the complementary coefficient αi calculated by the complementary coefficient calculation part
• K
• :=
• e
• ⁡
• (
• c
• 0
• ,
• k
• 0
• *
• )
• ·
• ∏
• i
• ∈
• I
• ⋀
• ρ
• ⁡
• (
• i
• )
• =
• (
• t
• ,
• v
• →
• i
• )
• ⁢
• ⁢
• e
• ⁡
• (
• c
• t
• ,
• k
• t
• *
• )
• α
• i
• ·
• ∏
• i
• ∈
• I
• ⋀
• ρ
• ⁡
• (
• i
• )
• =
• ⫬
• (
• t
• ,
• v
• →
• i
• )
• ⁢
• e
• ⁡
• (
• c
• t
• ,
• k
• t
• *
• )
• α
• i
• /
• (
• v
• →
• i
• ·
• x
• →
• i
• )
• .
• [
• Formula
• ⁢
• ⁢
• 14
• ]

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=1, . . . , d, d+2 (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 Γ having identification information t and an attribute vector x→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) for at least one integer t=1, . . . , d, and
• a signature key generation part which generates an element k*t concerning each identification information t included in the attribute set Γ, and an element k*d+2 and an element k*d+3 based on the attribute set Γ inputted by the first information input part, the signature key generation part being configured
• to generate the element k*t where xt,i′ multiplied by a random value δ is set as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of the basis B*t, for each identification information t included in the attribute set Γ,
• to generate the element k*d+2 where the random value δ is set as a coefficient for a basis vector b*d+2,p′ (p′ is a predetermined value) of a basis B*d+2, and
• to generate the element k*d+3 where the random value δ is set as a coefficient for a basis vector b*d+2,q′ (q′ is a predetermined value different from prescribed p′) of the basis B*d+2,
• 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 is either one of a positive tuple (t, v→i) and a negative tuple (t, v→i) of identification information t (t is any one integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt where nt is an integer of 1 or more), a predetermined matrix M having L rows and r columns (r is an integer of 1 or more), and a message m,
• a signature key acquisition part which acquires the elements k*t, k*d+2, and k*d+3 generated by the signature key generation part, and the attribute set Γ, as a signature key skΓ,
• a complementary coefficient calculation part which, based on the variable ρ(i) for each integer i=1, . . . , L and the attribute set Γ included in the signature key skΓ acquired by the signature key acquisition part, specifies, among integers i=1, . . . , L, a set I of an integer i for which the variable ρ(i) is a positive tuple (t, v→i) and with which an inner-product of v→i of the positive tuple and x→t included in Γ indicated by identification information t of the positive tuple becomes 0, and an integer i for which the variable ρ(i) is a negative tuple (t, v→i) and with which an inner-product of v→i of the negative tuple and x→t included in Γ indicated by the identification information t of the negative tuple does not become 0;
• and calculates a complementary coefficient αi with which a total of αiMi for i included in the set I specified, 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 w→, and
• a signature generation part which, based on the variable ρ(i), the attribute set Γ, the set I specified by the complementary coefficient calculation part, and the complementary coefficient αi calculated by the complementary coefficient calculation part, generates s*i for each integer i=1, . . . , L representing each row number of the matrix M, and s*x, as indicated in Formula 15, where
• βi is a value with which every element becomes 0 when βiMi is totaled for each integer i representing each row number of the matrix M, and
• for each integer i representing each row number of the matrix M,
• when iεI is established and the variable ρ(i) is a positive tuple (t, v→i), let a value γi:=αi, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 0 and yi,1=1,
• when iεI is established and the variable ρ(i) is a negative tuple (t, v→i), let a value γi:=αi/(v→i·x→t), and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 1,
• when iεI is not established and the variable ρ(i) is a positive tuple z,254 (t, v→i), let a value γi:=0, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 0 and yi,1=1, and
• when iεI is not established and the variable ρ(i) is a negative tuple (t, v→i), let a value γi:=0, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and is 1, and
• wherein the verification device includes
• a data acquisition part which acquires signature data sig including s*i and s*x generated by the signature generation part, the message m, the variable ρ(i), and the matrix M,
• an encrypted data generation part which generates an element ci and an element cx, the element ci being generated for each integer i representing a row number of the matrix M, based on a column vector s→T:=(s1, . . . , sL)T:=M·f→T generated based on a vector f→ having r pieces of elements, the vector w→, and the matrix M acquired by the data acquisition part;
• a value s0=w→·f→T;
• and a predetermined value θi (i is each row number of the matrix M, and X), the encrypted data generation part being configured
• to generate the element ci for each integer i=1 representing a row number of the matrix M, 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′ as a coefficient for a basis vector bt,i′ indicated by the identification information t and each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i) by setting sivi,i′ as a coefficient for the basis vector bt,i′ indicated by the identification information t of the negative tuple and each integer i′=1, . . . , nt, and
• to generate the element cx by setting s0−θxm in a basis vector bd+2,p′ (p′ is prescribed p′) of a basis vector Bd+2 and by setting θx in a basis vector bd+2,q′ (q′ is prescribed q′) of the basis vector Bd+2, and
• a pairing operation part which verifies validity of the signature data sig by performing a pairing operation indicated in Formula 16 for each integer i indicating X and a row number of the matrix M
• si*:=γi·ξkt*+βi·(Σt=1ntyi,ι·bt,ι*)+ri*
• sX*:=ξ(kd+2*+m·kd+3*)+rX* [Formula 15]
• where
• ξ, ri*, and rX* are predetermined values.
• Πe(ci,si*). [Formula 16]

A key generation device which generates a signature key skΓ in a signature processing system which executes a signature process using a basis Bt and a basis B*t for each integer t=1, . . . , d, d+2 (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 Γ having identification information t and an attribute vector 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 signature key generation part which generates an element k*t, an element k*d+2, and an element k*d+3 based on the attribute set Γ inputted by the first information input part, the element k*t concerning each identification information t included in the attribute set Γ, the signature key generation part being configured
• to generate the element k*t where xt,i′ multiplied by the random value δ is set as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of a basis B*t, for each identification information t included in the attribute set Γ,
• to generate the element k*t+2 where the random value δ is set as a coefficient for a basis vector b*d+2,p′ (p′ is a predetermined value) of a basis B*d+2, and
• to generate the element k*d+3 where the random value δ is set as a coefficient for a basis vector b*d+2,q′ (q′ is a predetermined value different from prescribed p′) of the basis B*d+2;
• and
• a key distribution part which distributes data including the attribute set Γ inputted by the information input part and the elements k*t, k*d+2, and k*d+3, as the signature key skΓ.

A signature device which generates signature data sig in a signature processing system which executes a signature process using a basis Bt and a basis B*t for each integer t=1, . . . , d, d+2 (d is an integer of 1 or more), the signature device comprising:

• 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 is either one of a positive tuple (t, v→i) and a negative tuple (t, v→i)of identification information t (t is any one integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′)(i′=1, . . . , nt where nt is an integer of 1 or more), a predetermined matrix M having L rows and r columns (r is an integer of 1 or more), and a message m;
• a signature key acquisition part which acquires an element k*t, an element k*d+2, and an element k*d+3 generated for at least one integer t=1, . . . , d, based on an attribute set Γ having identification information t and an attribute vector x→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) (t is each identification information included in the attribute set Γ), together with the attribute set Γ, as a signature key skΓ, the signature key acquisition part being configured
• to generate the element k*t being set with xt,i′ multiplied by the random value δ as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of a basis B*t, for each identification information t included in the attribute set Γ,
• to generate the element k*d+2 being set with the random value δ as a coefficient for a basis vector b*d+2,p′ (p′ is a predetermined value) of a basis B*d+2, and
• to generate the element k*d+3 being set with the random value δ as a coefficient for a basis vector b*d+2,q′ (q′ is a predetermined value different from prescribed p′) of the basis B*d+2;
• a complementary coefficient calculation part which, based on the variable ρ(i) for each integer i=1, . . . , L and the attribute set Γ included in the signature key skΓ acquired by the signature key acquisition part, specifies, among integers i=1, . . . , L, a set I of an integer i for which the variable ρ(i) is a positive tuple (t, v→i) and with which an inner-product of v→i of the positive tuple and x→t included in Γ indicated by identification information t of the positive tuple becomes 0, and an integer i for which the variable ρ(i) is a negative tuple (t, v→i) and with which an inner-product of v→i of the negative tuple and x→t included in Γ indicated by the identification information t of the negative tuple does not become 0;
• and calculates a complementary coefficient αi with which a total of αiMi for i included in the set I specified, 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 w→;
• a signature generation part which, based on the variable ρ(i), the attribute set Γ, the set I specified by the complementary coefficient calculation part, and the complementary coefficient αi calculated by the complementary coefficient calculation part, generates s*i for each integer i representing each row number of the matrix M, and s*x, as indicated in Formula 20, where
• βi is a value with which every element becomes 0 when βiMi is totaled for each integer i representing each row number of the matrix M, and
• for each integer i representing each row number of the matrix M,
• when iεI is established and the variable ρ(i) is a positive tuple (t, v→i), let a value γi:=αi, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 0 and yi,1=1,
• when iεI is established and the variable ρ(i) is a negative tuple (t, v→i), let a value γi:=αi/(v→i·x→t), and let a vector y→i:=(yi,ι) (ι:=1, . , nt) be a vector with which an inner-product of y→i and v→i is 1,
• when iεI is not established and the variable ρ(i) is a positive tuple (t, v→i), let a value γi:=0, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 0 and yi,1=1, and
• when iεI is not established and the variable ρ(i) is a negative tuple (t, v→i), let a value γi:=0, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 1;
• and
• a data output part which outputs data including the variable ρ(i), the matrix M, and the message m which are inputted by the information input part, and s*0, s*i, and s*x generated by the signature generation part, as signature data sig
• si*:=γi·ξkt*+βi·(Σι=1ntyi,ι·bt,ι*)+ri*
• sX*:=ξ(kd+2*+m·kd+3*)+rX* [Formula 20]
• where
• ξ, ri*, and rX* are predetermined values.

A verification device which verifies signature data sig in a signature processing system which executes a signature process using a basis Bt and a basis B*t for each integer t=1, . . . , d, d+2 (d is an integer of 1 or more), the verification device comprising:

• a data acquisition part which acquires the signature data sig including s*i, s*x, a message M, a variable number ρ(i), and a matrix M, out of:
• elements k*t, k*d+2, k*d+3;
• a set I and a complementary coefficient αi;
• and S*i and S*x;
• wherein the elements k*t, k*d+2, and k*d+3 are generated for at least one integer t=1, . . . , d, based on an attribute set Γ having identification information t and an attribute vector y→t:=(xt,i′) (i′=1, . . . , nt where nt is an integer of 1 or more) (t is each identification information included in the attribute set Γ),
• the element k*t being set with xt,i′ multiplied by the random value δ, as a coefficient for a basis vector b*t,i′ (i′=1, . . . , nt) of a basis B*t, for each identification information t included in the attribute set Γ,
• the element k*d+2 being set with the random value δ, as a coefficient for a basis vector b*d+2,p′ (p′ is a predetermined value) of a basis B*d+2, and
• the element k*d+3 being set with the random value δ, as a coefficient for a basis vector b*d+2,q′ (q′ is a predetermined value different from prescribed p′) of the basis B*d+2,
• wherein the set I and the complementary coefficient αi are calculated based on a variable ρ(i) for each integer i=1, . . . , L (L is an integer of 1 or more), which is either one of a positive tuple (t, v→i) and a negative tuple (t, v→i) of identification information t (t is any one integer of t=1, . . . , d) and an attribute vector v→i:=(vi,i′) (i′=1, . . . , nt where nt is an integer of 1 or more), and based on the attribute set Γ,
• the set I being a set of, among integers i=1, . . . , L, an integer i for which the variable ρ(i) is a positive tuple (t, v→i) and with which an inner-product of v→i of the positive tuple and x→t included in Γ indicated by 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) and with which an inner-product of v→i the negative tuple and x→t included in Γ indicated by the identification information t of the negative tuple does not become 0,
• the complementary coefficient αi being such that with which a total of αiMi for i included in the set I, based on Mi which is an element on an i-th row of the matrix M inputted, becomes a predetermined vector w→, and
• wherein s*i (each integer of i=1, . . . , L) and s*x are generated based on the variable ρ(i), the attribute set Γ, the set I, and the complementary coefficient αi, as indicated in Formula 21, where
• βi is a value with which every element becomes 0 when βiMi is totaled for each integer i representing each row number of the matrix M, and
• for each integer i representing each row number of the matrix M,
• when iεI is established and the variable ρ(i) is a positive tuple (t, v→i), let a value γi:=αi, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 0 and yi,1=1,
• when iεI is established and the variable ρ(i) is a negative tuple (t, v→i), let a value γi:=αi/(v→i·x→t), and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 1,
• when iεI is not established and the variable ρ(i) is a positive tuple (t, v→i), let a value γi:=0, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 0 and yi,1=1, and
• when iεI is not established and the variable ρ(i) is a negative tuple (t, v→i), let a value γi:=0, and let a vector y→i:=(yi,ι) (ι:=1, . . . , nt) be a vector with which an inner-product of y→i and v→i is 1;
• an encrypted data generation part which generates an element ci and an element cx, the element ci being generated for each integer i=1, . . . , L, based on a column vector s→T:=(si, . . . , sL)T:=M·f→T generated based on a vector f→ having r pieces of elements, the vector W→, and the matrix M inputted by the data acquisition part;
• a value s0:=w→·f→T;
• and a predetermined value θi(i is each row number of the matrix M, and X), the encrypted data generation part being configured
• to generate the element ci, for each integer i=1 representing a row number of the matrix M, 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′ as a coefficient for a basis vector bt,i′ indicated by the identification information t and each integer i′=2, . . . , nt, and when the variable ρ(i) is a negative tuple (t, v→i), by setting sivi,i′ as a coefficient for the basis vector bt,i′ indicated by the identification information t of the negative tuple and each integer i′=1, . . . , nt, and
• to generate the element cx by setting s0−θxm in a basis vector bd+2,p′ (′p is prescribed p′) of a basis vector Bd+2 and by setting θx in a basis vector bd+2,q′ (′q is prescribed q′) of the basis vector Bd+2;
• and
• a pairing operation part which verifies validity of the signature data sig by performing a pairing operation indicated in Formula 22 for each integer i indicating X and a row number of the matrix M
• si*:=γi·ξkt*+βi·(Σι=1ntyi,ι·bt,ι*)+ri*
• sX*:=ξ(kd+2*+m·kd+3*)+rX* [Formula 21]
• where
• ξ, ri* and rX* are predetermined values
• Πe(ci,si*). [Formula 22]