JP5331027B2 - Signature / verification system, signature / verification method, signature device, verification device, program, recording medium - Google Patents

Description

  The present invention relates to a signature / verification system, a signature / verification method, a signature device, a verification device, a program, and a recording medium, which are mainly used when sending and receiving messages via telecommunications.

  The digital signature calculates a value s that can be calculated only when the signer who knows the secret key sk corresponding to the public key pk correctly uses the secret key sk for the message m. It is used as a typical signature. A correct signature can be verified by anyone using the public key pk, and any third party who does not know the secret key sk cannot calculate the valid signature s.

  Digital signatures are used as basic components in various cryptographic protocols such as electronic cash and credential systems. In particular, in applications that require user privacy, it is possible to convince an arbitrary third party that the correct signature s for a message m is retained without revealing the signature s by combining with zero knowledge proof. Advanced usage forms are often seen.

Recent progress in pairing technology has made it possible to construct zero-knowledge proof that efficiently proves the fact that groups of elements satisfy a certain relationship (Non-Patent Document 1). Thus, if the signature s is an element of the group G with efficient pairing, that is, if sεG, the fact that the correct signature s is retained without revealing the signature s as described above It is possible to prove For example, disclosed in Non-Patent Document 2, in the method of so-called CL-Signature, the signature s to the message M∈Z _q is composed of three groups elements (a, b, c) ∈G 3.

  However, with CL-signature, an existing signature method that can prove its security only by number-theoretic assumptions without using idealized components (known as impossible) such as random oracles. , Message m is not an element of group G. Therefore, it is not used for the application of proving that the correct signature is retained for the concealed message in a state where the message is concealed. As a secure signature method even when a message is a group G element, Non-Patent Document 3 shows a method improved from the above-mentioned CL-Signature, which shows that it is safe against random message attacks. However, the security against stronger selective message attacks is unclear.

  As a method in which the message is a group element and proved to be strong against the selective message attack, there is a method shown in Non-Patent Document 4. This method will be described below. FIG. 1 is a diagram showing a configuration example of a signature / verification system, FIG. 2 is a diagram showing a processing flow of the signature device, and FIG. 3 is a diagram showing a processing flow of the verification device. The signature / verification system includes a signature device 700 and a verification device 900 connected to a network 800.

Let v = (q, G, G _T , e, g) be a public parameter. q is large prime numbers, G, G _T is a group of order q, e is G × G → G _T efficient calculations can pairing, g any generator of the group G, F, H, K , T is a generator of group G. Further, it is assumed that the message is limited to a group element pair (M, N) εG ² and satisfying e (M, H) = e (g, N).

  The signature device 700 generates a random integer x not less than 1 and not more than q−1 (S710). Then, X = xg and Y = xH are calculated (S720), (v, xg, xH) is set as the public key pk, and x is set as the secret key sk (S730).

  The signature device 700 generates random numbers c and r of 1 to q−1 (S750),

a ₂ = cg
a ₃ = cF
a ₄ = rg
a ₅ = rH
Is calculated (S760). Then, the five sets (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) εG ⁵ are set as a signature σ (S770).

The verification apparatus 900 receives the signature σ via the network 800 (S910). And for message pair (M, N) and signature σ,
e (a ₁ , X + a ₂ ) = e (K + M, g) e (T, a ₄ )
e (a ₂ , F) = e (g, a ₃ )
e (a ₄ , H) = e (g, a ₅ )
e (M, H) = e (g, N)
It is confirmed that e (X, H) = e (g, Y) (S920). If it is confirmed that all the conditions are satisfied, information indicating that the signature is correct is output, and if it is determined that any of the conditions is not satisfied, information indicating that the signature is incorrect is output (S930). .

Jens Groth and Amit Sahai, “Efficient Non-interactive Proof Systems for Bilinear Groups”, Eurocrypt 2008, LNCS 2965, pp.415-432. Jan Camenisch and Anna Lysyanskaya, “Signature Schemes and Anonymous Credentials from Bilinear Maps”, Crypto 2004, LNCS 3152, pp.56-72. Matthew Green and Susan Hohenberger, “Universally Composable Adaptive Oblivious Transfer”, IACR e-Print archive, 2008/163 [Search February 5, 2010], Internet <URL: http://eprint.iacr.org/cgi- bin / getfile.pl? entry = 2008/163 & version = 20080806: 150034 & file = 163.pdf>. Georg Fuchsbauer, “Automorphic Signatures in Bilinear Groups”, IACR e-print 200/320 [searched February 5, 2010], Internet <URL: http://eprint.iacr.org/2009/320.pdf>.

However, in the conventional technique, the signature / verification system has a problem that the signature is composed of five elements of the group G, and the verification is performed because five pairing equations are confirmed. In addition, the message is a group element pair (M, N) ∈ G ² , and there is a restriction that e (M, H) = e (g, N) must be satisfied.

  Therefore, the present invention is a digital signature method for a group element message that has a short signature length, a smaller amount of calculation of a verification formula, and can prove high security, and further has no conventional message restrictions, An object is to provide a signature method capable of generating a signature for an arbitrary message.

_{First, G 1,} G ₂ a mapping is difficult order q group of from _{G 1} to _{G 2,} bilinear mapping group of order q of _{G T,} the _{e G 1 × G 2 → G} T, g ₁ any generator of the group _{G 1,} the _{g 2} and any generator of the group _{G 2.} The first signature / verification system of the present invention comprises a signature device and a verification device. The signature device includes a signature recording unit, a key random number generation unit, a key calculation unit, a key generation unit, a message acquisition unit, a signature random number generation unit, a signature calculation unit, and a signature output unit. The verification apparatus includes a verification input unit, a verification confirmation unit, and a verification output unit. The signature recording unit records q, G ₁ , G ₂ , G _T , e, g ₁ , and g ₂ . The key random number generation unit generates random integers α, β, x, y of 1 or more and q−1 or less. The key calculator is
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^β ,
Calculate The key generation unit uses (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , A, B, h, g ₁ ′, h ′) as the public key pk, and (pk, α, β , X, y) is a secret key sk. Message acquisition unit receives a message M is one other than the original on the group G _2. The signature random number generation unit generates random integers ζ, ρ, ν of 1 or more and q−1 or less. The signature calculator is
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^β M ^−x z ⁻¹ ) ^{1 / ν} ,
Calculate The signature output unit outputs (r, s, u, v, z) as a signature σ. The verification input unit receives the message M and the signature σ. The verification confirmation part
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
Confirm. The verification output unit outputs information indicating that the signature is correct when the verification confirmation unit confirms that all conditions are satisfied, and indicates that the signature is incorrect when it is confirmed that any of the conditions is not satisfied. Output information.

Instead of using random integers α and β, only α may be used .

According to the signature / verification system of the present invention, it is assumed that the mapping from the group G ₁ to the group G ₂ is difficult by using a bilinear map composed of different groups. Then, using the property that it is difficult to find the exponents of different generators, messages on two different groups are used as signature output. Since the signature / verification system of the present invention has such characteristics, the number of expressions to be confirmed at the time of verification can be reduced. In addition, there are no restrictions on the message, and a signature can be generated for any message.

The figure which shows the structural example of the conventional signature and verification system. The figure which shows the processing flow of the conventional signature apparatus. The figure which shows the processing flow of the conventional verification apparatus. The figure which shows the structural example of the signature and verification system of Example 1 and Example 1 modification. The figure which shows the processing flow of the signature apparatus of Example 1 and Example 1 modification. The figure which shows the processing flow of the verification apparatus of this invention .

  Hereinafter, embodiments of the present invention will be described in detail. In addition, the same number is attached | subjected to the structure part which has the same function, and duplication description is abbreviate | omitted.

  4 is a diagram illustrating a configuration example of the signature / verification system according to the first embodiment, FIG. 5 is a diagram illustrating a processing flow of the signature device, and FIG. 6 is a diagram illustrating a processing flow of the verification device. The signature / verification system according to the first embodiment includes a signature device 100 and a verification device 200. In this figure, the signature device 100 and the verification device 200 are connected by a network 800. Note that the method of passing the signature σ output from the signature device 100 to the verification device 200 is not necessarily limited to a method using a network. For example, it may be transferred from the signature device 100 to the verification device 200 by a recording medium.

_{First, G 1,} G ₂ a mapping is difficult order q group of from _{G 1} to _{G 2,} bilinear mapping group of order q of _{G T,} the _{e G 1 × G 2 → G} T, g ₁ any generator of the group _{G 1,} the _{g 2} and any generator of the group _{G 2.} Specific examples of bilinear mapping include Weil pairing, Bilinear pairing, and Tate pairing. The signature device 100 includes a signature recording unit 190, a key random number generation unit 110, a key calculation unit 120, a key generation unit 130, a message acquisition unit 140, a signature random number generation unit 150, a signature calculation unit 160, and a signature output unit 170. The verification apparatus 200 includes a verification input unit 210, a verification confirmation unit 220, a verification output unit 230, and a verification recording unit 290.

The signature recording unit 190 records q, G ₁ , G ₂ , G _T , e, g ₁ , and g ₂ in advance. Then, the key random number generation unit 110 generates a random integer α, x, y of 1 or more and q−1 or less (S110). The key calculation unit 120
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^α ,
Is calculated (S120). The key generation unit 130 uses (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , A, B, h, g ₁ ′, h ′) as the public key pk, and (pk, α, x, y) is set as a secret key sk (S130).

Message acquisition unit 140 receives the message M is one other than the original on the group _{G 2} (S140). Note that receiving the message M includes not only inputting the message M from the outside of the signature apparatus 100 but also reading out the message M recorded in the signature recording unit 190 in advance. The signature random number generation unit 150 generates random integers ζ, ρ, and ν of 1 to q−1 (S150). The signature calculation unit 160
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ν} ,
Is calculated (S160). The signature output unit 170 outputs (r, s, u, v, z) as the signature σ (S170).

The verification input unit 210 receives the message M and the signature σ and stores them in the verification recording unit 290 (S210). The verification confirmation unit 220
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
Is confirmed (S220). The verification output unit 230 outputs information indicating that the signature is correct when the verification confirmation unit 220 confirms that all the conditions are satisfied, and the signature is incorrect when it is confirmed that any of the conditions is not satisfied. Is output (S230). For example, “1” may be output as information indicating that the signature is correct, and “0” may be output as information indicating that the signature is not correct.

According to the signature / verification system of the present embodiment, it is assumed that the mapping from the group G ₁ to the group G ₂ is difficult by using a bilinear map composed of different groups. Then, using the property that it is difficult to find the exponents of different generators, messages on two different groups are used as signature output. Since the signature / verification system of the present invention has such characteristics, the number of expressions to be confirmed at the time of verification can be reduced. In addition, there are no restrictions on the message, and a signature can be generated for any message.

[Modification]
In the first embodiment, a random integer α is used for calculating A and B of the key calculation unit. In this embodiment, α is used for the calculation of A by the key calculation unit, and β (a random integer different from alpha) is used for the calculation of B.

  4 is a diagram illustrating a configuration example of a signature / verification system according to a modification of the first embodiment, FIG. 5 is a diagram illustrating a processing flow of the signature device, and FIG. 6 is a diagram illustrating a processing flow of the verification device. The signature / verification system according to the first embodiment includes a signature device 300 and a verification device 200. In this figure, the signature device 300 and the verification device 200 are connected by a network 800. Note that the method of passing the signature σ output from the signature device 300 to the verification device 200 is not necessarily limited to a method using a network. For example, it may be transferred from the signature device 300 to the verification device 200 by a recording medium.

_{First, G 1,} G ₂ a mapping is difficult order q group of from _{G 1} to _{G 2,} bilinear mapping group of order q of _{G T,} the _{e G 1 × G 2 → G} T, g ₁ any generator of the group _{G 1,} the _{g 2} and any generator of the group _{G 2.} Signature device 300 includes a signature recording unit 390, a key the random number generation unit 310, a key calculation unit 320, the key generation unit 330, a message acquisition unit 140, a signature random number generation unit 150, signature calculation unit 3 60, the signature output unit 170. The verification apparatus 200 includes a verification input unit 210, a verification confirmation unit 220, a verification output unit 230, and a verification recording unit 290.

First, the signature recording unit 390 records q, G ₁ , G ₂ , G _T , e, g ₁ , and g ₂ in advance. Then, the key random number generation unit 310 generates random integers α, β, x, y of 1 or more and q−1 or less (S310). The key calculation unit 320
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^β ,
Is calculated (S320). The key generation unit 330 uses (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , A, B, h, g ₁ ′, h ′) as the public key pk, and (pk, α, Let β, x, y) be the secret key sk (S330). The signature calculation unit 360
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^β M ^−x z ⁻¹ ) ^{1 / ν} ,
Is calculated (S360). Message acquisition unit 140, a signature random number generation unit 150, the processing of the signature output unit 170 is the same as the signature device 100 of the first embodiment.

The verification device 200 is the same as that in the first embodiment. That is, the verification input unit 210 receives the message M and the signature σ and stores them in the verification recording unit 290 (S210). The verification confirmation unit 220
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
Is confirmed (S220). The verification output unit 230 outputs information indicating that the signature is correct when the verification confirmation unit 220 confirms that all the conditions are satisfied, and the signature is incorrect when it is confirmed that any of the conditions is not satisfied. Is output (S230).

Also in this modification, it is assumed that it is difficult to map from the group G ₁ to the group G ₂ using a bilinear map composed of different groups. Then, using the property that it is difficult to find the exponents of different generators, messages on two different groups are used as signature output. Since the signature / verification system of the present invention has such characteristics, the number of expressions to be confirmed at the time of verification can be reduced. In addition, there are no restrictions on the message, and a signature can be generated for any message .

Program, Recording Medium When the above-described configuration is realized by a computer, the processing contents of functions that each device should have are described by the program. The processing functions are realized on the computer by executing the program on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

  The program is distributed 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, the computer reads a program stored in its own recording medium and executes a process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

  The present invention can be used to prove the validity of electronic data.

100,300, 7 00 signing device 110,31 0 key the random number generation unit 120,32 0 key calculating unit 130,33 0 key generation unit 14 0 message acquiring unit 150 signature random number generation unit 160, 3 60 signature calculation unit 17 0 signature output unit 190,39 0 signature recording part 20 0 verification device 21 0 validation input unit 22 0 validation check unit 230 verifying the output unit 29 0 validation recording unit 8 00 network

Claims (10)

G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of group G ₁ and g ₂ as an arbitrary generator of group G ₂ ,
a signature recording unit for recording q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ ;
A key random number generator for generating random integers α, x, y of 1 to q−1;
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^α ,
A key calculation unit for calculating
And _{(q, G 1, G 2} , G T, e, g 1, g 2, A, B, h, g 1 ', h') and the public key pk and secret (pk, alpha, x, y) A key generation unit for key sk;
A message acquisition unit that receives a message M that is an element other than 1 on the group G ₂ ;
A signature random number generator for generating random integers ζ, ρ, ν of 1 to q−1;
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ν} ,
A signature calculation unit for calculating
A signature device comprising: a signature output unit that outputs (r, s, u, v, z) as a signature σ;
A verification input unit for receiving the message M and the signature σ;
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
A verification check unit for checking
When the verification confirmation unit confirms that all conditions are satisfied, information indicating that the signature is correct is output, and when it is determined that any condition is not satisfied, information indicating that the signature is incorrect is output. A signature / verification system comprising: a verification device comprising: a verification output unit. G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of group G ₁ and g ₂ as an arbitrary generator of group G ₂ ,
a signature recording unit for recording q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ ;
A key random number generator for generating random integers α, β, x, y of 1 to q−1;
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^β ,
A key calculation unit for calculating
And _{(q, G 1, G 2} , G T, e, g 1, g 2, A, B, h, g 1 ', h') and the public key pk and, (pk, α, β, x, y) A key generation unit with a secret key sk,
A message acquisition unit that receives a message M that is an element other than 1 on the group G ₂ ;
A signature random number generator for generating random integers ζ, ρ, ν of 1 to q−1;
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^β M ^−x z ⁻¹ ) ^{1 / ν} ,
A signature calculation unit for calculating
A signature device comprising: a signature output unit that outputs (r, s, u, v, z) as a signature σ;
A verification input unit for receiving the message M and the signature σ;
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
A verification check unit for checking
When the verification confirmation unit confirms that all conditions are satisfied, information indicating that the signature is correct is output, and when it is determined that any condition is not satisfied, information indicating that the signature is incorrect is output. A signature / verification system comprising: a verification device comprising: a verification output unit. A signature / verification method in a signature / verification system including a signature device and a verification device,
G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of group G ₁ and g ₂ as an arbitrary generator of group G ₂ ,
In the signature device,
The signature recording unit records q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ in advance,
A key random number generation unit for generating a random integer α, x, y between 1 and q−1;
The key calculator is
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^α ,
A key calculation step for calculating
The key generation unit uses (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , A, B, h, g ₁ ′, h ′) as the public key pk, and (pk, α, x , Y) as a secret key sk, and a key generation step,
A message acquisition step in which the message acquisition unit receives a message M that is an element other than 1 on the group G ₂ ;
A signature random number generation unit for generating a random integer ζ, ρ, ν of 1 or more and q−1 or less;
The signature calculation department
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ν} ,
A signature calculation step for calculating
A signature output unit including a signature output step of outputting (r, s, u, v, z) as a signature σ;
In the verification device,
A verification input step in which the verification input unit receives the message M and the signature σ;
Verification verification part
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
A verification confirmation step to confirm,
When the verification output unit confirms that the verification confirmation unit satisfies all the conditions, it outputs information indicating that the signature is correct, and when the verification output unit confirms that any of the conditions is not satisfied, the signature is not correct. And a verification output step for outputting information indicating the signature / verification method. A signature / verification method in a signature / verification system including a signature device and a verification device,
G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of group G ₁ and g ₂ as an arbitrary generator of group G ₂ ,
In the signature device,
The signature recording unit records q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ in advance,
A key random number generation unit for generating a random integer α, β, x, y between 1 and q−1;
The key calculator is
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^β ,
A key calculation step for calculating
The key generation unit uses (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , A, B, h, g ₁ ′, h ′) as the public key pk, and (pk, α, β , X, y) as a secret key sk, and a key generation step,
A message acquisition step in which the message acquisition unit receives a message M that is an element other than 1 on the group G ₂ ;
A signature random number generation unit for generating a random integer ζ, ρ, ν of 1 or more and q−1 or less;
The signature calculation department
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^β M ^−x z ⁻¹ ) ^{1 / ν} ,
A signature calculation step for calculating
A signature output unit including a signature output step of outputting (r, s, u, v, z) as a signature σ;
In the verification device,
A verification input step in which the verification input unit receives the message M and the signature σ;
Verification verification part
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
A verification confirmation step to confirm,
When the verification output unit confirms that the verification confirmation unit satisfies all the conditions, it outputs information indicating that the signature is correct, and when the verification output unit confirms that any of the conditions is not satisfied, the signature is not correct. A signature / verification method comprising: a verification output step for outputting the indicated information. G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of group G ₁ and g ₂ as an arbitrary generator of group G ₂ ,
a signature recording unit for recording q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ ;
A key random number generator for generating random integers α, x, y of 1 to q−1;
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^α ,
A key calculation unit for calculating
And _{(q, G 1, G 2} , G T, e, g 1, g 2, A, B, h, g 1 ', h') and the public key pk and secret (pk, alpha, x, y) A key generation unit for key sk;
A message acquisition unit that receives a message M that is an element other than 1 on the group G ₂ ;
A signature random number generator for generating random integers ζ, ρ, ν of 1 to q−1;
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ν} ,
A signature calculation unit for calculating
A signature output unit that outputs (r, s, u, v, z) as a signature σ. G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of group G ₁ and g ₂ as an arbitrary generator of group G ₂ ,
a signature recording unit for recording q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ ;
A key random number generator for generating random integers α, β, x, y of 1 to q−1;
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^β ,
A key calculation unit for calculating
And _{(q, G 1, G 2} , G T, e, g 1, g 2, A, B, h, g 1 ', h') and the public key pk and, (pk, α, β, x, y) A key generation unit with a secret key sk,
A message acquisition unit that receives a message M that is an element other than 1 on the group G ₂ ;
A signature random number generator for generating random integers ζ, ρ, ν of 1 to q−1;
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^β M ^−x z ⁻¹ ) ^{1 / ν} ,
A signature calculation unit for calculating
A signature output unit that outputs (r, s, u, v, z) as a signature σ. G _{1, G 2} a mapping is difficult order q group of from _{G 1} to _{G 2,} a group of order q of _{G T,} bilinear mapping of _{e G 1 × G 2 → G} T, the _{g 1} An arbitrary generator of the group G ₁ , g ₂ an arbitrary generator of the group G ₂ , α, x, y, ζ, ρ, ν an integer of 1 to q−1,
h = g ₁ ^y ,
g ₁ ′ = g ₁ ^x ,
h ′ = h ^x ,
A = e (g ₁ , g ₂ ) ^α ,
B = e (h, g ₂ ) ^α ,
(Q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , A, B, h, g ₁ ′, h ′) as a public key pk,
z = g ₂ ^ζ ,
r = g ₁ ^ρ ,
u = h ^ν ,
s = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ρ} ,
v = (g ₂ ^α M ^−x z ⁻¹ ) ^{1 / ν} ,
A verification device for confirming that (r, s, u, v, z) calculated as follows is a correct signature σ,
A verification input unit for receiving the message M and the signature σ = (r, s, u, v, z);
A = e (g ₁ ′, M) e (g ₁ , z) e (r, s),
B = e (h ′, M) e (h, z) e (u, v),
A verification check unit for checking
When the verification confirmation unit confirms that all conditions are satisfied, information indicating that the signature is correct is output, and when it is determined that any condition is not satisfied, information indicating that the signature is incorrect is output. A verification device comprising: a verification output unit.   G ₁ , G ₂ G ₁ To G ₂ A group of order q difficult to map to, G _T Is a group of order q, e is G ₁ × G ₂ → G _T Bilinear mapping of g ₁ Group G ₁ Any generator of, g ₂ Group G ₂ An arbitrary generator of [alpha], [beta], x, y, [zeta], [rho], and [nu]
  h = g ₁ ^y ,
  g ₁ '= G ₁ ^x ,
  h ’= h ^x ,
  A = e (g ₁ , G ₂ ) ^α ,
  B = e (h, g ₂ ) ^α ,
(Q, G ₁ , G ₂ , G _T , E, g ₁ , G ₂ , A, B, h, g ₁ ‘, H’) as the public key pk,
  z = g ₂ ^ζ ,
  r = g ₁ ^ρ ,
  u = h ^ν ,
  s = (g ₂ ^α M ^-X z ^-1 ) ^{1 / ρ} ,
  v = (g ₂ ^β M ^-X z ^-1 ) ^{1 / ν} ,
A verification device for confirming that (r, s, u, v, z) calculated as follows is a correct signature σ,
  A verification input unit for receiving the message M and the signature σ = (r, s, u, v, z);
  A = e (g ₁ ', M) e (g ₁ , Z) e (r, s),
  B = e (h ′, M) e (h, z) e (u, v),
A verification check unit for checking
  When the verification confirmation unit confirms that all conditions are satisfied, information indicating that the signature is correct is output, and when it is determined that any condition is not satisfied, information indicating that the signature is incorrect is output. Verification output section
  A verification apparatus comprising: A program that causes a computer to function as the signature device according to claim 5 or 6 , or the verification device according to claim 7 or 8 .   A recording medium on which the program according to claim 9 is recorded.

Images