JP6148205B2 - Signature system, signature generation device, signature verification device, signature method, and program - Google Patents

Description

  The present invention relates to signature technology, and in particular, to a tagged disposable signature technology.

  Non-Patent Documents 1 and 2 disclose methods of disposable signatures with a group structure maintenance tag configured by a symmetric bilinear map group (for example, a symmetric pairing group).

Masayuki Abe, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Tagged One-Time Signatures: Tight Security and Optimal Tag Size,” Public Key Cryptography 2013, 312-331. Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, Miyako Ohkubo, “Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions,” ASIACRYPT 2012: 4-24.

  However, the methods disclosed in Non-Patent Documents 1 and 2 have a problem that the calculation amount of bilinear mapping necessary for signature verification is large and the calculation cost is high. For example, the signature verification formula of the scheme disclosed in Non-Patent Document 1 includes 7 + 2k bilinear maps.

  The present invention has been made in view of these points, and an object of the present invention is to provide a tag-attached disposable signature technique capable of reducing the calculation cost at the time of signature verification as compared with the prior art.

_{G 1,} G 2, G _T is the group, _{g 1} is generator of the group _{G 1, g 2} is generator of the group _{G 2,} e is bilinear mapping _{G 1 × G 2 → G T} , the secret key is at least x , Y, and the public key includes Y ₁ = g ₁ ^y , X ₂ = g ₂ ^x , and V = e (Y ₁ , X ₂ ). The signature generation time, give the tag _T 2 _{= A} ^{2 y} corresponding to any of the original _{A 2} groups _{G 2,} to give the image c of information including the message and the tag _{T 2,} based on _Z 2 = A group _{G 2} get a ₂ X ₂ ^-c. At the time of signature verification, it is determined whether or not a verification condition that satisfies the condition that e (Y ₁ , Z ₂ ) · V ^c = e (g ₁ , T ₂ ) is satisfied is satisfied.

  In the present invention, the calculation amount of bilinear mapping required for signature verification is smaller than in the prior art, and the calculation cost for signature verification can be reduced.

FIG. 1 is a block diagram for illustrating a functional configuration of the signature system according to the embodiment. FIG. 2 is a block diagram for illustrating a functional configuration of the key generation apparatus according to the embodiment. FIG. 3 is a block diagram for illustrating a functional configuration of the signature generation apparatus according to the embodiment. FIG. 4 is a block diagram for illustrating a functional configuration of the signature verification apparatus according to the embodiment. FIG. 5 is a flowchart for illustrating the key generation processing of the embodiment. FIG. 6A is a flowchart for illustrating the signature generation processing of the embodiment. FIG. 6B is a flowchart for illustrating the signature verification processing according to the embodiment.

Embodiments of the present invention will be described below.
[Definition]
Terms used in the embodiments are defined.
_{G 1,} G 2, G _T represents a group of prime order q. For example, the group _{G 1, G 2, G T} is abelian, for example cyclic groups. The group G ₁ and the group G ₂ may be the same as each other (G ₁ = G ₂ ) or may be different from each other (G ₁ ≠ G ₂ ). g ₁ is any generator of the group _{G 1, g 2} is arbitrary generator of the group _{G 2, g T} is an arbitrary generator of the group _{G T.} e means bilinear mapping _{G 1} × _{G 2} → _{G T} for outputting the group _{G T} as input and the original source and the group _{G 2} groups _{G 1.} Bilinear map e _{is, G 1 × G 2 → G} T is efficiently computable (computability), any a, b∈Z _q relative to ^{_{e (g 1 a, g 2}} b) = e (g ₁ , g ₂ ) is a mapping that satisfies ^ab (bilinearity) and satisfies e (g ₁ , g ₂ ) ≠ 1 (non-degenerate). An example of the bilinear map e is pairing. For example, e (g ₁ , g ₂ ) = g _T is satisfied. A bilinear map e with G ₁ = G ₂ is called a symmetric bilinear map (eg, symmetric pairing), and a bilinear map e with G ₁ ≠ G ₂ is called an asymmetric bilinear map (eg, asymmetric pairing). Call. Group _G 1 that symmetric bilinear map is _present, G 2, _{G T} symmetry bilinearity mapping group (e.g., symmetric pairing group) and call, the group _{G 1,} G 2 there are asymmetric bilinear mapping, _{G T} Is called an asymmetric bilinear mapping group (for example, an asymmetric pairing group). Z _p represents the residue group by the positive integer p. An example of Z _p is the set {0,..., P−1}. p is, for example, a prime number. α∈β represents that α is an element of β.

  Tagged One-Time Signature (TOS) is a signature in which a unique tag is attached to a message each time a signature is generated, and how many combinations of (message, tag, signature) were obtained. However, it means that it is difficult to forge a signature for another message that satisfies the verification expression for the tag.

[First Embodiment]
A first embodiment of the present invention will be described with reference to the drawings. In this embodiment, G ₁ = G ₂ may be satisfied, or G ₁ ≠ G ₂ may be satisfied. When G ₁ = G ₂ , g ₁ = g ₂ is set.
<Configuration>
As illustrated in FIG. 1, the signature system 1 of this embodiment includes a key generation device 11, a signature generation device 12, and a signature verification device 13, which are configured to be communicable through a network such as the Internet. Yes. As illustrated in FIG. 2, the key generation device 11 of this embodiment includes a selection unit 111, group calculation units 112 and 113, a bilinear mapping calculation unit 114, a key configuration unit 115, and an output unit 116. As illustrated in FIG. 3, the signature generation apparatus 12 according to the present exemplary embodiment includes an input unit 121, a decomposition unit 122, a storage unit 123, a selection unit 124, a tag selection unit 125, a mapping calculation unit 126, a group calculation unit 127, and an output. Part 128. As illustrated in FIG. 4, the signature verification apparatus 13 according to the present exemplary embodiment includes an input unit 131, a decomposition unit 132, a storage unit 133, a determination unit 134, and an output unit 135. Each of the key generation device 11, the signature generation device 12, and the signature verification device 13 includes, for example, a processor (hardware processor) such as a central processing unit (CPU), a random-access memory (RAM), a read-only ROM (ROM). a general-purpose or dedicated computer having a memory such as a memory) executes a predetermined program. This program may be installed in a computer, or may be recorded in a ROM or the like in advance. In addition, some or all of the processing units may be configured using an electronic circuit that realizes a processing function independently instead of an electronic circuit (circuitry) that realizes a functional configuration by reading a program like a CPU. .

<Premise>
As a premise, it is assumed that the global parameter gk is generated by the group generator Gen (1 ^λ ) (λ is a security parameter composed of an integer of 1 or more). The global parameter gk includes a parameter Λ = (p, G ₁ , G ₂ , G _T , g ₁ , g ₂ , g _T , e). However, when G ₁ = G ₂ , the parameter Λ = (p, G ₁ , G _T , g ₁ , g _T , e) may be set as g ₁ = g ₂ . It is assumed that the global parameter gk is set in the key generation device 11, the signature generation device 12, and the signature verification device 13 and can be used.

<Key generation processing: FIG. 5>
The key generation device 11 (FIG. 2) uses the algorithm TOS. Key (gk) is executed, and a key pair of the public key pk and the secret key sk is generated and output. This process will be described in detail.

First, the selection unit 111 selects and outputs an arbitrary element x, yεZ _p of Z _p . The elements x and y are selected uniformly at random, for example. Elements x and y may be generated each time a key is generated, or may be selected from a plurality of elements that have been generated in advance (step S111).

Group operation unit 112 inputs the original y output from the selector 111, and outputs the obtained original _{Y ¹ = g} 1 ^y ∈G 1 group _{G 1} (step S112). Note that “obtaining α” may mean “calculating α and obtaining the result” or “selecting α from a pre-calculated value and obtaining the value”. There may be. The group calculation unit 113 receives the element x output from the selection unit 111, obtains and outputs the element X ₂ = g ₂ ^x εG ₂ of the group G ₂ (step S113).

Bilinear mapping operation unit 114 inputs the _Y 1, _{X 2} output from the group calculation unit 112 and 113, their bilinear mapping _{V = e (Y 1, X} 2) ∈G T the obtained outputs (Step S114).

The key construction unit 115 receives x and y output from the selection unit 111, Y ₁ and X ₂ output from the group calculation units 112 and 113, and V output from the bilinear map calculation unit 114 as inputs, and is disclosed. A key pk = (Y ₁ , X ₂ , V) and a secret key sk = (x, y) are obtained and output. The public key pk and the secret key sk are sent to the output unit 117 (step S115).

  The output unit 116 outputs the public key pk and the secret key sk. The public key pk is sent to the signature generation device 12 and the signature verification device 13, input to the input units 121 and 131, and stored in the storage units 123 and 133, respectively. The private key sk is securely sent to the signature generation device 12, is input to the input unit 121, and is securely stored in the storage unit 123 (step S116).

<Signature generation processing (6A)>
The signature generation device 12 (FIG. 3) uses the algorithm TOS.1 for the global parameter gk and the secret key sk. Tag (gk, sk) is executed to obtain a tag tag, and an algorithm TOS. Is applied to the secret key sk, message msg, and tag tag. Sign (sk, msg, tag) is executed to obtain and output a signature σ. This process will be described in detail.

First, the message msg is input to the input unit 121 and stored in the storage unit 123. The message msg is further sent to the disassembling unit 122 (step S121). The parsing unit 122 parses the message msg, and obtains _k parsed messages m ₁ ,..., M _k ∈Z _p ^k corresponding to the message msg (where k is an integer equal to or greater than 1). Output. The parsed messages m ₁ ,..., M _k are stored in the storage unit 123 (step S122).

The selection unit 124 selects and outputs an arbitrary element A ₂ εG ₂ of the group G ₂ . Original A ₂ is selected at random for example. It original A ₂ may be generated each time the signature generation, may be selected from a plurality of source generated in advance (step S124).

The tag selection unit 125 extracts (parses) y from the public key pk read from the storage unit 123. Furthermore tag selection unit 125 inputs the _{A 2} that the selection unit 124 outputs, outputs the obtained tag ^{_{tag = T 2 = A 2 y}} ∈G 2 corresponding to the original _{A 2} (step S125).

Mapping operation unit 126 reads messages m ₁ ,..., M _k parsed from storage unit 123. Further, the mapping calculation unit 126 receives the tag tag = T ₂ output from the tag selection unit 125 and receives the image m of the information M including the parsed messages m ₁ ,..., M _k and the tag tag = T _2. to obtain a Z _p to output. The information M may include only the messages m ₁ ,..., M _k and the tag tag = T ₂ , or may include public information (for example, the global parameter gk and the public key pk). . An example of the image c is an image obtained by applying a map having collision resistance to the information M. An example of a map having collision difficulty is a collision collision hash function (for example, SHA-2) or a common key encryption function (for example, AES or Camellia (registered trademark)). An image c may be obtained by applying a mapping having collision difficulty to the result obtained by applying a predetermined conversion function to the information M (step S126).

The group calculation unit 127 extracts (parses) X ₂ from the public key pk read from the storage unit 123. Further, A ₂ output from the selection unit 124 and the image c output from the mapping calculation unit 126 are input to the group calculation unit 127. Group operation unit 127, to obtain the original ^{_{Z 2 = A 2 X 2 -c}} ∈G 2 groups _{G 2} using these signature σ = (c, _{Z 2)} for outputting a (step S127).

  The output unit 128 receives the message msg read from the storage unit 123, the tag tag output from the tag selection unit 125, and the signature σ output from the group calculation unit 127. The output unit 128 outputs the message msg, the tag tag, and the signature σ (step S128).

<Signature verification processing (6B)>
The signature verification apparatus 13 (FIG. 4) uses the algorithm TOS.1 for the public key pk, the message msg, the tag tag, and the signature σ. Vrf (pk, msg, tag, σ) is executed and the verification result is output. This process will be described in detail.

First, the message msg, tag tag, and signature σ are input to the input unit 131 and stored in the storage unit 133. These are not necessarily obtained correctly as described above. The message msg is further sent to the disassembly unit 132 (step S131). The disassembling unit 132 parses the message msg, and obtains and outputs _k parsed messages m ₁ ,..., M _k εZ _p ^k corresponding to the message msg. The parsed messages m ₁ ,..., M _k are stored in the storage unit 133 (step S132).

The determining unit 134 reads the public key pk = (Y ₁ , X ₂ , V), the signature σ = (c, Z ₂ ), the tag tag = T ₂ , and the messages m ₁ ,..., M _k from the storage unit 133. , Message m ₁ ,..., M _k and tag tag = T ₂ , e (Y ₁ , Z ₂ ) · V ^c = e (g ₁ , T ₂ ) for image c = H (M) of information M (1)
It is determined whether or not a verification condition that satisfies the above relationship is a necessary condition. However, the generation method of the information M and the image c is the same as that in step S126. For example, the determination unit 134 obtains an image H (M) of the information M including the messages m ₁ ,..., M _k and the tag tag = T _2, and whether this matches the c included in the signature σ (c = H (M)), and if c = H (M), it is determined whether the relationship of Expression (1) is satisfied. There is no limitation on the method for determining whether or not the relationship of Expression (1) is satisfied, and any method may be used. For example, the left side and the right side of Expression (1) may be calculated to determine whether or not they are equal, or the function value on the left side of Expression (1) is compared with the function value on the right side to make this determination. May be performed. Alternatively, whether or not the relationship of the formula (1) is satisfied depending on whether or not the relationship of e (Y ₁ , Z ₂ ) · V ^c · e (g ₁ , T ₂ ) ⁻¹ = 1 is satisfied instead of the formula (1). It may be determined. Alternatively, satisfying another condition (for example, another verification expression) may be added to the verification condition (step S134).

  When it is determined that the verification condition is not satisfied (for example, c ≠ H (M) or the relationship of Expression (1) is not satisfied), the determination unit 134 outputs 0 indicating the verification failure, and the output unit 135 Outputs 0 (step S1350). On the other hand, when it is determined that the verification condition is satisfied (for example, c = H (M) and the relationship of Expression (1) is satisfied), the determination unit 134 outputs 1 indicating the verification success, and the output unit 135 outputs this 1 (step S1351).

<Reason why a correctly generated signature passes verification>
Original _{A 2} groups _{G 2} is, by using the generated original _{g 2} groups _{G 2 A} 2 _{= g} ^{2 a} (However, a∈Z _p) can be a representation. When the signature σ is correctly generated, the left side of the equation (1) can be transformed as follows.
e (Y ₁ , Z ₂ ) · V ^{c
_{= E (g 1 y, g}} 2 a g 2 -cx) · e (g 1 y, g 2 x) c
^{_{= E (g 1, g 2}} ) -cxy + ay · e (g 1, g 2) cxy
= E (g ₁ , g ₂ ) ^ay (2)
The right side of equation (1) can be modified as follows.
e (g ₁ , T ₂ )
= E (g ₁ , A ₂ ^y )
^{_{= E (g 1, g 2}} ay)
= E (g ₁ , g ₂ ) ^ay (3)
From equations (2) and (3), it can be seen that the relationship of equation (1) is satisfied when the signature σ is correctly generated. This is true whether G ₁ = G ₂ or G ₁ ≠ G ₂ .

<Features of this embodiment>
In the disposable signature with a tag according to this embodiment, the signature verification can be performed only by calculating two bilinear maps (Equation (1)), so that the calculation cost can be reduced as compared with the conventional case. This can reduce the burden on the computer and improve the processing speed of the application.

[Second Embodiment]
This embodiment improves safety in the implementation with the asymmetric bilinear map group (G ₁ ≠ G ₂ ). Below, it demonstrates centering around difference with 1st Embodiment, and the same reference number is quoted about the matter which is common to this, and description is simplified.

<Configuration>
As illustrated in FIG. 1, the signature system 2 of the present embodiment includes a key generation device 21, a signature generation device 12, and a signature verification device 13, which are configured to be communicable through a network such as the Internet. Yes. As illustrated in FIG. 2, the key generation device 21 according to the present embodiment includes a selection unit 111, group calculation units 112, 113, and 212, a bilinear mapping calculation unit 114, a key configuration unit 215, and an output unit 116. The rest is the same as in the first embodiment except that G ₁ ≠ G ₂ .

<Premise>
Except that the key generation device 11 is replaced with the key generation device 21 and G ₁ ≠ G ₂ , this is the same as <Prerequisite> in the first embodiment.

<Key generation processing: FIG. 5>
The key generation device 11 (FIG. 2) uses the algorithm TOS. Key (gk) is executed, and a key pair of the public key pk and the secret key sk is generated and output. This process will be described in detail.

First, the processes of steps S111 to S113 described above are executed. Next, the group calculation unit 212 receives the element y output from the selection unit 111 as an input, obtains and outputs the ^element Y ₂ = g ₂ ^y εG ₂ of the group G ₂ (step S212). Thereafter, after the process of step S114 described above is executed, the key configuration unit 215 outputs x, y output from the selection unit 111, Y ₁ , X ₂ , Y output from the group calculation units 112, 113, 212. ₂ and V output from the bilinear mapping operation unit 114 are input, and a public key pk = (Y ₁ , X ₂ , Y ₂ , V) and a secret key sk = (x, y) are obtained and output. The public key pk and the secret key sk are sent to the output unit 117 (step S215). The subsequent processing is the same as in the first embodiment.

<Signature Generation Processing (6A) / Signature Verification Processing (6B)>
Except for G ₁ ≠ G ₂ , it is the same as the signature generation processing and signature verification processing of the first embodiment.

<Features of this embodiment>
Even with a single-use signature with a tag according to the present embodiment, it is possible to perform signature verification only by calculating two bilinear maps, so that the calculation cost can be reduced as compared with the conventional one. Further, when a simulation for security proof is performed, not only the public key Y ₁ = g ₁ ^y ∈G _{1 of} the group G ₁ corresponding to the secret key y but also the public key Y ₂ = g ₂ ^{y of the} group G ₂ ΕG _{2 is} also required. In this embodiment, G ₁ ≠ G ₂ , but the public key Y ₂ is also generated as a public key in addition to the public key Y ₁ used for signature verification. As a result, it is possible to prove the safety even for the implementation in the asymmetric bilinearity map group (G ₁ ≠ G ₂ ), thereby ensuring the safety.

[Other variations]
The present invention is not limited to the above-described embodiment. For example, in the above method, instead of the parsed messages m ₁ ,..., M _k , the message msg or other information corresponding to the message msg may be used. In the above embodiment, the signature σ = (c, Z ₂ ), but the signature σ may not include c. In this case, the signature verification apparatus obtains an image c = H (M) of the information M including the messages m ₁ ,..., M _k and the tag tag = T _2, and whether or not the relationship of the expression (1) is satisfied. Determine. Further, either x or y may be a constant (for example, 1εZ _p ), and the secret key may be either x or y that is not a constant. The public key may include other public parameters. Further, instead of each device exchanging information via a network, at least a part of the devices may exchange information via a portable recording medium. Alternatively, at least some of the devices may exchange information via a non-portable recording medium. That is, the combination which consists of a part of these apparatuses may be the same apparatus. For example, the signature generation device may further function as a key generation device.

  The various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. Needless to say, other modifications are possible without departing from the spirit of the present invention.

  When the above configuration is realized by a computer, the processing contents of the functions that each device should have are described by a program. By executing this program on a computer, the above processing functions are realized on the computer. The program describing the processing contents can be recorded on a computer-readable recording medium. An example of a computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  This program is distributed, for example, by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads a program stored in its own recording device and executes a process according to the read program. As another execution form of the program, the computer may read the program directly from the portable recording medium and execute processing according to the program, and each time the program is transferred from the server computer to the computer. The processing according to the received program may be executed sequentially. The above-described processing may be executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition without transferring a program from the server computer to the computer. Good.

  In the above embodiment, the processing functions of the apparatus are realized by executing a predetermined program on a computer. However, at least a part of these processing functions may be realized by hardware.

DESCRIPTION OF SYMBOLS 1, 2 Signature system 11, 21 Key generation apparatus 12 Signature generation apparatus 13 Signature verification apparatus

Claims (8)

_{G 1,} G 2, G _T is the group, _{g 1} is the group _{G 1} of origin, _{g 2} is generator of the group _{G 2,} e is bilinear mapping _{G 1 × G 2 → G T} , the secret key Including at least one of x and y, and the public key includes Y ₁ = g ₁ ^y , X ₂ = g ₂ ^x , V = e (Y ₁ , X ₂ ),
The tag T _{2 =} give A ₂ ^y Rutagu selection unit corresponding to the arbitrary element A ₂ of the group G _2, and obtained Ru mapping unit image c of information including a message and said tag T _2, said group A signature generation device including a group operation unit for obtaining an element Z ₂ = A ₂ X ₂ ^-c of G ₂ ;
The tag _{T 2,} information corresponding to the information including the message and said tag _{T 2,} and the input unit for accepting the original _{Z 2,} e to the image _{c (Y 1, Z 2)} · V c = a signature verification apparatus including: a determination unit that determines whether a verification condition that satisfies a condition of e (g ₁ , T ₂ ) as a necessary condition is satisfied;
Having a signature system. The signature system according to claim 1, wherein x and y are arbitrary values.
A first group arithmetic unit to obtain the original _Y 1 _{= g} ^{1 y} of the group _{G 1,} a second group arithmetic unit to obtain the original _X 2 _{= g} ^{2 x} of the group _{G 2,} the original V of the group _{G T} = A signature system having a key generation device including a bilinear mapping operation unit that obtains e (Y ₁ , X ₂ ). The signature system of claim 2, comprising:
The key generation device includes a third group calculation unit that obtains Y ₂ = g ₂ ^y of the group G ₂ ,
The secret key comprises the x, y, it said public key further comprises Y _2, signature system. _{G 1,} G 2, G _T is the group, _{g 1} is the group _{G 1} of origin, _{g 2} is generator of the group _{G 2,} e is bilinear mapping _{G 1 × G 2 → G T} , the secret key Including at least one of x and y, and the public key includes Y ₁ = g ₁ ^y , X ₂ = g ₂ ^x , V = e (Y ₁ , X ₂ ),
A tag selection unit for obtaining a tag T ₂ = A ₂ ^y corresponding to an arbitrary element A ₂ of the group G ₂ ;
A mapping unit for obtaining an image c of information including a message and the tag T ₂ ;
A group operation unit for obtaining an element Z ₂ = A ₂ X ₂ ^-c of the group G ₂ ;
A signature generation device. The signature generation device according to claim 4,
The image c is an image obtained by the action of mapping with collision resistance to information including a message and said tag T _2, the signature generating apparatus. _{G 1,} G 2, G _T is the group, _{g 1} is the group _{G 1} of origin, _{g 2} is generator of the group _{G 2,} e is bilinear mapping _{G 1 × G 2 → G T} , the secret key Including at least one of x and y, and the public key includes Y ₁ = g ₁ ^y , X ₂ = g ₂ ^x , V = e (Y ₁ , X ₂ ),
A tag T ₂ that is an element of the group G ₂ , information corresponding to information including the message and the tag T ₂ , an input unit that receives the element Z ₂ of the group G ₂ ;
A verification condition that requires that the relationship of e (Y ₁ , Z ₂ ) · V ^c = e (g ₁ , T ₂ ) is satisfied for the image c of the information including the message and the tag T _2. A determination unit for determining whether to satisfy,
A signature verification apparatus. _{G 1,} G 2, G _T is the group, _{g 1} is the group _{G 1} of origin, _{g 2} is generator of the group _{G 2,} e is bilinear mapping _{G 1 × G 2 → G T} , the secret key Including at least one of x and y, and the public key includes Y ₁ = g ₁ ^y , X ₂ = g ₂ ^x , V = e (Y ₁ , X ₂ ),
A tag selection unit of the signature generation device obtains a tag T ₂ = A ₂ ^y corresponding to an arbitrary element A ₂ of the group G ₂ , and a mapping unit of the signature generation device includes a message and the tag T ₂ An image c of information is obtained, and the group calculation unit of the signature generation apparatus obtains the element Z ₂ = A ₂ X ₂ ^-c of the group G ₂ ,
An input unit of the signature verification apparatus receives the tag T ₂ , information corresponding to the information including the message and the tag T ₂ , and the element Z ₂ , and the determination unit of the signature verification apparatus receives the image c On the other hand , a signature method for determining whether or not a verification condition that satisfies a relation of e (Y ₁ , Z ₂ ) · V ^c = e (g ₁ , T ₂ ) is satisfied. Signature generating apparatus 請 Motomeko 4 or 5, or a program for causing a computer to function as the signature verifying apparatus according to claim 6.

Images