JP2012175634A - Aggregate signature system, verification system, aggregate signature method, and aggregate signature program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide an aggregate signature system, a verification system, an aggregate signature method, and an aggregate signature program that suppress a signature size to a constant value even when persons who sign increase in number, and achieve a sequenced electronic signature through efficient arithmetic processing.SOLUTION: In the aggregate signature system, each node performs operation on a hash value obtained from a message of the node right before it and a hash value obtained from a message of the node itself with a signature key assigned to the node itself, and generates signature information of itself using signature information generated by the node right before it.

Description

  The present invention relates to an electronic data aggregate signature system, verification system, aggregate signature method, and aggregate signature program.

  Currently, various electronic information is transmitted through networks and media. Even in an organization such as a company or community, various information such as reports, reports, proposals, and correspondence books are digitized and circulated among employees or members via a network.

  There is a digital signature as a mechanism for guaranteeing that the information is transmitted or viewed. Using this electronic signature, the signature is calculated using the signature key and electronic information that only a specific person knows as input values, and the verifier inputs the public information called the verification key and the signed data. By performing a verification operation as a value, it is possible to confirm that the specific person is the source of the data. Here, since it is impossible to derive the signature key from the verification key in terms of computational complexity, the validity of the signature is guaranteed because it is impossible for another person to impersonate the specific person and perform the signature. Is done.

  Further, in circulation of electronic information in an organization, a case where a signature is made with a plurality of people intervening is assumed, for example, circulation of electronic data or an approval system in a company. As a method of signing multiple persons, a multiple signature (for example, refer to Non-Patent Document 1) that can verify each signer, or a group that can guarantee that someone who belongs to a specific group has signed. A signature (see, for example, Patent Document 1) has been proposed.

JP 2001-166687 A JP 09-270787 A JP 2002-040935 A

Shingo, “A variation of ElGamal signature suitable for multiple signatures”, Symposium on Cryptography and Information Security (CSS), SCIS94-2C, IEICE, 1994

  However, in these multiple signatures and group signatures, all signers are expressed in an equivalent relationship. Therefore, it is impossible to express how electronic data has been distributed in the multiple signature system shown as an example only by this signature method.

  On the other hand, an ordered multiple signature scheme (for example, see Patent Documents 2 and 3) can be cited as a scheme for proving the order and the hierarchical relationship. As a result, the order of the signers is guaranteed, and the upper and lower personal relationships can be expressed. However, these existing ordered multiple signature schemes have been proposed based on the RSA (Rivest Shamir Adleman) problem or based on the discrete logarithm problem. In the RSA problem base, the signature size increases as the number of signatures increases, and in the discrete logarithm problem base, the calculation processing is burdened to use zero knowledge proof, and the processing is not efficient. Moreover, since both of them are systems in which a plurality of people sign the same message, each signer cannot perform an aggregate signature for different messages.

  In order to solve the above-described problems, the present invention provides an aggregate signature system and a verification system that can suppress the signature size to a constant value even when the number of people to sign increases, and can perform an ordered digital signature by efficient arithmetic processing. It is an object of the present invention to provide an aggregate signature method and an aggregate signature program.

  The present invention provides the following solutions.

(1) An aggregate signature system according to the present invention is an aggregate signature system that performs an ordered aggregate signature from one node to another node in order to solve the above-described problem. A signature key consisting of a predetermined natural number and a first value belonging to a first GDH (GAP-Diffie-Hellman) group belong to the first GDH group generated by performing an operation using the signature key. A verification key is assigned to each node, and each node includes the following units.
(A) A receiving unit that receives a message to be signed by the immediately preceding node or a hash value of the message and the signature information of the immediately preceding node when the immediately preceding node exists.
(B) When there is a message of its own and the immediately preceding node, a one-way hash function operation is performed on the message of the immediately preceding node, and a hash belonging to the second GDH group of each message Signature node one-way hash function calculation unit for generating a value.
(C) The result of the operation performed on the hash value of its own message with its own signature key and, if the previous node exists, the signature of its own node on the hash value of the message of the previous node A signature information generation unit that generates the signature information of itself by summing up the result of the operation using the key and the signature information of the immediately preceding node.
(D) A transmitting unit that transmits its own message or the hash value of the message and its signature information to the immediately following node when the immediately following node exists.

  According to such a configuration, the aggregate signature system assigns to each node the hash value obtained from the message of the immediately preceding node and the hash value obtained from its own message at each node. An operation is performed using the signature key, and the signature information generated by the immediately preceding node is used to generate its own signature information. The aggregate signature system can express the signature order up to each node by this signature information.

  Further, with this configuration, the aggregate signature system makes it difficult for a third party who does not know the signature key to obtain the signature key from a point on the elliptic curve that is an element of the GDH group. Can be. Even if the number of signers (number of nodes) increases, the generated signature information is a point on the elliptic curve, so the size (capacity) of the signature information does not increase and can be suppressed to a certain value or less. The aggregate signature can be generated efficiently.

  (2) Further, in the aggregate signature system, the signature information generation unit, when there are a plurality of the immediately preceding nodes, a result of performing an operation on the hash value of its own message with its own signature key, A plurality of results obtained by performing computation on the hash value of the message of each of the immediately preceding nodes using the signature key of the own node and the signature information of each of the immediately preceding nodes are summed to generate own signature information It is characterized by that.

According to such a configuration, the aggregate signature system, for each node, for each hash value obtained from the message of the immediately preceding node or nodes and the hash value obtained from its own message, An operation is performed using the signature key assigned to the own node, and the signature information generated by the immediately preceding node is used to generate its own signature information. The aggregate signature system can express the signature order in the tree structure up to each node by this signature information.
Note that the tree structure refers to all tree structures having an arbitrary structure, whether symmetrical or asymmetric. The present invention can be applied to a tree structure having this arbitrary structure.

  (3) In the aggregate signature system, each of the nodes includes a public unit that discloses its own signature information.

  According to such a configuration, each node can publish signature information, which is an ordered aggregate signature, to other nodes.

  (4) In the aggregate signature system, the disclosure unit further discloses the order information of the nodes.

  According to such a configuration, each node can publish the order of the nodes in which the signature is performed in the process until the signature information is generated together with the signature information.

  (5) A verification system according to the present invention is a verification system for verifying signature information published by the disclosure unit provided in the aggregate signature system, in order to solve the above-described problem, A collection unit that collects messages of all nodes in the process of generating signature information or hash values of the messages and verification keys of all nodes, and a message collected by the collection unit, respectively. A verification node unidirectional hash function calculation unit that performs a directional hash function calculation to generate a hash value belonging to the second GDH group of each message, a verification key of all the nodes, and A verification unit that verifies the validity of the published signature information based on the hash value of the message.

  According to such a configuration, the verification system verifies the validity of the published signature information based on the verification keys of all the nodes and the hash value of the message by the verification unit.

  Therefore, in the verification system, it is possible to prove the signature order by verifying the published signature information without verifying the individual signature information generated at each node. In other words, the verification system can execute the verification work while reducing the processing load on the verification node.

  (6) In the verification system, the verification unit performs a pairing operation based on the result of the pairing operation using the verification key and the hash value of the same node, and the hash value of the node immediately before the verification key and the node. Is compared with the first value and the result of the pairing operation using the published signature information, and if both match, it is determined that the published signature information is valid. If both do not match, it is determined that the published signature information is not valid.

  According to such a configuration, the verification system can verify the validity of the ordered aggregate signature by an efficient calculation process by the GDH signature using the pairing calculation.

(7) An aggregate signature method according to the present invention is an aggregate signature method for performing an ordered aggregate signature from one node to another node in order to solve the above-described problem. A signature key consisting of a predetermined natural number and a first value belonging to a first GDH (GAP-Diffie-Hellman) group belong to the first GDH group generated by performing an operation using the signature key. A verification key is assigned to each node, and each node executes the following steps.
(A) A reception step of receiving a message that is a signature target of the immediately preceding node or a hash value of the message and signature information of the immediately preceding node when the immediately preceding node exists.
(B) When there is a message of its own and the immediately preceding node, a one-way hash function operation is performed on the message of the immediately preceding node, and a hash belonging to the second GDH group of each message Signature node one-way hash function calculation step for generating a value.
(C) The result of the operation performed on the hash value of its own message with its own signature key and, if the previous node exists, the signature of its own node on the hash value of the message of the previous node A signature information generation step of generating the signature information of itself by summing up the result of the operation with the key and the signature information of the immediately preceding node.
(D) A transmission step of transmitting the own message or the hash value of the message and the signature information of the message to the immediately following node when the immediately following node exists.

(8) An aggregate signature program according to the present invention is an aggregate for causing a computer to execute an aggregate signature method for performing an ordered aggregate signature from one node to another in order to solve the above-described problem. A signing program, wherein each node performs an operation on a signing key composed of a predetermined natural number and a first value belonging to a first GDH (GAP-Diffie-Hellman) group using the signing key. A verification key belonging to the first GDH group to be generated is assigned, and each node is caused to execute the following steps.
(A) A reception step of receiving a message that is a signature target of the immediately preceding node or a hash value of the message and signature information of the immediately preceding node when the immediately preceding node exists.
(B) When there is a message of its own and the immediately preceding node, a one-way hash function operation is performed on the message of the immediately preceding node, and a hash belonging to the second GDH group of each message Signature node one-way hash function calculation step for generating a value.
(C) The result of the operation performed on the hash value of its own message with its own signature key and, if the previous node exists, the signature of its own node on the hash value of the message of the previous node A signature information generation step of generating the signature information of itself by summing up the result of the operation with the key and the signature information of the immediately preceding node.
(D) A transmission step of transmitting the own message or the hash value of the message and the signature information of the message to the immediately following node when the immediately following node exists.

  According to the present invention, even when the number of people to be signed increases, the signature size can be suppressed to a constant value, and an ordered aggregate signature can be performed by efficient calculation processing.

It is a block diagram which shows the structure of the leaf node in the aggregate signature system which concerns on 1st Embodiment. It is a block diagram which shows the structure of the intermediate node in the aggregate signature system which concerns on 1st Embodiment. It is a block diagram which shows the structure of the root node in the aggregate signature system which concerns on 1st Embodiment. It is a block diagram which shows the structure of the verification node in the aggregate signature system which concerns on 1st Embodiment. 6 is a flowchart for explaining a method for generating signature information of a leaf node in the first embodiment. 6 is a flowchart for explaining a method for generating signature information of an intermediate node in the first embodiment. In 1st Embodiment, it is a flowchart with which it uses for description about the method of publishing signature information in a root node. 5 is a flowchart for explaining a method for verifying the validity of signature information in a verification node in the first embodiment. In 1st Embodiment, it is a figure where it uses for description about operation | movement of an aggregate signature system. It is a block diagram which shows the structure of the leaf node in the aggregate signature system which concerns on 2nd Embodiment. It is a block diagram which shows the structure of the intermediate node in the aggregate signature system which concerns on 2nd Embodiment. It is a block diagram which shows the structure of the root node in the aggregate signature system which concerns on 2nd Embodiment. It is a block diagram which shows the structure of the verification node in the aggregate signature system which concerns on 2nd Embodiment.

<First Embodiment>
Hereinafter, a first embodiment, which is an example of an embodiment of the present invention, will be described. The aggregate signature system according to the present embodiment is a system in which a plurality of nodes are configured in a tree structure, and an ordered multiple signature is performed in order from a lower node on an independent message at the plurality of nodes. Further, the validity of the signature information disclosed by the highest root node is verified by the verification node in the verification system.

By the way, a signature key and a verification key that are not duplicated in advance are assigned to each node by a certificate authority (CA). Signing key consists predetermined natural number (x), the verification key, GDH (GAP-Diffie-Hellman ) Group point on the elliptic curve is an element of _{(G 1) (g 1)} a unique signature key (x) It is preferable to consist of points (v = xg ₁ ) on the elliptic curve generated based on the above. With this configuration, it is difficult for a third party who does not know the signature key (x) to obtain the signature key (x) from the values of “v” and “g ₁ ”.

  Here, a specific signature scheme employed in the present embodiment will be described. In the aggregate signature system, a GAP-Diffie-Hellman (GDH) signature is adopted as a base signature scheme. The GDH signature is a signature that utilizes the fact that the Decision-Diffie-Hellman (DDH) problem can be solved by using a certain black box function e (P, Q) called pairing.

Next, the GDH signature using the pairing operation will be described. A GDH group has been defined in connection with the Diffie-Hellman problem on an elliptic curve. The GDH group will be briefly described. Let G ₁ and G _{2 be} a set of points on different elliptic curves. When g ₁ is an element of the set G ₁ and g ₂ is an element of the set G ₂ , the Decision Diffie-Hellman (DDH) problem and the Computational Diffie-Hellman (CDH) problem on the elliptic curve are defined as follows.

DDH problem: When there are natural numbers a, b, and c, and g _x , ag _x , bg _x , and cg _x (x is 1 and 2) are given, it is a problem that determines whether c = ab.
CDH problem: There is a, b, a natural number of _c, g _x, ag x, bg _{when x} is given, the problem of calculating abg _y (x is 1 and 2, y is 1 or 2).

At this time, the DDH problem is simple in terms of calculation amount, but if the CDH problem is difficult in terms of calculation amount, this set G _x is defined as a GDH group.

On the other hand, there are those that can define a black box function e (P, Q) called pairing that can have the following properties depending on P and Q as points on a certain elliptic curve. To do.
e (P, Q ₁ + Q ₂ ) = e (P, Q ₁ ) e (P, Q ₂ ) (1)
e (P ₁ + P ₂ , Q) = e (P ₁ , Q) e (P ₂ , Q) (2)
e (aP, bQ) = e (bP, aQ) = e (abP, Q) = e (P, abQ) = e (P, Q) ^ab (3)

Therefore, when g _x is a point on an elliptic curve that can be paired, if g _x , ag _x , bg _x , and cg _x are input to equation (3), for example,
e (ag ₁ , bg ₂ ) = e (g ₁ , g ₂ ) ^ab (4)
e (g ₁ , cg ₂ ) = e (g ₁ , g ₂ ) ^c (5)
It becomes. Therefore, whether or not “ab = c” can be determined based on whether or not both values match, and g ₁ and g ₂ can be elements of the GDH group G ₁ or G ₂ .

A GDH signature is constructed using this property. Assume that the sets G ₁ and G ₂ are GDH groups, and g ₁ and g ₂ are points that are elements of the sets G ₁ and G ₂ , respectively. Further, unlike the method in which the one-way hash function H ₂ is mapped and converted into numerical data having an arbitrary bit length size, which is normally used, to numerical data having a fixed bit length size,
H ₂ : {0, 1} ^* → G ₂
As is defined as a method of mapping transform the elements of the GDH group G ₂ represented numerical data size of any bit length as a point on an elliptic curve.

At this time, the GDH signature is defined as follows.
Key generation: A natural number x is selected, and v = xg ₁ is calculated from g ₁ . Let x be the signature key and point v on the elliptic curve be the verification key.
Signature: The signer calculates h = H ₂ (m) for the message “mε {0,1} ^* ”, and further calculates σ = xh using his signature key. Publish σ as a signature for m.
Verification: The verifier calculates h = H ₂ (m) from the message m, and prepares g ₁ and v belonging to the set G ₁ and h and σ belonging to the set G ₂ . e (g ₁ , σ) and e (v, h) are calculated, and if both values match, the signature σ is determined to be a correct signature.

At this time, since the value of h becomes an element of the set G ₂ , it can be expressed as h = yg ₂ using a certain natural number y. As a result, if the signature is correctly performed, (g ₁ , v, h, σ) = (g ₁ , xg ₁ , yg ₂ , xyg ₂ ). Therefore, if it is a valid signature, the pairing operation in the above verification is e (g ₁ , σ) = e (g ₁ , xyg ₂ ) = e (g ₁ , g ₂ ) ^xy = e (xg ₁ , yg ₂ ) = e (v, h) and the values match, so that verification is possible. Note that due to the difficulty of the CDH problem, which is a condition of the GDH group, it is impossible for a third party who does not know the signature key x to derive the signature σ from the values of g ₁ , g ₂ , v, and h.

  As shown in FIG. 1, a leaf node 10 which is the lowest node in the tree structure includes a storage unit 11, a leaf node one-way hash function calculation unit 12, a leaf node signature information generation unit 13, and a leaf node transmission unit. 14.

The storage unit 11 calculates the signature key (x _leaf ) assigned to itself (the node of the signer u _leaf ) and the value g ₁ (first value) belonging to the set G ₁ using this signature key. And a verification key (v _leaf = x _leaf g ₁ ) belonging to the set G ₁ generated by performing the above.

The leaf node one-way hash function calculation unit 12 performs a one-way hash function calculation on the message (m _leaf ) that is the signature target, and hashes belonging to the set G ₂ (second GDH group). Generate a value.

The leaf node signature information generation unit 13 calculates the hash value (h _leaf = H ₂ (m _leaf )) of the message (m _leaf ), which is the subject of signature, calculated by the leaf node one-way hash function calculation unit 12. performs calculation by own signature key _{(x leaf)} in contrast, generates signature information _{(σ leaf = x leaf h leaf} ).

The leaf node transmission unit 14 transmits the generated signature information (σ _leaf ) and message (m _leaf ) to the next (immediately above) node, that is, the intermediate node 20.

  Further, as shown in FIG. 2, the intermediate node 20, which is a node above the lowest (leaf node 10) in the tree structure, has a storage unit 21, an intermediate node reception unit 22, and an intermediate node one-way hash function operation. Unit 23, intermediate node signature information generation unit 24, and intermediate node transmission unit 25.

The storage unit 21 is generated by computing the signature key (x _up ) assigned to itself (signer u _up node) and the value g ₁ belonging to the set G ₁ using this signature key. The verification keys (v _up = x _up g ₁ ) belonging to the set G ₁ are stored.

The intermediate node reception unit 22 includes a message (m _low ) that is a signature target of one or a plurality of nodes (signer u _low nodes) directly below, signature information (σ _low ) generated by the nodes immediately below, Receive.

The intermediate node one-way hash function calculation unit 23 performs a one-way hash function calculation on each message (m _low ) received from the node immediately below and the message (m _up ) that is the signature target of the intermediate node. Te, to generate a hash value belonging to the set G _2.

The intermediate node signature information generation unit 24 performs an operation on the hash value (h _up = H ₂ (m _up )) obtained from its own message (m _up ) using its own unique signature key (x _up ). A result, and a result obtained by performing an operation with its own signature key (x _up ) on a hash value (h _low = H ₂ (m _low )) obtained from each message (m _low ) of the node immediately below, The signature information (σ _low ) of the node immediately below is summed to generate its own intermediate node signature information (σ _up = Σ _low (σ _low + x _up h _low ) + x _up h _up ) (Σ _low is The sum of all of one or more nodes).

When there is a next (immediately above) node, the intermediate node transmission unit 25 transmits a message (m _up ) that is a signature target of itself and intermediate node signature information (σ _up ) to the next node.

  According to such a configuration, each of the intermediate signatures in each intermediate node 20 has its own node for the hash value obtained from the message of the node immediately below and the hash value obtained from its own message. An operation is performed using the signature key assigned to the node, and the signature information generated by the nodes immediately below is summed to generate intermediate node signature information. This signature information holds the signature path in the tree structure up to its own node, and is generated only by points on the elliptic curve. That is, even if the number of signers (number of nodes) increases, the signature size does not increase and can be suppressed to a certain value or less.

  Further, as shown in FIG. 3, the root node 30 which is the highest intermediate node in the tree structure includes a storage unit 31, a root node reception unit 32, a root node one-way hash function calculation unit 33, and a root node. A signature information generation unit 34 and a disclosure unit 35 are provided.

Storage unit 31, and itself (signers _{u root} node) to Allocated signature key _{(x root),} for values _{g 1} belonging to the set _{G 1,} is generated by performing an operation by the signature key The verification keys belonging to the set G ₁ (v _root = x _root g ₁ ) are stored.

  The root node receiving unit 32 has the same configuration as the intermediate node receiving unit 22, and the root node one-way hash function calculating unit 33 has the same configuration as the intermediate node one-way hash function calculating unit 23. The root node signature information generation unit 34 has the same configuration as the intermediate node signature information generation unit 24.

The public unit 35 publishes the root node signature information generated by the root node signature information generation unit 34. According to such a configuration, the root node 30 discloses the signature information (σ _root ) generated by itself as public signature information (σ) to other nodes, particularly the verification node 40 in the verification system described later. Can do.

  In addition, the publishing unit 35 also publishes information on the arrangement of the signers in the tree structure indicating the signature order and the correspondence between each signer and the message that has signed.

  Next, a verification system that verifies the public signature information (σ) disclosed by the root node 30 will be described. As shown in FIG. 4, the verification node 40 included in the verification system includes a collection unit 41, a verification node one-way hash function calculation unit 42, and a verification unit 43.

The collection unit 41 collects messages (m _i ) and verification keys (v _i ) of all the nodes that have signed (the leaf node 10, the intermediate node 20, and the root node 30). At this time, the collection unit 41 does not necessarily obtain the information on the arrangement of the signers in the tree structure and the correspondence between each signer and the message that has signed, but obtains it from the root node 30. It is also preferable to do so. Even when the collection unit 41 does not obtain these pieces of information, the verification unit 43 calculates the public signature by calculating all combinations regarding the arrangement of the signers and the correspondences between the signers and the signed messages. It is possible to verify the validity of the information. However, if the collection unit 41 obtains these pieces of information and passes them to the verification unit 43, the calculation amount of the verification unit 43 can be reduced as compared with the case where there is no such information.

The verification node one-way hash function calculation unit 42 performs a one-way hash function calculation on each message (m _i ) collected by the collection unit 41 to obtain hash values belonging to each message set G _2. (H _i = H ₂ (m _i )) is generated.

  The verification unit 43 obtains the verification keys of all the nodes collected by the collection unit 41, the hash values obtained by the verification node one-way hash function calculation unit 42, the arrangement of the signers, and the signers and signatures. The validity of the public signature information (σ) is verified based on the information regarding the correspondence relationship with the performed message. At this time, if there is no information regarding the arrangement of the signers and the correspondence between each signer and the message that has been signed, the verification unit 43 calculates all the combinations related to these correspondences.

Specifically, the verification unit 43 uses the verification key and hash value of each node, the result of the pairing operation using the verification key and hash value of the same node, the verification key of a certain node, and the hash value of the previous node. A value obtained by multiplying all the results of the pairing operation, that is,
{Π _all-node (e (v _i , h _i ))} {Π (e (v _up , h _low ))}
Calculate Then, the verification unit 43, the calculation result, g ₁ and public signature information (sigma) the result of pairing computation by, i.e.,
e (g ₁ , σ)
If the two match, it is determined that the public signature information is valid, and if both do not match, it is determined that the public signature information is not valid.

  In this way, the verification node 40 uses the verification unit 43 to verify the verification keys of all the nodes, the hash value of the message, the arrangement of the signers, and the information on the correspondence between the signers and the messages that have been signed. The validity of the signature information of the public root node 30 can be verified based on. Here, with regard to the information regarding the arrangement of the signers and the correspondence relationship between each signer and the message that has been signed, the verification unit 43 can verify the validity of the signature information without these information. Is possible.

  Therefore, the verification system verifies the signature information published by the root node 30 only by numerical operation without verifying the individual signature information generated at each node, so It can be proved that the signatures have been made in the order as described above. That is, the verification operation can be efficiently performed by reducing the processing load of the verification node 40 without requiring another device for order management. The verification node 40 may be a node dedicated to verification, or may be any intermediate node 20 or root node 30 of the aggregate signature system.

  Next, a method for generating signature information for each node in the aggregate signature system and a method for verifying the validity of the signature information in the verification system will be described.

As shown in FIG. 5, the leaf node 10 (signer u _leaf ) performs a leaf node signature by _performing a leaf node one-way hash function calculation step ST1, a leaf node signature information generation step ST2, and a leaf node transmission step ST3. Information is generated and transmitted to the immediately above node (intermediate node 20).

In the leaf node one-way hash function computation step ST1, the leaf node one-way hash function computation unit 12 in the leaf node 10 performs a one-way hash function computation on its own message (m _leaf ).

In the leaf node signature information generation step ST2, the leaf node signature information generation unit 13 in the leaf node 10 _applies its signature key to the hash value (h _leaf ) calculated in the leaf node one-way hash function calculation step ST1. An operation is performed using (x _leaf ) to generate signature information (σ _leaf ).

In the leaf node transmission step ST3, the leaf node transmission unit 14 in the leaf node 10 transmits the signature information (σ _leaf ) generated in the leaf node signature information generation step ST2 to the intermediate node 20 immediately above.

As shown in FIG. 6, the intermediate node 20 (signer u _up ) other than the leaf node 10 performs an intermediate node reception step ST11, an intermediate node one-way hash function calculation step ST12, an intermediate node signature information generation step ST13, The intermediate node signature information is generated and transmitted to the intermediate node 20 immediately above by the intermediate node transmission step ST14.

In the intermediate node receiving step ST11, the intermediate node receiving unit 22 in the signer u _up node receives the message (m _low ) of the immediately lower node (signer u _low ) and the signature information (σ _low ) generated by the immediately lower node. ).

In the intermediate node one-way hash function calculation step ST12, the intermediate node one-way hash function calculation unit 23 in the node of the signer u _up performs the message (m _low ) and the message (m _low ) of the node immediately below. Each one-way hash function operation is performed.

In the intermediate node signature information generation step ST13, the intermediate node signature information generation unit 24 in the node of the signer u _up uses its own signature key (x _up ) for the hash value (h _up ) obtained by calculation from its own message. ), The result of operation with its own signature key (x _up ) on the hash value (h _low ) obtained from the message of the node immediately below, and received from the node immediately below The signature information (σ _low ) is summed to generate the signature information (σ _up ) of its own node.

In the intermediate node transmission step ST14, the intermediate node transmission unit 25 in the node of the signer u _up has its own message (m _up ) and its own node signature information (σ _up ) when there is a node immediately above the tree structure. ) To the immediately above node.

Further, as shown in FIG. 7, the _root node 30 (signer u _root ), which is the highest node in the tree structure, includes a root node reception step ST21, a root node one-way hash function calculation step ST22, and a root node. The public signature information (σ) in the aggregate signature system is disclosed by the signature information generation step ST23 and the signature information disclosure step ST24.

In the root node receiving step ST21, the root node receiving unit 32 in the root node 30 receives the message (m _low ) of the node immediately below (signer u _low ) and the signature information (σ _low ) generated by the node immediately below. To do.

In the root node one-way hash function calculation step ST22, the root node one-way hash function calculation unit 33 in the root node 30 applies to the message (m _low ) and the message (m _root ) of the node immediately below. Performs a one-way hash function operation.

In the root node signature information generation step ST23, the root node signature information generation unit 34 in the root node 30 calculates a hash value (h _root ) obtained by calculation from its own message by using its own signature key (x _root ). a result of a result of a hash value obtained by calculation from the message of the node immediately below with respect to (h _low) was calculated by the own signature key (x _root), the signature information received from the node immediately below (Σ _low ) is summed and signature information (σ _root ) of its own node is generated.

  In the signature information disclosure step ST24, the disclosure unit 35 in the root node 30 discloses the signature information generated in the root node signature information generation step ST23 as public signature information (σ).

  As described above, according to the aggregate signature method according to the aggregate signature system, in each intermediate node 20, the hash value obtained from the message of the node immediately below and the hash value obtained from the own message are obtained. The calculation is performed using the signature key assigned to its own node, and the signature information generated by the node immediately below is summed to generate intermediate node signature information. This signature information holds a signature path to its own node and is generated only by points on the elliptic curve. That is, even if the number of signers (number of nodes) increases, the signature size does not increase and can be suppressed to a certain value or less.

  Further, as shown in FIG. 8, the verification node 40 in the verification system verifies the validity of the public signature information (σ) by the collection step ST31, the verification node one-way hash function calculation step ST32, and the verification step ST33. Validate.

In the collecting step ST31, the collecting unit 41 collects the messages (m _i ) of all the nodes for which the signature has been performed, and the verification keys (v _i ) of all the nodes.

  In the verification node one-way hash function calculation step ST32, the verification node one-way hash function calculation unit 42 performs a one-way hash function calculation on each of the messages collected in the collection step ST31.

  In the verification step ST33, the verification unit 43 is based on the verification keys of all the nodes collected in the collection step ST31 and the hash values obtained in the verification node one-way hash function calculation step ST32 from the messages of all the nodes. The validity of the public signature information (σ) is verified.

  In this way, the verification system verifies the validity of the public intermediate node signature information (public signature information σ) based on the verification keys of all the nodes and the hash values of the messages in the verification step ST33. be able to.

  Therefore, in the verification method according to the verification system, by verifying the signature information published by the root node 30 only by numerical operation without verifying individual signature information generated at each node, the tree structure It is possible to prove in what order the nodes have been signed. In other words, the verification operation can be executed while reducing the processing load of the verification process ST33 without requiring another device for order management.

[Example]
Here, the operation of the aggregate signature system in the case where the tree structure is composed of three levels of the triple tree will be specifically described with reference to FIG. In the following, it is assumed that the first layer is the root node 30, the second layer is the intermediate node 20, and the third layer is the leaf node 10.

That is, one root node 30 is arranged in the first layer. In the second layer, three intermediate nodes 20 are arranged, and u ₁ to u ₃ are arranged immediately below u _root . Further, the third layer, is arranged a leaf node 10 nine, _{u 13} from _{u 11} is arranged directly below the _{u 1, u 23} from _{u 21} is arranged directly below the _{u 2,} directly below the _{u 3} u ₃₁ to u ₃₃ are arranged.

In addition, the certificate authority (CA) assigns a signature key and a verification key that do not overlap each node in advance as follows. Note that s and t are integer signs such that 1 ≦ s ≦ 3 and 1 ≦ t ≦ 3, respectively.
The first layer :( signature key, the verification _{key) = (x root, v root} ) = (x root, x root g 1)
Second layer: (signature key, verification key) = (x _s , v _s ) = (x _s , x _s g ₁ )
3rd layer: (signature key, verification key) = (x _st , v _st ) = (x _st , x _st g ₁ )

The nine leaf nodes 10 (users u _st ) of the third layer obtain hash values (h _st = H ₂ (m _st )) for the messages (m _st ) that are their signature targets, The signature information (σ _st = x _st h _st ) is generated by performing an operation using the signature key x _st of its own. In addition, the leaf node 10 (user u _st ) transmits the generated signature information (σ _st ) and the message (m _st ) to the immediately upper node (user u _s ).

The three intermediate nodes 20 (user u _s ) in the second layer first obtain a hash value (h _s = H ₂ (m _s )) from the message (m _s ) that is the subject of signature.
Then, the intermediate node 20 (user _{u s)} from the message _{(m s1, m s2, m} s3) received from the node immediately below (user _{u s1, u s2, u s3} ), the hash value _(h s1 = H ₂ (m _s1 ), h _s2 = H ₂ (m _s2 ), h _s3 = H ₂ (m _s3 )).

Further, the intermediate node 20 (user u _s ) uses the signature information (σ _s1 , σ _s2 , σ _s3 ) received from the node immediately below,
σ _s = σ _s1 + x _sh h _s1 + σ _s2 + x _sh h _s2 + σ _s3 + x _sh h _s3
+ X _sh h _s (6)
= X _s1 h _s1 + x _s h _s1 + x _s2 h _s2 + x _s h _s2
+ X _s3 h _s3 + x _s h _s3 + x _s h _s (7)
Calculate Then, the intermediate node 20 (user u _s ) transmits the generated signature information (σ _s ) and the message (m _s ) to the node immediately above (user u _root ).

The root node 30 (user u _root ) of the first layer first obtains a hash value (h _root = H ₂ (m _root )) from the message (m _root ) to be signed.
Next, the root node 30 (user u _root ) obtains the hash value (h ₁ = H) from the messages (m ₁ , m ₂ , m ₃ ) received from the nodes directly below (users u ₁ , u ₂ , u ₃ ). ₂ (m ₁ ), h ₂ = H ₂ (m ₂ ), h ₃ = H ₂ (m ₃ )).

Furthermore, the root node 30 (user u _root ) uses the signature information (σ ₁ , σ ₂ , σ ₃ ) received from the node immediately below,
σ = σ ₁ + x _root h ₁ + σ ₂ + x _root h ₂ + σ ₃ + x _root h ₃
+ X _root h _root (8)
_{= X 11 h 11 + x 1} h 11 + x 12 h 12 + x 1 h 12
+ X ₁₃ h ₁₃ + x ₁ h ₁₃ + x ₁ h ₁ + x _root h ₁
+ X ₂₁ h ₂₁ + x ₂ h ₂₁ + x ₂₂ h ₂₂ + x ₂ h ₂₂
+ X ₂₃ h ₂₃ + x ₂ h ₂₃ + x ₂ h ₂ + x _root h ₂
+ X ₃₁ h ₃₁ + x ₃ h ₃₁ + x ₃₂ h ₃₂ + x ₃ h ₃₂
+ X ₃₃ h ₃₃ + x ₃ h ₃₃ + x ₃ h ₃ + x _root h ₃
+ X _root h _root (9)
Calculate Then, the root node 30 (user u _root ) publishes the generated signature information (σ) as aggregate signature information for all users.

The root node 30 also discloses the signature position information in the signer's tree structure. The signature position information is, for example, {(u ₁₁ , u ₁ ), (u ₁₂ , u ₁ ), (u ₁₃ , u ₁ ), (u ₂₁ , u ₂ ), (u ₂₂ , u ₂ ), (u ₂₃ , u ₂ ), (u ₃₁ , u ₃ ), (u ₃₂ , u ₃ ), (u ₃₃ , u ₃ ), (u ₁ , u _root ), (u ₂ , u _root ), (u ₃ , u _root )} as a sequence of adjacent node combinations.

  In this way, the aggregate signature system can represent the tree structure by representing the relationship between two nodes that are continuous (adjacent) on the tree structure by the product of the signature key and the hash value. Even if the number of nodes increases, the public signature information (σ) generated by the root node 30 is disclosed. Since this signature information is a point on an elliptic curve, the size (capacity) of the information does not increase and can be suppressed to a certain value or less, and an ordered aggregate signature can be generated efficiently.

  The verification node 40 verifies the validity of the public signature information (σ) by the following verification process 1 to verification process 3.

(Verification process 1) The verification node 40 is a message (m _root , m ₁ , m ₂ , m ₃ , m ₁₁ , m ₁₂ , m ₁₃ , m ₂₁ , m ₂₂ ) that all nodes that have signed the signatures. , M ₂₃ , m ₃₁ , m ₃₂ , m ₃₃ ) and hash values (h _root = H ₂ (m _root ), h ₁ = H ₂ (m ₁ ), h ₂ = H ₂ ( m ₂ ), h ₃ = H ₂ (m ₃ ), h ₁₁ = H ₂ (m ₁₁ ), h ₁₂ = H ₂ (m ₁₂ ), h ₁₃ = H ₂ (m ₁₃ ), h ₂₁ = H ₂ ( m ₂₁ ), h ₂₂ = H ₂ (m ₂₂ ), h ₂₃ = H ₂ (m ₂₃ ), h ₃₁ = H ₂ (m ₃₁ ), h ₃₂ = H ₂ (m ₃₂ ), h ₃₃ = H ₂ ( m ₃₃ )).

(Verification Process 2) Verification node 40, the verification keys of all the nodes performing the signature _{(v root, v 1, v} 2, v 3, v 11, v 12, v 13, v 21, v 22, v 23 , V ₃₁ , v ₃₂ , v ₃₃ ).

(Verification process 3) The verification node 40 verifies the validity of the publicly available public signature information (σ). Specifically, the verification node 40 uses the hash value obtained in the verification process 1 and the verification keys of all the collected nodes,
e (v ₁₁ , h ₁₁ ) · e (v ₁ , h ₁₁ )
_{· E (v 12, h 12} ) · e (v 1, h 12)
_{· E (v 13, h 13} ) · e (v 1, h 13)
E (v ₁ , h ₁ ) e (v _root , h ₁ )
_{· E (v 21, h 21} ) · e (v 2, h 21)
E (v ₂₂ , h ₂₂ ) e (v ₂ , h ₂₂ )
E (v ₂₃ , h ₂₃ ) e (v ₂ , h ₂₃ )
E (v ₂ , h ₂ ) e (v _root , h ₂ )
_{· E (v 31, h 31} ) · e (v 3, h 31)
E (v ₃₂ , h ₃₂ ) e (v ₃ , h ₃₂ )
E (v ₃₃ , h ₃₃ ) e (v ₃ , h ₃₃ )
E (v ₃ , h ₃ ) e (v _root , h ₃ )
・ E (v _root , h _root ) (10)
And confirms that this value matches the value of e (g ₁ , σ). If these values match, it is determined that the public signature information (σ) is valid.

Here, when “e (g ₁ , σ)” in (Verification process 3) is expanded,
e (g ₁ , σ)
= E (g ₁ , x ₁₁ h ₁₁ ) · e (g ₁ , x ₁ h ₁₁ )
E (g ₁ , x ₁₂ h ₁₂ ) e (g ₁ , x ₁ h ₁₂ )
E (g ₁ , x ₁₃ h ₁₃ ) e (g ₁ , x ₁ h ₁₃ )
E (g ₁ , x ₁ h ₁ ) e (g ₁ , x _root h ₁ )
E (g ₁ , x ₂₁ h ₂₁ ) e (g ₁ , x ₂ h ₂₁ )
E (g ₁ , x ₂₂ h ₂₂ ) e (g ₁ , x ₂ h ₂₂ )
E (g ₁ , x ₂₃ h ₂₃ ) · e (g ₁ , x ₂ h ₂₃ )
E (g ₁ , x ₂ h ₂ ) e (g ₁ , x _root h ₂ )
E (g ₁ , x ₃₁ h ₃₁ ) e (g ₁ , x ₃ h ₃₁ )
E (g ₁ , x ₃₂ h ₃₂ ) · e (g ₁ , x ₃ h ₃₂ )
E (g ₁ , x ₃₃ h ₃₃ ) e (g ₁ , x ₃ h ₃₃ )
E (g ₁ , x ₃ h ₃ ) e (g ₁ , x _root h ₃ )
E (g ₁ , x _root h _root ) (11)
_{= E (x 11 g 1,} h 11) · e (x 1 g 1, h 11)
_{· E (x 12 g 1,} h 12) · e (x 1 g 1, h 12)
_{· E (x 13 g 1,} h 13) · e (x 1 g 1, h 13)
E (x ₁ g ₁ , h ₁ ) e (x _root g ₁ , h ₁ )
_{· E (x 21 g 1,} h 21) · e (x 2 g 1, h 21)
E (x ₂₂ g ₁ , h ₂₂ ) e (x ₂ g ₁ , h ₂₂ )
_{· E (x 23 g 1,} h 23) · e (x 2 g 1, h 23)
E (x ₂ g ₁ , h ₂ ) e (x _root g ₁ , h ₂ )
E (x ₃₁ g ₁ , h ₃₁ ) e (x ₃ g ₁ , h ₃₁ )
E (x ₃₂ g ₁ , h ₃₂ ) e (x ₃ g ₁ , h ₃₂ )
_{· E (x 33 g 1,} h 33) · e (x 3 g 1, h 33)
E (x ₃ g ₁ , h ₃ ) e (x _root g ₁ , h ₃ )
_{· E (x root g 1,} h root) ··· (12)
= E (v ₁₁ , h ₁₁ ) · e (v ₁ , h ₁₁ )
_{· E (v 12, h 12} ) · e (v 1, h 12)
_{· E (v 13, h 13} ) · e (v 1, h 13)
E (v ₁ , h ₁ ) e (v _root , h ₁ )
_{· E (v 21, h 21} ) · e (v 2, h 21)
E (v ₂₂ , h ₂₂ ) e (v ₂ , h ₂₂ )
E (v ₂₃ , h ₂₃ ) e (v ₂ , h ₂₃ )
E (v ₂ , h ₂ ) e (v _root , h ₂ )
_{· E (v 31, h 31} ) · e (v 3, h 31)
E (v ₃₂ , h ₃₂ ) e (v ₃ , h ₃₂ )
E (v ₃₃ , h ₃₃ ) e (v ₃ , h ₃₃ )
E (v ₃ , h ₃ ) e (v _root , h ₃ )
・ E (v _root , h _root ) (13)
Thus, if the signature process is correctly performed, the expression (10) is satisfied. Therefore, the aggregate signature can be verified from the public verification key of the user and the hash values obtained from all the messages.

Here, paying attention to the value of sigma, the user _{u st} is performed signature processing only _{h st (the} calculation of _x st _{h st),} the other _{h s} and _{h root} doing such a signature process Absent. As a result, it can be seen that the user _ust is the first, that is, the signer of the leaf node 10 in the tree structure.

In addition, since the item “x _s h _st ” indicates that the user u _s is performing the signature process on h _st that the first signer has signed, this user u It can be seen that _s is the second (intermediate node 20) signer. User _{u s} is performing the signature process on _{h s (x s h s)} at the same time. Similarly, the section “x _root h _s ” indicates that it is the user u _root that is performing the signature processing on this h _s , so this user u _root is the third signer. I understand that there is.

Further, since there is no user who performs the signature processing for h _root and the user u _root has converged, it can be seen that the third signer is the root node 30.

Further, in the equation (11), a third party who does not know the signature key that is the secret information from the CDH problem or the discrete logarithm problem on the elliptic curve can change each term (x _α h _β or x _β h _β ) on the right side. Since it cannot be removed arbitrarily, it is impossible to change the order by a third party. In other words, the present signature scheme adopted by the aggregate signature system and the verification system can express the signature order in the tree structure by the product of the signature key and the hash value.

  Even if the number of signers (the number of nodes) increases, the public information is only the public signature information (σ). Since the public signature information (σ) is a point on one elliptic curve, the size (capacity) of the information does not increase and can be suppressed to a certain value or less.

  Further, in the verification system, it is possible to prove in what order the nodes have been signed by performing verification only by the numerical operation shown in the verification process 3. Therefore, it is possible to efficiently perform the verification work by reducing the processing load of the verification system without separately preparing an apparatus for order management.

Second Embodiment
Hereinafter, a second embodiment which is an example of an embodiment of the present invention will be described. In addition, about the structure similar to 1st Embodiment, the same code | symbol is attached | subjected and description is abbreviate | omitted or simplified.

In the aggregate signature system according to the present embodiment, the configuration of the leaf node one-way hash function calculation unit 12 and the leaf node transmission unit 14 of the leaf node 10 is different from that of the first embodiment.
That is, the leaf node transmission unit 14 uses the hash value (h _leaf ) and the leaf node signature information (σ _leaf ), which are the calculation results of the leaf node one-way hash function calculation unit 12, as a node directly above (intermediate node 20). Send to.

The intermediate node 20 is different from the first embodiment in the configuration of an intermediate node receiver 22, an intermediate node one-way hash function calculator 23, and an intermediate node transmitter 25.
That is, the intermediate node receiving unit 22 receives the hash value (h _low ) from the node immediately below instead of the message (m _low ) and supplies the hash value (h _low ) to the intermediate node signature information generation unit 24. This eliminates the need for the intermediate node 20 to perform a one-way hash function operation on the message (m _low ) of the immediately preceding node.

Further, the intermediate node transmission unit 25 transmits the hash value (h _up ) and the intermediate node signature information (σ _up ), which are the calculation results of the intermediate node one-way hash function calculation unit 23, to the node immediately above.

The root node 30 is different from the first embodiment in the configuration of the root node receiving unit 32 and the root node one-way hash function calculating unit 33.
That is, the root node receiving unit 32 receives a hash value (h _low ) instead of a message (m _low ) from a node immediately below and supplies the hash value (h _low ) to the root node signature information generating unit 34. As a result, the root node 30 does not need to perform a one-way hash function operation on the message (m _low ) of the node immediately below.

  In the verification system according to the present embodiment, the configuration of the collection node 41 of the verification node 40 is different from that of the first embodiment. Furthermore, the verification node 40 does not require the verification node one-way hash function calculation unit 42 in the first embodiment.

That is, the collecting unit 41 supplies from each node, the hash value instead of the message _{(m i) (h i)} received by the verification unit 43. This eliminates the need for the verification node 40 to perform a one-way hash function operation on the message (m _i ) of each node.

According to this embodiment, the processing load of the one-way hash function calculation in each node can be reduced.
Specifically, the processing load of the intermediate node one-way hash function calculation step ST12 and the root node one-way hash function calculation step ST22 in the first embodiment is reduced, and the verification node one-way hash function calculation step ST32 is It becomes unnecessary.

It should be noted that between the nodes, it suffices that either the message (m _i ) or the hash value (h _i ) is transmitted and received, and it does not have to be unified within the aggregate signature system and the verification system. Moreover, it is good also as transmitting and receiving both a message and a hash value.

  Since the aggregate signature system and the verification system in each embodiment described above target independent messages at each node, for example, as in the case of generating content by collecting signed materials, the subordinate (partial ) To a higher-level (whole) bottom-up signature scheme.

In each of the above-described embodiments, the two arguments that are inputs to the pairing function are expressed as scalar multiples of the points g ₁ or g ₂ on the elliptic curve that can be paired. The curve differs between the first argument and the second argument. That is, the for the first argument of the pairing function and for the second argument, two points on different elliptic curve, respectively (G ₁ or G ₂₎ (g ₁ or g ₂₎ is given. Specifically, the verification key for the first argument is a scalar multiple of g ₁ (point on G ₁ ), and the hash value and signature information for the second argument is a scalar multiple of g ₂ (point on G ₂ ). It becomes.

As a result, the number of computations may increase, but since the processing can be performed in parallel in the computation of the pairing function, the computation time can be expected to be shortened.
Also, if a defect is found in either the set G ₁ or G ₂ , the aggregate signature system and the verification system are maintained by sharing one or exchanging it with another GDH group.

  As mentioned above, although embodiment of this invention was described, this invention is not restricted to embodiment mentioned above. The effects described in the embodiments of the present invention are only the most preferable effects resulting from the present invention, and the effects of the present invention are limited to those described in the embodiments of the present invention. is not.

  In the above-described embodiment, the root node 30 includes the public unit 35, but may include other nodes (intermediate node 20, leaf node 10). In this case, the verification node 40 can verify the validity of the signature path leading to the disclosed node based on the published signature information. Further, the disclosure unit 35 of each node may disclose the verification key of its own node and provide it to the verification node 40.

In the above-described embodiment, the signature key and the verification key are assigned by the certificate authority. However, the present invention is not limited to this. For example, the aggregate signature system determines natural numbers x a signature key, and a value g ₁ belonging to the set G _1, may be calculated by calculating a verification key (v = xg _1).

  In the above-described embodiment, the ordered multiple signature in the tree structure in which a plurality of nodes directly below the intermediate node 20 is described, but the present invention is not limited to this. In other words, the present invention can be applied to a case where there is a single node directly below the intermediate node 20 and a plurality of nodes are arranged in a line.

  In this case, since the aggregate signature system and the verification system are intended to sign independent messages at each node, for example, a continuous operation that receives the previous message and adds the next message, such as an electronic bulletin board or a blog comment. Can be used against.

In this case, the signing order information (signature position information) of the signer disclosed by the root node 30 (final node) is, for example, {(1, u ₁ ), (2, u ₂ ),. k, u _k )}, and is expressed as a sequence of nodes to which sequence numbers are added.

  A series of processing by the aggregate signature system and the verification system can also be performed by software. When a series of processing is performed by software, a program constituting the software is installed in a general-purpose computer or the like. The program may be recorded on a removable medium such as a CD-ROM and distributed to the user, or may be distributed by being downloaded to the user's computer via a network.

DESCRIPTION OF SYMBOLS 10 Leaf node 11 Memory | storage part 12 Leaf node unidirectional hash function calculating part 13 Leaf node signature information generation part 14 Leaf node transmission part 20 Intermediate node 21 Storage part 22 Intermediate node receiving part 23 Intermediate node unidirectional hash function calculating part 24 Intermediate node signature information generation unit 25 Intermediate node transmission unit 30 Root node 31 Storage unit 32 Root node reception unit 33 Root node one-way hash function calculation unit 34 Root node signature information generation unit 35 Disclosure unit 40 Verification node 41 Collection unit 42 Verification Node one-way hash function calculation unit 43 Verification unit

Claims (8)

An aggregate signature system for performing an ordered aggregate signature from one node to another,
In each node, the first key generated by computing the signature key composed of a predetermined natural number and the first value belonging to the first GDH (GAP-Diffie-Hellman) group using the signature key. Each of the verification keys belonging to the GDH group of
A receiving unit that receives a message to be signed by the immediately preceding node or a hash value of the message, and signature information of the immediately preceding node when the immediately preceding node exists;
If there is a message of its own and the previous node, perform a one-way hash function operation on the message of the previous node to generate a hash value belonging to the second GDH group of each message A signature node one-way hash function computing unit,
When the hash value of its own message is calculated using its own signature key and the previous node exists, the hash value of the message of the previous node is calculated using the signature key of its own node And a signature information generation unit that generates the signature information of itself by summing together the signature information of the previous node and the signature information of the previous node;
An aggregate signature system comprising: a transmitting unit that transmits its own message or a hash value of the message and its own signature information to the immediately subsequent node when the immediately following node exists.   When there are a plurality of the immediately preceding nodes, the signature information generation unit performs a calculation on the hash value of its own message using its signature key and the hash value of the message of each of the immediately preceding nodes. The aggregate signature system according to claim 1, wherein the signature information is generated by summing a plurality of results obtained by performing the calculation using the signature key of the node itself and the signature information of each of the immediately preceding nodes.   The aggregate signature system according to claim 1, wherein each of the nodes includes a public unit that discloses its own signature information.   The aggregate signature system according to claim 3, wherein the disclosure unit further discloses order information of each node. A verification system for verifying signature information disclosed by the disclosure unit provided in the aggregate signature system according to claim 3 or 4,
A collection unit that collects messages of all nodes in the process of generating the disclosed signature information or hash values of the messages, and verification keys of all the nodes;
A verification node one-way hash function operation unit that performs a one-way hash function operation on each message collected by the collection unit to generate a hash value belonging to the second GDH group of each message;
A verification system comprising: a verification unit that verifies the validity of the published signature information based on the verification keys of all the nodes and the hash values of the messages of all the nodes.   The verification unit multiplies the result of the pairing operation by the verification key and hash value of the same node and the result of the pairing operation by the hash value of the node immediately before the verification key of the certain node, Compared with the result of the pairing operation by the first value and the published signature information, if both match, it determines that the published signature information is valid, and if both do not match, the published 6. The verification system according to claim 5, wherein it is determined that the signed information is not valid. An aggregate signature method for performing an ordered aggregate signature from one node to another, comprising:
In each node, the first key generated by computing the signature key composed of a predetermined natural number and the first value belonging to the first GDH (GAP-Diffie-Hellman) group using the signature key. Each of the verification keys belonging to the GDH group of
Generation of a verification key for generating an own verification key belonging to the first GDH group by performing an operation on the first value belonging to the first GDH (GAP-Diffie-Hellman) group with the own signature key Process,
When the immediately preceding node exists, the receiving step of receiving the message to be signed by the immediately preceding node or the hash value of the message, and the signature information of the immediately preceding node;
If there is a message of its own and the previous node, perform a one-way hash function operation on the message of the previous node to generate a hash value belonging to the second GDH group of each message A signature node one-way hash function calculation step,
When the hash value of its own message is calculated using its own signature key and the previous node exists, the hash value of the message of the previous node is calculated using the signature key of its own node And a signature information generation step of generating the signature information of itself by summing up the result of performing and the signature information of the immediately preceding node;
An aggregate signature method that executes a transmitting step of transmitting an own message or a hash value of the message and an own signature information to the immediately following node when an immediately following node exists. An aggregate signature program for causing a computer to execute an aggregate signature method for performing an ordered aggregate signature from one node to another,
In each node, the first key generated by computing the signature key composed of a predetermined natural number and the first value belonging to the first GDH (GAP-Diffie-Hellman) group using the signature key. And a verification key belonging to each GDH group are assigned to each node.
Generation of a verification key for generating an own verification key belonging to the first GDH group by performing an operation on the first value belonging to the first GDH (GAP-Diffie-Hellman) group with the own signature key Process,
When the immediately preceding node exists, the receiving step of receiving the message to be signed by the immediately preceding node or the hash value of the message, and the signature information of the immediately preceding node;
If there is a message of its own and the previous node, perform a one-way hash function operation on the message of the previous node to generate a hash value belonging to the second GDH group of each message A signature node one-way hash function calculation step,
When the hash value of its own message is calculated using its own signature key and the previous node exists, the hash value of the message of the previous node is calculated using the signature key of its own node And a signature information generation step of generating the signature information of itself by summing up the result of performing and the signature information of the immediately preceding node;
An aggregate signature program for executing a transmission step of transmitting the message itself or the hash value of the message and the signature information of the message to the node immediately after the node immediately after the node exists.

Images