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

Description

  The present invention relates to an aggregate signature system using an electronic signature, a verification system, an aggregate signature method, and an 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 for performing signatures of a plurality of persons, multiple signatures (for example, refer to Non-Patent Document 1) and aggregate signatures (for example, refer to Non-Patent Document 2) that can verify respective signers belong to a specific group. A group signature (see, for example, Patent Document 1) that can guarantee that someone of the person who signed the document has signed 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 D. Boneh, C.I. Gentry, B.M. Lynn, and H.M. Shacham, “Aggregate and Verifiably Encrypted Signs from Bilinear Map,” Advances in Cryptology-EUROCRYPT 2003, LNCS 2656, pp. 416-432, Springer-Verlag, 2003

  However, in these multiple signatures, aggregate signatures, and group signatures, all signers are expressed in an equivalent relationship. Therefore, it is not possible to express how electronic data has been distributed in the signature system using only these signature methods.

  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 are methods that can be performed only when there is only one user before and after each signer, for example, a mesh in which relationships between users are one-to-many or many-to-many. In the case of a structure, the existing signature scheme cannot express this structure. In addition, since these signature schemes are schemes 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 problems, an object of the present invention is to provide an aggregate signature system, a verification system, an aggregate signature method, and an aggregate signature program that can represent a mesh structure.

  The present invention provides the following solutions.

  (1) An aggregate signature system according to the present invention is an aggregate signature system in which a plurality of general nodes are configured in a mesh structure, and an aggregate signature is performed between the plurality of general nodes. A unique signature key and a unique verification key that are not duplicated are assigned in advance, and each general node in the mesh structure is a general node that performs a one-way hash function operation on a message to be signed between adjacent general nodes. General node signature information generation for generating own signature information by calculating with a unique signature key for the hash value calculated by the directional hash function calculation unit and the general node one-way hash function calculation unit Between the neighboring general nodes by the signature information received from the common part and the neighboring general node A representative node that supervises the plurality of general nodes, and a public node comprising a sum of the multiple signature information unique between adjacent general nodes in the mesh structure. A public multiple signature information generation unit that generates multiple signature information; and a public list information generation unit that generates public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and messages. .

  According to such a configuration, the aggregate signature system includes a plurality of general nodes configured in a mesh structure, and generates multiple signature information by computation between two general nodes that are continuous (adjacent) on the mesh structure. Then, the aggregate signature system publishes the sum of multiple signature information as public multiple signature information of the entire mesh structure at a representative node that supervises a plurality of general nodes. Further, the aggregate signature system publishes public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and the message.

  Therefore, the aggregate signature system can express the mesh structure by generating multiple signature information that represents the relationship between two consecutive (adjacent) nodes on the mesh structure, and summing them with the representative node. .

  (2) In the aggregate signature system, a unique signature key and a unique verification key are assigned in advance to the representative node, and a representative node that performs a one-way hash function operation on a message that is a signature target of the representative node. A representative node signature information generation unit that generates a representative node signature information by calculating a hash value calculated by the directional hash function calculation unit and the representative node one-way hash function calculation unit using its own unique signature key. The public multiple signature information generation unit generates the public multiple signature information including the representative node signature information, and the public list information generation unit includes the representative node, the representative node, and a message. The public list information is generated including information indicating the correspondence relationship between

  According to such a configuration, the aggregate signature system publishes, as the public multiple signature information of the entire mesh structure, the representative node obtained by adding the representative node signature information to the sum of the multiple signature information. Further, the aggregate signature system publishes public list information including information indicating the correspondence between the representative node and the message in addition to the combination of the adjacent general nodes and the correspondence between the adjacent general node and the message. .

  Therefore, the aggregate signature system generates multiple signature information representing the relationship between two general nodes that are continuous (adjacent) on the mesh structure, sums them at the representative node, and adds the signature information of the representative node. By doing so, the mesh structure including the representative node can be expressed.

  (3) In the aggregate signature system, the multiple signature information generation unit generates unique multiple signature information between the adjacent general nodes only at one of the adjacent general nodes.

  According to such a configuration, the aggregate signature system can avoid duplication of generated multiple signature information, so that the number of computations and the number of communications are reduced, and the processing load is reduced.

  (4) In the aggregate signature system, the unique signature key includes a predetermined natural number, and the unique verification key includes a point on an elliptic curve that is an element of a GDH (GAP-Diffie-Hellman) group and the It consists of points on the elliptic curve generated based on the unique signature key.

  According to such a configuration, the aggregate signature system makes it difficult for a third party who does not know the unique signature key to obtain the unique signature key from a point on the elliptic curve that is an element of the GDH group. can do. Even if the number of general nodes or the number of connections (neighboring) increases in the mesh structure, the public multiple signature information generated at the representative node is released. Since this is a point on the elliptic curve, the size (capacity) of the information does not increase, it can be suppressed to a certain value or less, and signature information can be generated efficiently.

  (5) A verification system according to the present invention is a verification system for verifying the public multiple signature information generated by the aggregate signature system, wherein a one-way hash function operation is performed on a message included in the public list information. A verification node one-way hash function calculation unit to perform, a collection unit that collects unique verification keys of all nodes included in the public list information, a hash value calculated by the verification node one-way hash function calculation unit, A verification unit that verifies the validity of the public multiple signature information based on the unique verification keys of all the nodes collected by the collection unit and the public list information.

  According to such a configuration, the verification system verifies the validity of the public multiple signature information by the verification unit based on the unique verification keys of all the public nodes.

  Therefore, in the verification system, the relationship is constructed by the mesh structure by verifying the public multiple signature information generated as a sum of these without verifying the individual multiple signature information generated at the general node. It can prove the situation of the node that is. In other words, the verification system can execute the verification work while reducing the processing load on the verification node.

  (6) The aggregate signature method according to the present invention is an aggregate signature method in which a plurality of general nodes are configured in a mesh structure, and an aggregate signature is performed between the plurality of general nodes. A unique signature key and a unique verification key that are not duplicated are assigned in advance, and each general node in the mesh structure is a general node that performs a one-way hash function operation on a message to be signed between adjacent general nodes. Directional hash function calculation step and general node signature information generation for calculating the hash value calculated in the general node one-way hash function calculation step using its own unique signature key and generating its own signature information Between the adjacent general nodes by the process, the signature information received from the adjacent general node, and its own signature information. And a representative node that supervises the plurality of general nodes includes a total sum of the multiple signature information unique between adjacent general nodes in the mesh structure. A public multiple signature information generating step for generating public multiple signature information, and a public list information generating step for generating public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and messages. Run.

  According to such a configuration, an effect similar to (1) can be expected when each node executes the aggregate signature method.

  (7) The aggregate signature program according to the present invention is an aggregate signature program for realizing a method of performing an aggregate signature between the plurality of general nodes by a computer, wherein the plurality of general nodes are configured in a mesh structure. Each general node is assigned a unique signature key and unique verification key that do not overlap each other in advance, and a general node one-way that performs a one-way hash function operation on a message to be signed between adjacent general nodes General node signature information generating step of calculating the hash value calculated in the common hash function calculating step and the hash value calculated in the general node one-way hash function calculating step with its own unique signature key and generating its own signature information And the signature information received from the adjacent general node and its own signature information. A multiple signature information generation step for generating unique multiple signature information between nodes is executed by each general node in the mesh structure, and is made up of a sum of unique multiple signature information between adjacent general nodes in the mesh structure A public multiple signature information generating step for generating multiple signature information, a public list information generating step for generating public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and the message, and It is executed by a representative node that supervises a plurality of general nodes.

  According to such a configuration, an effect similar to (1) can be expected by causing each node to execute the aggregate signature program.

  According to the present invention, an aggregate signature expressing a mesh structure can be performed.

It is a block diagram which shows the structure of the aggregate signature system which concerns on 1st Embodiment. It is a block diagram which shows the structure of the general node in the aggregate signature system which concerns on 1st Embodiment. It is a block diagram which shows the structure of the representative 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 verification system which concerns on 1st Embodiment. 5 is a flowchart for explaining a method for generating unique multiple signature information between adjacent general nodes in the first embodiment. 5 is a flowchart for explaining a method of generating public multiple signature information and public list information in the first embodiment. 5 is a flowchart for explaining a method of verifying the validity of public multiple signature information in the first embodiment. In 1st Embodiment, it is a figure where it uses for description about operation | movement of the aggregate signature system in an example of a mesh structure. It is a block diagram which shows the structure of the representative 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 verification system which concerns on 2nd Embodiment. In 2nd Embodiment, it is a flowchart with which it uses for description about the method of producing | generating public multiple signature information and public list information. In 2nd Embodiment, it is a figure where it uses for description about operation | movement of the aggregate signature system in an example of a mesh structure.

<First Embodiment>
Hereinafter, a first embodiment, which is an example of an embodiment of the present invention, will be described. In the aggregate signature system A according to the present embodiment, a plurality of general nodes B are configured in a mesh structure as shown in FIG. Then, the aggregate signature system A performs a multiple signature on unique electronic data (message) among the plurality of general nodes B, and publishes an electronic signature expressing the mesh structure by the representative node C. Further, the verification node D in the verification system verifies the validity of the electronic signature published by the representative node C. Thereby, the verification node D can confirm the arrangement | positioning of the entity comprised by the mesh structure shape, and the message showing the relationship between entities, and accompanying information.

  By the way, a unique signature key and a unique verification key that are not duplicated in advance are assigned to each general node B by a certificate authority (CA). The unique signature key is composed of a predetermined natural number (x), and the unique verification key is a point (g) on an elliptic curve that is an element of a GDH (GAP-Diffie-Hellman) group (G) and a unique signature key (x). It is preferable to consist of points (v = xg) on an elliptic curve generated based on the above. Such a configuration makes it difficult for a third party who does not know the unique signature key (x) to obtain the unique 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, 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 be a set of points on an elliptic curve. When “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 in the set G are defined as follows.

DDH problem: A problem of determining whether c = ab when there are natural numbers a, b, and c and g, ag, bg, and cg are given.
CDH problem: A problem of calculating abg when there is a natural number of a, b, and c, and g, ag, and bg are given.

  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 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 (aP, bQ) = e (bP, aQ) = e (abP, Q) = e (P, abQ) = e (P, Q) ^ab (1)

Therefore, when g is a point on an elliptic curve that can be paired, if g, ag, bg, and cg are input to Equation (1),
e (ag, bg) = e (g, g) ^ab (2)
e (g, cg) = e (g, g) ^c (3)
Thus, whether or not “ab = c” can be determined depending on whether or not both values match, and g can be an element of the GDH group G.

A GDH signature is constructed using this property. The set G is a GDH group, and g is a point that is an element of the set G. In addition, unlike the method in which the one-way hash function H is mapped and converted into numerical data having an arbitrary bit length size that is normally used, the numerical data having a fixed bit length size,
H: {0,1} ^* → G
It is defined that this is a method in which numerical data of an arbitrary bit length size is mapped and converted to elements of the GDH group G expressed as points 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, v, h, and σ. 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 the signature is valid, 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 that 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, v, and h.

  As shown in FIG. 2, the general node B in the mesh structure includes a storage unit B1, a general node one-way hash function calculation unit B2, a general node signature information generation unit B3, and a multiple signature information generation unit B4. .

The storage unit B1 stores a unique signature key (x _q ) and a unique verification key (v _q ) assigned to itself (signer u _q node).
General nodes one-way hash function calculation unit B2 is the signature target message representative of relationships and accompanying information to an adjacent common node (node signer _{u p) (m p-q} ) a one-way hash function operation Do.

The general node signature information generation unit B3 uses the hash value (h _pq = H (m _pq )) calculated by the general node one-way hash function calculation unit B2 based on its own signature key (x _q ). An operation is performed to generate its own signature information (x _q h _p-q ). Then, the general node signature information generation unit B3 transmits the generated signature information (x _q h _pq ) to another adjacent general node B.

Multisignature information generating unit B4, in the mesh structure, the signature information generated by the adjacent normal node B (node signer _{u p) (x p h p} -q), its own signature information _(x q _{h p -Q} ) is added to generate multiple signature information (σ _p-q = (x _p + x _q ) h _p-q ) unique between adjacent general nodes B (between u _p -u _q ). Then, the multiple signature information generation unit B4 transmits the generated multiple signature information (σ _p−q ) to the representative node C.

Here, the multiple signature information is generated for each of all combinations of the adjacent general nodes B in the mesh structure, and these are transmitted to the representative node C. Incidentally, multiple signature information (σ _p-q) is assumed to be generated in either one of the adjacent normal node B (u _p or u _q), information sent to the representative node C shall not overlap .

The representative node C representatives u _r to oversee general Node B configured mesh structure, as shown in FIG. 3 includes a public multisignature information generation unit C1, and the public list information generation unit C2.

  The public multiple signature information generation unit C1 sums the unique multiple signature information between one or a plurality of adjacent general nodes B in the mesh structure, and generates public multiple signature information (σ). Then, the public multiple signature information generation unit C1 transmits the generated public multiple signature information (σ) to the verification node D.

The public list information generation unit C2 includes public list information (L = {(up, u, u _p , u) that indicates a combination of one or a plurality of adjacent general nodes B in the mesh structure and a correspondence relationship between the adjacent general nodes B and the message. _q , m _p-q )}). Then, the public list information generation unit C2 transmits the generated public list information (L) to the verification node D.

As described above, the aggregate signature system A is composed of a plurality of general nodes B configured in a mesh structure and a representative node C, and between two general nodes B that are continuous (adjacent) on the mesh structure ( Any node generates multiple signature information (σ _p-q ) by calculation in the interval between u _p -u _q ). Then, the aggregate signature system A sums the multiple signature information (σ _p−q ) generated for all the general nodes B at the representative node C, and adds this to the public multiple signature information (( (σ = Σσ _p−q ).

Therefore, the aggregate signature system A performs signature processing from the values “h _p-q ” and “x _p + x _q ” corresponding to two continuous (adjacent) general nodes B on the mesh structure. Therefore, it can be understood by what kind of relationship the nodes have been signed. As a result, the arrangement of the general nodes B in the mesh structure is known. Also, a third party who does not know the signature key (x _p or x _q ) that is secret information from the CDH problem or the discrete logarithm problem on the elliptic curve creates multiple signature information (σ or σ _p-q ). Impossible.

  Even if the number of general nodes B and the number of adjacent (adjacent) nodes increase in the mesh structure, the public multiple signature information (σ) generated at the representative node C is disclosed. Since this public multiple signature information (σ) is a point on the elliptic curve, the size (capacity) of the information does not increase and can be suppressed to a certain value or less. Signature information can be generated.

  Next, a verification system for verifying public multiple signature information will be described. As shown in FIG. 4, the verification node D included in the verification system includes a verification node one-way hash function calculation unit D1, a collection unit D2, and a verification unit D3.

The verification node one-way hash function calculation unit D1 performs one-way hash function calculation on the message (m _p-q ) included in the public list information (L) as a signature target (h _p-q = H (m _p-q )).

The collection unit D2 collects the unique verification keys (v _p , v _q ,...) Of all nodes included in the public list information (L), that is, all the general nodes B that have signed the message. To do.

The verification unit D3 has the hash value (h _p-q ) calculated by the verification node one-way hash function calculation unit D1, and the unique verification keys (v _p , v _q ) of all the general nodes B collected by the collection unit D2. ) And the public list information (L), the validity of the public multiple signature information (σ) is verified.

Specifically, the verification unit D3 are combined _(u p, u _q) of the general node B that all adjacent obtained from the public list information (L) for _{"Πe (v p + v q,} h p-q) " And the validity of the public multiple signature information (σ) is verified by confirming that the calculation result matches the value of “e (g, σ)”.

  In this way, the verification node D verifies the validity of the public multiple signature information by the verification unit D3 based on the public verification keys of all the general nodes B.

  Therefore, in the verification system, the relationship is constructed by the mesh structure by verifying the public multiple signature information generated as a sum of these without verifying the individual multiple signature information generated at the general node B. It can prove the situation of the node that is. That is, the verification operation can be executed while reducing the processing load on the verification node D. The verification node D may be a node dedicated to verification, or may be any general node B or representative node C arranged on the mesh structure of the aggregate signature system A.

  Here, the verification node D does not necessarily need to obtain the public list information indicating the combination of the adjacent general nodes B and the correspondence relationship between the adjacent general nodes B and the signed messages. It is preferable to obtain it from node C. Even when the verification node D does not obtain the public list information, the verification unit D3 calculates all combinations regarding the combination of the adjacent general node B and the correspondence relationship between the adjacent general node B and the signed message. By doing so, it is possible to verify the validity of the public signature information. However, if the verification node D obtains the public list information and passes it to the verification unit D3, the calculation amount of the verification unit D3 can be reduced as compared with the case where this information is not available.

  Next, a method for generating public multiple signature information by the general node B and the representative node C in the aggregate signature system A and a method for verifying the validity of the public multiple signature information by the verification node D in the verification system will be described. .

As shown in FIG. 5, the general node B (signers u _p and u _q ) performs a general node one-way hash function calculation step ST1, a general node signature information generation step ST2, and a multiple signature information generation step ST3. The unique multiple signature information (σ _p-q ) is generated between adjacent general node Bs (between u _p -u _q ).

In general nodes one-way hash function calculation step ST1, the signer u general nodes one-way hash function calculation unit B2 at the node of the _p performs a one-way hash function operation on the message (m _p-q).

In general node signature information generation step ST2, the signer general node signature information generation unit B3 in the node u _p is computed hash values in the normal node one-way hash function calculation step ST1 (h _p-q) to its An operation is performed using the unique signature key (x _p ), and signature information (x _{ph pq} ) is generated.

In multi-signature information generation step ST3, the signer multiple signature information generation unit B4 in the node _{u q,} to the normal node signature information generated in the signature information generation step _{ST2 (x p h p-q} ), its Signature information (x _q h _p-q ) is added to generate unique multiple signature information (σ _p-q ) between adjacent general nodes B (between u _p -u _q ).

  Further, as shown in FIG. 6, the representative node C generates public multiple signature information (σ) and public list information (L) through a public multiple signature information generation step ST11 and a public list information generation step ST12. To do.

  In the public multiple signature information generation step ST11, the public multiple signature information generation unit C1 sums the unique multiple signature information between one or a plurality of adjacent general nodes B in the mesh structure, and generates public multiple signature information (σ) To do.

  In the public list information generation step ST12, the public list information generation unit C2 generates public list information (L) indicating a combination of adjacent general nodes B in the mesh structure and a correspondence relationship between the adjacent general nodes B and messages. To do.

As described above, according to the aggregate signature method according to the aggregate signature system A, any one of the nodes is multiplexed between two general nodes B (between u _p -u _q ) continuous (adjacent) on the mesh structure. Signature information (σ _p−q ) is generated by calculation. In the aggregate signature method according to the aggregate signature system A, the multiple signature information generated between all the general nodes B is summed at the representative node C, and this is added to the public multiple signature information (( (σ = Σσ _p−q ).

  Therefore, according to the aggregate signature method according to the aggregate signature system A, the relationship between two continuous (adjacent) general nodes B on the mesh structure is represented by multiple signature information using the sum of signature keys. Can be expressed by the representative node C to express the mesh structure. Even if the number of general nodes B and the number of adjacent (adjacent) nodes increase in the mesh structure, the public multiple signature information (σ) generated at the representative node C is disclosed. Since this is a point on the elliptic curve, the size (capacity) of the information does not increase and can be suppressed to a certain value or less, so the aggregate signature system A can efficiently generate the signature information. it can.

  Further, as shown in FIG. 7, the verification node D verifies the validity of the public multiple signature information (σ) by the verification node one-way hash function calculation step ST21, the collection step ST22, and the verification step ST23. .

In the verification node one-way hash function calculation step ST21, the verification node one-way hash function calculation unit D1 performs a one-way hash function calculation on the message (m _p-q ).

In the collection step ST22, the collection unit D2 collects the unique verification keys (v _p , v _q ) of all the general nodes B that have signed the message (m _p-q ).

In the verification step ST23, the verification unit D3 uses the hash value (h _p-q ) calculated in the verification node one-way hash function calculation step ST21, and the unique verification keys of all general nodes B collected in the collection step ST22 ( Based on v _p , v _q ), and public list information (L), the validity of the public multiple signature information (σ) is verified.

  In this way, the verification node D verifies the validity of the public multiple signature information through the verification step ST23 based on the public verification keys of all the general nodes B.

  Therefore, in the verification method according to the verification system, by verifying the public multiple signature information generated as a sum of these without verifying the individual multiple signature information generated in the general node B, the mesh structure It is possible to prove the situation of the node for which the relationship is established. That is, the verification work can be executed while reducing the processing load of the verification process ST23.

[Example]
Here, the operation of the aggregate signature system A will be specifically described using the mesh structure shown in FIG. 8 as an example. In this example, seven general nodes B from node 1 to node 7 are arranged in a mesh structure, node 1 and node 2, node 2 and node 3, node 3 and node 4, node 4 and node 5, node 5 and 6, node 6 and node 7, node 7 and node 1, node 2 and node 6, node 3 and node 5, and node 3 and node 7 respectively perform multiple signatures as adjacent nodes.

Further, the certificate authority (CA) previously assigns a unique signature key (hereinafter referred to as a signature key) and a unique verification key (hereinafter referred to as a verification key) that do not overlap each node. Specifically, a signature key and a verification key that do not overlap with other nodes are assigned to the nodes 1 to 7 as follows.
Node 1: (signature key, verification key) = (x ₁ , v ₁ ) = (x ₁ , x ₁ g)
Node 2: (signature key, verification key) = (x ₂ , v ₂ ) = (x ₂ , x ₂ g)
Node 3: (signature key, verification key) = (x ₃ , v ₃ ) = (x ₃ , x ₃ g)
Node 4: (signature key, verification key) = (x ₄ , v ₄ ) = (x ₄ , x ₄ g)
Node 5: (signature key, verification key) = (x ₅ , v ₅ ) = (x ₅ , x ₅ g)
Node 6: (signature key, verification key) = (x ₆ , v ₆ ) = (x ₆ , x ₆ g)
Node 7: (signature key, verification key) = (x ₇ , v ₇ ) = (x ₇ , x ₇ g)

First, each node obtains a hash value (h _p-q = H (m _p-q )) for a message (m _p-q ) representing a relationship with adjacent nodes and accompanying information.

Next, multiple signature information is generated between all adjacent nodes.
Specifically, for example, the node 1 (signer u ₁ ) generates signature information (x ₁ h _1-2 ) by multiplying the hash value h _1-2 by its signature key (x ₁ ), and the node 2 to send. The node 2 (signer u ₂ ) adds its own signature information (x ₂ h _1-2 ) to the signature information (x ₁ h _1-2 ) received from the node 1, and (4 The multiple signature information is generated according to the formula.
σ _1-2 = x ₁ h _1-2 + x ₂ h _1-2 = (x ₁ + x ₂ ) h _1-2 (4)

Note that either the node 1 or the node 2 may perform the calculation of the equation (4). That is, the node 2 may generate the signature information (x ₂ h _1-2 ) and then transmit it to the node 1, and the node 1 may generate the multiple signature information (σ _1-2 ).

Further, in the node 1 or the node 2, original data {(u ₁ , u ₂ , m _1-2 )} of public list information indicating a correspondence relationship between a combination of adjacent nodes and a message to be signed is generated.

Similarly, between other adjacent nodes, multiple signature information (σ _2-3 , σ _3-4 , σ _4-5 , σ _5-6 , σ _6-7 , σ _7-1 , σ _2-6 , σ _3-5 , σ _3-7 ) and public list information original data are generated.

When the original data of the multiple signature information and the public list information is generated between all the adjacent nodes, the representative node C (representative u _r ) has the multiple signature information (σ _p-q ) and the public list information. Collect the original data. Then, the representative node C adds all the collected multiple signature information (σ _p−q ), and generates public multiple signature information (σ) according to equations (5) to (6).

In addition, the representative node C combines the original data of all the collected public list information, and generates public list information (L) according to equation (7).

  Then, the representative node C publishes the generated public multiple signature information (σ) and public list information (L) as public information.

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

(Verification process 1) The verification node D _calculates a hash value (h _pq = H (m _pq )) for all messages (m _pq ) included in the public list information (L).
(Verification process 2) The verification node D verifies all the verification keys (v ₁ , v ₂ , v ₃ , v ₄ , v ₅ , v) of all the general nodes B that signed the message included in the public list information (L). ₆ , v ₇ ).

(Verification process 3) The verification node D verifies the validity of the public multiple signature information (σ) disclosed by the representative node C. Specifically, the verification node D has a hash value (h _pq = H (m _pq )) and a verification key (v ₁ , v ₂ , v ₃ , v ₄ , v ₅ , v ₆ , v _7. ) And the public list information (L), the calculation shown in the equations (8) to (10) is performed, and it is confirmed that the equation (10) and “e (g, σ)” match. If these values match, it is determined that the public multiple signature information (σ) is valid.

となる。署名の過程が正しく行われていれば、（１０）式と（１２）式は、一致する。このことにより、公開されている検証鍵から、公開多重署名情報（σ）の検証が可能となる。 Here, “e (g, σ)” in (Verification process 3) is expressed by Equation (6) and the nature of pairing.

It becomes. If the signing process is performed correctly, the expressions (10) and (12) match. This makes it possible to verify the public multiple signature information (σ) from the public verification key.

Further, (11) Focusing on formulas, corresponding to the general node B _{(u p} and _{u q)} of any adjacent, signature processing from a value of _{"h p-q"} and _"x p + _{x q"} is performed Therefore, the relationship between the nodes is shown.

  In this way, the verification system (verification node D) can grasp what kind of relationship has been signed on the mesh structure, and as a result, grasp the arrangement of the signers on the mesh structure. can do.

Moreover, the discrete logarithm problem on CDH problem and elliptic curve, a third party who does not know the signature key which is secret information, it is not possible to produce a sigma or sigma _p-q.

  That is, the present verification method employed by the verification system (verification node D) represents the relationship between two consecutive (adjacent) nodes on the mesh structure using the sum of the signature keys, and collects all of these at the representative node C. Thus, the mesh structure can be expressed.

  Even if the number of nodes increases, the public multiple signature information (σ) generated at the representative node C is disclosed, and since this is a point on the elliptic curve, the size (capacity) of the information Can be suppressed to a certain value or less, and signature information is efficiently generated.

Second Embodiment
Hereinafter, a second embodiment which is an example of an embodiment of the present invention will be described. The aggregate signature system A according to the present embodiment is different from the first embodiment in the configuration of the representative node C, and also performs signatures at the representative node C. The configuration of the verification node D in the verification system is also different. In addition, the same code | symbol is attached | subjected about the structure similar to 1st Embodiment, and description is abbreviate | omitted or simplified.

Representative node C representatives u _r to oversee general Node B configured mesh structure, as shown in FIG. 9, the public multiple signature information generation section C1, a public list information generation unit C2, a storage unit C3 The representative node unidirectional hash function calculation unit C4 and the representative node signature information generation unit C5 are provided.

The storage unit C3 stores the assigned unique signature key (x _r ) and the unique verification key (v _r ).
The representative node one-way hash function calculation unit C4 performs one-way hash function calculation on the message (m _r ) that is the signature target of itself (h _r = H (m _r )).

The representative node signature information generation unit C5 performs an operation on the hash value (h _r ) calculated by the representative node one-way hash function calculation unit C4 using its own unique signature key (x _r ), so that the representative node signature information ( σ _r = x _r h _r ).

The public multiple signature information generation unit C1 totals unique multiple signature information between one or a plurality of adjacent general nodes B in the mesh structure, and further, the representative node signature information (σ _{r 2} ) is included (added) to generate public multiple signature information (σ _with-root ). Then, the public multiple signature information generation unit C1 transmits the generated public multiple signature information (σ _with-root ) to the verification node D.

Publicized list information generation unit C2, the combination of the general node B to one or more adjacent in the mesh structure, and list information (L = {(u p showing the correspondence between the general node B and the message to the _adjacent, u _q , M _p-q )}). Furthermore, publicized list information generation unit C2 is in this list information (L), were synthesized information indicating a correspondence relationship between a representative node C and the message, Public list information _{(L with-root = {(} u r, null, m _r )} ∪L). Then, the public list information generation unit C2 transmits the generated public list information (L _with-root ) to the verification node D.

As described above, the aggregate signature system A is composed of a plurality of general nodes B configured in a mesh structure and a representative node C, and between two general nodes B that are continuous (adjacent) on the mesh structure ( Any node generates multiple signature information (σ _p-q ) by calculation in the interval between u _p -u _q ). Then, the aggregate signature system A sums the multiple signature information (σ _p-q ) generated for all the general nodes B at the representative node C. Further, the representative node C adds the representative node signature information (σ _r = x _r h _r ) indicating the representative node C to the sum of the multiple signature information to obtain the public multiple signature information (σ _{with-root) of the} entire mesh structure. = Σ _r + Σσ _p−q ).

Therefore, the aggregate signature system A performs signature processing from the values “h _p-q ” and “x _p + x _q ” corresponding to two continuous (adjacent) general nodes B on the mesh structure, The signature processing is performed from the values “h _r ” and “x _r ” unique to the representative node C. For this reason, the aggregate signature system A knows how the nodes have been signed. As a result, the arrangement of the general node B and the representative node C in the mesh structure is known. Further, from a CDH problem or a discrete logarithm problem on an elliptic curve, a third party who does not know the signature key (x _p , x _q or x _r ) that is secret information can obtain multiple signature information (σ _p-q , σ _r or σ It is impossible to create _with-root ).

Even if the number of general nodes B and the number of adjacent (adjacent) nodes increase in the mesh structure, the public multiple signature information (σ _with-root ) generated at the representative node C is disclosed. Since this public multiple signature information (σ _with-root ) 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. Signature information can be generated efficiently.

  Further, as shown in FIG. 10, the verification node D included in the verification system that verifies public multiple signature information includes a verification node one-way hash function calculation unit D1, a collection unit D2, and a verification unit D3.

The verification node one-way hash function calculation unit D1 performs one-way hash function calculation on the message (m _p-q and m _r ) that is a signature target included in the public list information (L _with-root ). .

The collection unit D2 includes the unique verification keys (v _p , v _q ) of all the nodes included in the public list information (L _with-root ), that is, all the general nodes B and representative nodes C that have signed the message. , V _r ).

The verification unit D3 includes the hash values (h _p-q and h _r ) calculated by the verification node one-way hash function calculation unit D1, and all the unique verification keys (v _p , v _q , Based on v _r ) and public list information (L _with-root ), the validity of the public multiple signature information (σ _with-root ) is verified.

Specifically, the verification unit D3 are combined _(u p, u _q) of the general node B that all adjacent obtained from the public list information _{(L with-root)} and representative node C _{(u r)} for the "e ( v _r , h _r ) Π e (v _p + v _q , h _p−q ) ”, and confirming that the result of the calculation matches the value of“ e (g, σ _with-root ) ” Validity of public multiple signature information (σ _with-root ) is verified.

  In this way, the verification node D verifies the validity of the public multi-signature information by the verification unit D3 based on the public verification keys of all the public nodes B and the representative nodes C that have been made public.

  Therefore, the verification system includes the representative node C by verifying the public multiple signature information generated including the sum of these without verifying the individual multiple signature information generated at the general node B. It is possible to prove the situation of the node whose relationship is constructed by the mesh structure. That is, the verification operation can be executed while reducing the processing load on the verification node D.

  Next, a method for generating public multiple signature information by the general node B and the representative node C in the aggregate signature system A and a method for verifying the validity of the public multiple signature information by the verification node D in the verification system will be described. .

As with the first embodiment (see FIG. 5), the general node B (signers u _p and u _q ) performs a general node one-way hash function calculation step ST1, a general node signature information generation step ST2, and a multiple signature. the information generating step ST3, generates the adjacent normal node B _(u p -u _q between) specific to multiple signature information (σ _p-q).

Further, as shown in FIG. 11, the representative node C performs a representative node one-way hash function calculation step ST31, a representative node signature information generation step ST32, a public multiple signature information generation step ST33, and a public list information generation step ST34. To generate public multiple signature information (σ _with-root ) and public list information (L _with-root ).

In the representative node one-way hash function calculation step ST31, the representative node one-way hash function calculation unit C4 performs a one-way hash function calculation on the message (m _r ) that is the signature target of itself.

In the representative node signature information generation step ST32, the representative node signature information generation unit C5 calculates the hash value (h _r ) calculated in the representative node one-way hash function calculation step ST31 using its own unique signature key (x _r ). The representative node signature information (σ _r = x _r h _r ) composed of the operation values obtained by performing the above is generated.

In the public multiple signature information generation step ST33, the public multiple signature information generation unit C1 sums unique multiple signature information between one or a plurality of adjacent general nodes B in the mesh structure, and further adds representative node signature information. Public multiple signature information (σ _with-root ) is generated.

In the public list information generation step ST34, the public list information generation unit C2 performs a combination of one or a plurality of adjacent general nodes B in the mesh structure, a correspondence relationship between the adjacent general nodes B and the message, and a representative node C. The public list information (L _with-root ) indicating the correspondence between the message and the message is generated.

As described above, according to the aggregate signature method according to the aggregate signature system A, any one of the nodes is multiplexed between two general nodes B (between u _p -u _q ) continuous (adjacent) on the mesh structure. Signature information (σ _p−q ) is generated by calculation. Then, in the aggregate signature method according to the aggregate signature system A, the representative node C sums the multiple signature information generated for all the general nodes B. Further, in the aggregate signature method according to the aggregate signature system A, the representative node signature information (σ _r = x _r h _r ) indicating the representative node C is added to the sum of the multiple signature information, and the entire mesh structure is disclosed. It is disclosed as multiple signature information (σ _with-root = σ _r + Σσ _p−q ).

Therefore, according to the aggregate signature method according to the aggregate signature system A, the relationship between two continuous (adjacent) general nodes B on the mesh structure is represented by multiple signature information using the sum of signature keys. Can be expressed by the representative node C, and the signature information of the representative node C is added to express the mesh structure including the representative node C. Even if the number of general nodes B and the number of adjacent (adjacent) nodes increase in the mesh structure, the public multiple signature information (σ _with-root ) generated at the representative node C is disclosed. Since this is a point on the elliptic curve, the size (capacity) of the information does not increase and can be suppressed to a certain value or less, so the aggregate signature system A can efficiently generate the signature information. it can.

[Example]
Here, the operation of the aggregate signature system A will be specifically described using the mesh structure shown in FIG. 12 as an example. In this example, as in the first embodiment, seven general nodes B from node 1 to node 7 are arranged in a mesh structure, node 1 and node 2, node 2 and node 3, node 3 and node 4 Node 4 and Node 5, Node 5 and Node 6, Node 6 and Node 7, Node 7 and Node 1, Node 2 and Node 6, Node 3 and Node 5, and Node 3 and Node 7 are mutually adjacent nodes. Perform multiple signatures.

Further, the certificate authority (CA) previously assigns a unique signature key (hereinafter referred to as a signature key) and a unique verification key (hereinafter referred to as a verification key) that do not overlap each node. Specifically, a signature key and a verification key that are not duplicated with other nodes are assigned to the node 1 to the node 7 and the representative node C as follows.
Node 1: (signature key, verification key) = (x ₁ , v ₁ ) = (x ₁ , x ₁ g)
Node 2: (signature key, verification key) = (x ₂ , v ₂ ) = (x ₂ , x ₂ g)
Node 3: (signature key, verification key) = (x ₃ , v ₃ ) = (x ₃ , x ₃ g)
Node 4: (signature key, verification key) = (x ₄ , v ₄ ) = (x ₄ , x ₄ g)
Node 5: (signature key, verification key) = (x ₅ , v ₅ ) = (x ₅ , x ₅ g)
Node 6: (signature key, verification key) = (x ₆ , v ₆ ) = (x ₆ , x ₆ g)
Node 7: (signature key, verification key) = (x ₇ , v ₇ ) = (x ₇ , x ₇ g)
Node C: (signature key, verification key) = (x _r , v _r ) = (x _r , x _r g)

First, the nodes 1 to 7 obtain a hash value (h _p-q = H (m _p-q )) for a message (m _p-q ) representing a relationship with adjacent nodes and accompanying information. Also, the representative node C obtains a hash value (h _r = H (m _r )) for a message (m _r ) representing information unique to the representative node C.

Next, multiple signature information is generated between all adjacent nodes.
Specifically, for example, the node 1 (signer u ₁ ) generates signature information (x ₁ h _1-2 ) by multiplying the hash value h _1-2 by its signature key (x ₁ ), and the node 2 to send. Then, the node 2 (signer u ₂ ) adds its own signature information (x ₂ h _1-2 ) to the signature information (x ₁ h _1-2 ) received from the node 1, and (13) Multiple signature information is generated by an expression.
σ _1-2 = x ₁ h _1-2 + x ₂ h _1-2 = (x ₁ + x ₂ ) h _1-2 (13)

Note that the calculation of equation (13) may be performed by either node 1 or node 2. That is, the node 2 may generate the signature information (x ₂ h _1-2 ) and then transmit it to the node 1, and the node 1 may generate the multiple signature information (σ _1-2 ).

Further, in the node 1 or the node 2, original data {(u ₁ , u ₂ , m _1-2 )} of public list information indicating a correspondence relationship between a combination of adjacent nodes and a message to be signed is generated.

Similarly, between other adjacent nodes, multiple signature information (σ _2-3 , σ _3-4 , σ _4-5 , σ _5-6 , σ _6-7 , σ _7-1 , σ _2-6 , σ _3-5 , σ _3-7 ) and public list information original data are generated.

When the original data of the multiple signature information and the public list information is generated between all the adjacent nodes, the representative node C (representative u _r ) has the multiple signature information (σ _p-q ) and the public list information. Collect the original data. Then, the representative node C adds all the collected multiple signature information (σ _p−q ) and the signature information (σ _r ) of the representative node C, and makes public multiple signature information (14) to (15) according to the expressions (14) to (15). σ _with-root ).

In addition, the representative node C combines the original data of all the collected public list information, and generates public list information (L _with-root ) according to Expression (16).

Then, the representative node C publishes the generated public multiple signature information (σ _with-root ) and public list information (L _with-root ) as public information.

Further, the verification node D verifies the validity of the public multiple signature information (σ _with-root ) by the following verification process 1 to verification process 3.

(Verification process 1) The verification node D performs hash values (h _p−q = H (m _p− ) for all messages (m _p−q and m _r ) included in the public list information (L _with-root ). _q ) and h _r = H (m _r )).
(Verification process 2) The verification node D verifies the verification keys (v ₁ , v ₂ , v ₃ , v) of all the general nodes B and the representative nodes C that have signed the messages included in the public list information (L _with-root ). v ₄ , v ₅ , v ₆ , v ₇ , v _r ).

(Verification process 3) The verification node D verifies the validity of the public multiple signature information (σ _with-root ) disclosed by the representative node C. Specifically, the verification node D includes a hash value (h _p−q = H (m _p−q ) and h _r = H (m _r )), a verification key (v ₁ , v ₂ , v ₃ , v _4). , V ₅ , v ₆ , v ₇ , v _r ) and public list information (L _with-root ), the operations shown in the equations (17) to (19) are performed, and the equations (19) and “e (G, σ _with-root ) ”is confirmed to match, and if these values match, it is determined that the public multiple signature information (σ _with-root ) is valid.

となる。署名の過程が正しく行われていれば、（１９）式と（２１）式は、一致する。このことにより、公開されている検証鍵から、公開多重署名情報（σ_{ｗｉｔｈ−ｒｏｏｔ}）の検証が可能となる。 Here, “e (g, σ _with-root )” in (Verification process 3) is expressed by the equation (15) and the nature of pairing.

It becomes. If the signing process is performed correctly, the equations (19) and (21) match. This makes it possible to verify public multiple signature information (σ _with-root ) from a public verification key.

Further, paying attention to (20), corresponding to the normal node B _{(u p} and _{u q)} of any adjacent, signature processing from a value of _{"h p-q"} and _"x p + _{x q"} is performed Therefore, the relationship between the nodes is shown. Furthermore, the first term is composed only of the signature key (x _r ) of the representative node C. Therefore, it can be seen signer of the primary node C is u _r.

  As described above, the verification system (verification node D) can grasp what kind of relationship has been signed on the mesh structure, and as a result, on the mesh structure including the representative node C. It is possible to grasp the arrangement of signers.

In addition, it is impossible for a third party who does not know the signature key as secret information to generate σ _with-root , σ _p-q, or σ _r from the CDH problem or the discrete logarithm problem on the elliptic curve.

  That is, the present verification method employed by the verification system (verification node D) represents the relationship between two consecutive (adjacent) nodes on the mesh structure using the sum of the signature keys, and collects all of these at the representative node C Thus, the mesh structure can be expressed.

Even if the number of nodes increases, the public multiple signature information (σ _with-root ) generated by the representative node C is disclosed, and since this is a point on an elliptic curve, the size of the information (Capacity) does not increase, can be suppressed to a certain value or less, and signature information is efficiently generated.

In the aggregate signature system A in each embodiment described above, one of the adjacent general nodes B generates multiple signature information (σ _p-q ) and transmits it to the representative node C. It is not limited to. That is, both the adjacent general nodes B may generate multiple signature information and transmit it to the representative node C.
In this case, the representative node C does not need to receive the combination information of the adjacent general node B as the original data of the public list information. That is, the representative node C can determine that the combinations of the general nodes B that have received the same multiple signature information are adjacent to each other and have performed multiple signatures on each other, and can generate public list information based on this combination.

In the above-described embodiment, the two arguments that are inputs to the pairing function are expressed as a scalar multiple of the point g on the elliptic curve that can be paired. The argument and the second argument may not be common. That is, two points (g ₁ or g ₂ ) on different elliptic curves (G ₁ or G ₂ ) may be given for the first argument and the second argument of the pairing function, respectively.
In this case, g appearing in the first argument of the pairing function in the description of the foregoing embodiments the g _1, g appearing in the second argument is read as g _2. Also, whether the various public information (specific verification key, hash value, signature information) generated using the points on the elliptic curve is input to the first argument or the second argument of the pairing function. Accordingly, _one type is generated using either G ₁ or G ₂ , or two types are generated using both.
As a result, the number of public information, that is, the number of operations may increase, but since the processing can be performed in parallel in the calculation of the pairing function, the calculation time can be expected to be shortened.

  The series of processing by the aggregate signature system A 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.

A aggregate signature system B general node B1 storage unit B2 general node one-way hash function calculation unit B3 general node signature information generation unit B4 multiple signature information generation unit C representative node C1 public multiple signature information generation unit C2 public list information generation unit C3 storage unit C4 representative node one-way hash function calculation unit C5 representative node signature information generation unit D verification node and verification system D1 verification node one-way hash function calculation unit D2 collection unit D3 verification unit

Claims (7)

An aggregate signature system in which a plurality of general nodes are configured in a mesh structure, and an aggregate signature is performed between the plurality of general nodes. Each general node has a unique signature key and a unique verification key that are not duplicated in advance. Assigned,
Each general node in the mesh structure is
A general node one-way hash function operation unit that performs a one-way hash function operation on a message to be signed between adjacent general nodes;
A general node signature information generation unit that performs an operation with its own unique signature key on the hash value calculated by the general node one-way hash function calculation unit, and generates its own signature information;
A multiple signature information generation unit that generates multiple signature information unique between adjacent general nodes based on the signature information received from adjacent general nodes and its own signature information,
The representative node that supervises the plurality of general nodes is:
A public multiple signature information generating unit that generates public multiple signature information composed of a sum of multiple unique signature information between adjacent general nodes in the mesh structure;
An aggregate signature system comprising: a public list information generation unit configured to generate a public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and messages. The representative node is
A unique signature key and a unique verification key are assigned in advance,
A representative node one-way hash function operation unit that performs one-way hash function operation on a message to be signed;
A representative node signature information generation unit that performs an operation with its own unique signature key on the hash value calculated by the representative node one-way hash function calculation unit, and generates representative node signature information,
The public multiple signature information generation unit generates the public multiple signature information including the representative node signature information,
The aggregate signature system according to claim 1, wherein the public list information generation unit generates the public list information including information indicating the representative node and a correspondence relationship between the representative node and a message.   The aggregate signature system according to claim 1, wherein the multiple signature information generation unit generates unique multiple signature information between the adjacent general nodes by only one of the adjacent general nodes. The unique signature key consists of a predetermined natural number,
2. The unique verification key comprises a point on an elliptic curve generated based on a point on an elliptic curve that is an element of a GDH (GAP-Diffie-Hellman) group and the unique signature key. Item 4. The aggregate signature system according to any one of Items 3. A verification system for verifying the public multiple signature information generated by the aggregate signature system according to any one of claims 1 to 4,
A verification node one-way hash function calculation unit that performs a one-way hash function operation on a message included in the public list information;
A collection unit that collects unique verification keys of all nodes included in the public list information;
The validity of the public multiple signature information based on the hash value calculated by the verification node one-way hash function calculation unit, the unique verification keys of all the nodes collected by the collection unit, and the public list information A verification system comprising: a verification unit for verifying An aggregate signature method in which a plurality of general nodes are configured in a mesh structure, and an aggregate signature is performed between the plurality of general nodes, and each general node has a unique signature key and a unique verification key that are not duplicated in advance. Assigned,
Each general node in the mesh structure is
A general node one-way hash function calculation step for performing a one-way hash function calculation on a message to be signed between adjacent general nodes;
A general node signature information generating step of calculating the hash value calculated in the general node one-way hash function calculating step using its own unique signature key and generating its own signature information;
Performing a multiple signature information generation step of generating unique multiple signature information between adjacent general nodes based on the signature information received from adjacent general nodes and its own signature information;
The representative node that supervises the plurality of general nodes is:
A public multiple signature information generating step for generating public multiple signature information consisting of a sum of unique multiple signature information between adjacent general nodes in the mesh structure;
An aggregate signature method for executing a public list information generation step of generating public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and messages. An aggregate signature program for realizing a method of performing an aggregate signature between a plurality of general nodes by a computer, in which a plurality of general nodes are configured in a mesh structure, and a unique signature that is not duplicated in advance in each general node A key and a unique verification key,
A general node one-way hash function calculation step for performing a one-way hash function calculation on a message to be signed between adjacent general nodes;
A general node signature information generating step of calculating the hash value calculated in the general node one-way hash function calculating step using its own unique signature key and generating its own signature information;
A multiple signature information generation step of generating unique multiple signature information between adjacent general nodes based on the signature information received from adjacent general nodes and its own signature information is executed by each general node in the mesh structure. ,
A public multiple signature information generating step for generating public multiple signature information consisting of a sum of unique multiple signature information between adjacent general nodes in the mesh structure;
A public list information generating step for generating a public list information indicating a combination of adjacent general nodes and a correspondence relationship between the adjacent general nodes and messages is executed by a representative node that supervises the plurality of general nodes. Gate signature program.

Images