Signature device, verification device, signature method, verification method, and computer readable medium

A verification device comprising:

• processing circuitry to:
• acquire a signature in which an attribute vector and predicate information of arithmetic branching programs (ABP) are set over a basis B* of a basis B and the basis B*, which are dual bases in dual vector spaces, and
• verify the signature by performing a pairing operation on the acquired signature and verification data in which verification information is set over the basis B,
• wherein the signature includes elements respectively corresponding to elements of the attribute vector, and in each of the elements of the signature, index information I* associated with a corresponding one of the elements of the attribute vector is set as a coefficient of one or more but not all basis vectors in the basis B*, and
• wherein the verification data includes one or more elements corresponding to one or more elements of the attribute vector, and in each element of the verification data, index information I is set as a coefficient of each basis vector in the basis B corresponding to the one or more but not all basis vectors, the index information I being such that a sum of inner products of the index information I and the index information I* becomes 0.

A signature method comprising:

• acquiring a signature key in which an attribute vector is set over a basis B* of a basis B and the basis B*, which are dual bases in dual vector spaces;
• generating a signature for a message by setting predicate information of arithmetic branching programs (ABP) for the signature key;
• and
• outputting the signature and the message,
• wherein the signature key includes elements respectively corresponding to elements of the attribute vector, and in each of the element of the signature key, index information I* associated with a corresponding one of the elements of the attribute vector is set as a coefficient of one or more but not all basis vectors in the basis B*.

A non-transitory computer readable medium storing a signature program that causes a computer to function as a signature device to perform:

• an acquisition process of acquiring a signature key in which an attribute vector is set over a basis B* of a basis B and the basis B*, which are dual bases in dual vector spaces;
• a signature process of generating a signature for a message by setting predicate information of arithmetic branching programs (ABP) for the signature key acquired by the acquisition process;
• and
• an output process of outputting the signature generated by the signature process and the message,
• wherein the signature key includes elements respectively corresponding to elements of the attribute vector, and in each of the element of the signature key, index information I* associated with a corresponding one of the elements of the attribute vector is set as a coefficient of one or more but not all basis vectors in the basis B*.

A verification method comprising:

• acquiring a signature in which an attribute vector and predicate information of arithmetic branching programs (ABP) are set over a basis B* of a basis B and the basis B*, which are dual bases in dual vector spaces;
• and
• verifying the signature by performing a pairing operation on the signature and verification data in which verification information is set over the basis B,
• wherein the signature includes elements respectively corresponding to elements of the attribute vector, and in each of the elements of the signature, index information I* associated with a corresponding one of the elements of the attribute vector is set as a coefficient of one or more but not all basis vectors in the basis B*, and
• wherein the verification data includes one or more elements corresponding to one or more elements of the attribute vector, and in each element of the verification data, index information I is set as a coefficient of each basis vector in the basis B corresponding to the one or more but not all basis vectors, the index information I being such that a sum of inner products of the index information I and the index information I* becomes 0.

A non-transitory computer readable medium storing a verification program that causes a computer to function as a verification device to perform:

• an acquisition process of acquiring a signature in which an attribute vector and predicate information of arithmetic branching programs (ABP) are set over a basis B* of a basis B and the basis B*, which are dual bases in dual vector spaces;
• and
• a verification process of verifying the signature by performing a pairing operation on the signature acquired by the acquisition process and verification data in which verification information is set over the basis B,
• wherein the signature includes elements respectively corresponding to elements of the attribute vector, and in each of the elements of the signature, index information I* associated with a corresponding one of the elements of the attribute vector is set as a coefficient of one or more but not all basis vectors in the basis B*, and
• wherein the verification data includes one or more elements corresponding to one or more elements of the attribute vector, and in each element of the verification data, index information I is set as a coefficient of each basis vector in the basis B corresponding to the one or more but not all basis vectors, the index information I being such that a sum of inner products of the index information I and the index information I* becomes 0.