JP5330964B2 - Signature / verification system, signature / verification method, signature device, verification device, program - Google Patents

Description

  The present invention relates to a signature / verification system, a signature / verification method, a signature device, a verification device, and a program, 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 one of the conditions is not satisfied, information indicating that the title 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 [searched October 27, 2009], 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 October 27, 2009], 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.

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

  The signature / verification system of the present invention includes a signature device and a verification device. The signature device includes at least a signature recording unit, a signature confirmation unit, a signature random number generation unit, a signature calculation unit, and a signature output unit. The signature device may further include a key random number generation unit, a key calculation unit, and a key generation unit. The verification apparatus includes a verification input unit, a verification confirmation unit, and a verification output unit.

In the first signature-verification system of the present invention, G _{1, G 2,} the group mapping and its inverse mapping of a group of order q of G _T G ₁ → G ₂ can not be computed efficiently, e G ₁ × G ₂ → G _T pairing, g ₁ is an arbitrary generator of group G ₁ , g ₂ is an arbitrary generator of group G ₂ , and (M ₁ , M ₂ ) is on group G ₁ Message m consisting of M _{1 which} is an element other than ₁ and M ₂ which is an element of group G ₂ , x and y are arbitrary integers of 1 to q−1, X ₂ = g ₂ ^x , Y ₂ = g ₂ ^y . The key random number generation unit generates an integer x and an integer y. The key calculation unit calculates X ₂ = g ₂ ^x and Y ₂ = g ₂ ^y . The key generation unit sets (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , X ₂ , Y ₂ ) as the public key pk and (pk, x, y) as the secret key sk. . Note that Γ = (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ ) and the public key pk may be (Γ, X ₂ , Y ₂ ). The signature recording unit records q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , X ₂ , Y ₂ , x, y. The signature confirmation unit confirms that e (M ₁ , g ₂ ) = e (g ₁ , M ₂ ). The signature random number generation unit generates a random integer r of 1 to q-1. The signature calculator is
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = g ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
Calculate The signature output unit outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ. The verification input unit receives the message m and the signature σ. The verification confirmation part
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , g ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
Confirm that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ ). The verification output unit outputs information indicating that the signature is correct when the verification confirmation unit confirms that all the conditions are satisfied, and indicates that the book title is incorrect when it is confirmed that any of the conditions is not satisfied. Output information.

In the second signature / verification system of the present invention, G ₁ , G ₂ , and G _T are groups of order q, e is a bilinear map of G ₁ × G ₂ → G _T , and g ₁ and h ₁ are groups G. An arbitrary generator of ₁ , g ₂ and h ₂ (where h ₂ = g ₂ ^α ) is an arbitrary generator of group G ₂ , and (M ₁ , M ₂ ) is an element other than ₁ on group G ₁ message m composed of _{M 2} is located _{M 1} and the group _{G 2} of the original, x and y one or more q-1 following any _integer, X ₂ ⁼ h _{2 x,} and Y ² _{= g} 2 ^y. In this signature / verification system, the groups G ₁ and G ₂ may be the same group.

The key random number generation unit generates an integer x and an integer y. The key calculation unit calculates X ₂ = h ₂ ^x and Y ₂ = g ₂ ^y . The key generation unit uses (q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ , X ₂ , Y ₂ ) as the public key pk, and (pk, α, x, Let y) be the secret key sk. Note that Γ = (q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ ) may be used, and the public key pk may be (Γ, X ₂ , Y ₂ ). Signature recording _{part, q, G 1, G 2} , G T, e, g 1, h 1, g 2, h 2, X 2, Y 2, α, x, to record the y. The signature confirmation unit confirms that e (M ₁ , h ₂ ) = e (g ₁ , M ₂ ). The signature random number generation unit generates a random integer r of 1 to q-1. The signature calculator is
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = h ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
Calculate The signature output unit outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ. The verification input unit receives the message m and the signature σ. The verification confirmation part
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , h ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
Confirm that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ ). The verification output unit outputs information indicating that the signature is correct when the verification confirmation unit confirms that all the conditions are satisfied, and indicates that the book title is incorrect when it is confirmed that any of the conditions is not satisfied. Output information.

  According to the signature / verification system of the present invention, a signature can be composed of four group elements, and four pairing equations that must be confirmed by a verification apparatus can be achieved. In addition, the signature length is shortened only by changing the configuration of the signature without reducing the matters that must be confirmed by the signature (whether each element has not been forged), so there is no deterioration in security. . Therefore, it is possible to provide a digital signature method for a group element message that has a short signature length, requires a smaller amount of calculation of a verification formula, and can prove high security.

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 this invention. The figure which shows the processing flow of the signature apparatus of this invention. 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 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. The signature device 100 includes at least a signature recording unit 190, a signature confirmation unit 140, a signature random number generation unit 150, a signature calculation unit 160, and a signature output unit 170. The signature device 100 may further include a key random number generation unit 110, a key calculation unit 120, and a key generation unit 130. When the key random number generation unit 110, the key calculation unit 120, and the key generation unit 130 are not provided, the secret key sk corresponding to the public key pk is generated by a key generation device (the key random number generation unit 110, the key calculation unit 120, From the device including the key generation unit 130) and recorded in the signature recording unit 190. In the following description, a case where the key random number generation unit 110, the key calculation unit 120, and the key generation unit 130 are provided will be described. 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. In Example _1, G _1, G 2, a group of order q of _{G T G 1} → mapping and inverse mapping of _{G 2} is a group that can not be computed efficiently, the e _{G 1} × _{G 2} → pairing of G _{T, g 1} any generator of the group _{G 1,} any generator of the _{g 2} groups _{G 2,} a _(M 1, _{M 2)} other than 1 element on the group _{G 1} M message m composed of _{M 2} is ₁ and the group _{G 2} of the original, x and y one or more q-1 following any _integer, X ₂ ⁼ g _{2 x,} and Y ² _{= g} 2 ^y.

(Q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ ) are disclosed as public information Γ, and the signature recording unit 190 performs q, G ₁ , G ₂ , G _T , e, g _1, records the _{g 2.} The key random number generation unit 110 generates an integer x and an integer y (S110). The key calculation unit 120
X ₂ = g ₂ ^x
Y ₂ = g ₂ ^y
Is calculated (S120). The key generation unit 130 uses (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , X ₂ , Y ₂ ) as the public key pk, and (pk, x, y) as the secret key sk. The signature is recorded in the signature recording unit 190 (S130). The public key pk may be (Γ, X ₂ , Y ₂ ). With the processing so far, the signature recording unit 190 is in a state where q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , X ₂ , Y ₂ , x, y are recorded. The signature confirmation unit 140 confirms whether or not the condition of e (M ₁ , g ₂ ) = e (g ₁ , M ₂ ) is satisfied. If this condition is not satisfied, an error is output and the process ends. If this condition is satisfied, the process proceeds to the next process (S140). The signature random number generation unit 150 generates a random integer r between 1 and q−1 (S150). The signature calculation unit 160
A ₁ = g ₁ ^r
A ₂ = M ₁ ^ry
B ₃ = g ₂ ^rx M ₂ ^rxy
B ₄ = g ₂ ^ry
Is calculated (S160). The signature output unit 170 outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ (S170). The verification input unit 210 receives the message m and the signature σ (S210). The verification confirmation unit 220
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , g ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
It is confirmed that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ ) (S220). The verification output unit 230 outputs information (for example, “1”) indicating that the signature is correct when the verification confirmation unit 220 confirms that all the conditions are satisfied, and confirms that any of the conditions is not satisfied. In this case, information indicating that the book title is not correct (for example, “0”) is output (S230).

  According to the signature / verification system of the first embodiment, the signature can be composed of four group elements, and the number of pairing equations that must be confirmed by the verification device can be increased to four. In addition, the signature length is shortened only by changing the configuration of the signature without reducing the matters that must be confirmed by the signature (whether each element has not been forged), so there is no deterioration in security. . Therefore, it is possible to provide a digital signature method for a group element message that has a short signature length, requires a smaller amount of calculation of a verification formula, and can prove high security.

In the signature / verification system of the second embodiment, the types of components are the same as those of the first embodiment, and the processing of each component is different. FIG. 4 shows a configuration example of the signature / verification system according to the second embodiment, FIG. 5 shows a processing flow of the signature apparatus, and FIG. 6 shows a processing flow of the verification apparatus. The signature / verification system according to the second embodiment includes a signature device 300 and a verification device 400. In this figure, the signature device 300 and the verification device 400 are connected by a network 800, but the signature σ may be passed by other than the network. The signature device 300 includes at least a signature recording unit 390, a signature confirmation unit 340, a signature random number generation unit 350, a signature calculation unit 360, and a signature output unit 370. The signature device 300 may further include a key random number generation unit 310, a key calculation unit 320, and a key generation unit 330. When the key random number generation unit 310, the key calculation unit 320, and the key generation unit 330 are not provided, the public key pk and the secret key sk corresponding to the public key pk are generated by a key generation device (the key random number generation unit 310, the key calculation unit 320, From the device including the key generation unit 330) and recorded in the signature recording unit 390. In the following description, a case where the key random number generation unit 310, the key calculation unit 320, and the key generation unit 330 are provided will be described. The verification apparatus 400 includes a verification input unit 410, a verification confirmation unit 420, a verification output unit 430, and a verification recording unit 490. In Example 2, G ₁ , G ₂ , and G _T are groups of order q, e is a bilinear map of G ₁ × G ₂ → G _T , g ₁ and h ₁ are arbitrary generators of group G ₁ , g ₂ and h ₂ (where h ₂ = g ₂ ^α ) is an arbitrary generator of group G ₂ , and (M ₁ , M ₂ ) is an element other than ₁ on group G ₁ and group G ₂ A message m, x, and y consisting of M ₂ that is an element of X is an arbitrary integer between 1 and q−1, and X ₂ = h ₂ ^x and Y ₂ = g ₂ ^y . In this signature / verification system, the groups G ₁ and G ₂ may be the same group.

(Q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ ) are disclosed as public information Γ, and the signature recording unit 390 stores q, G ₁ , G ₂ , G _{T, e,} records the _{g 1, h 1, g 2} , h 2. The key random number generation unit 310 generates an integer x and an integer y (S310). The key calculation unit 320
X ₂ = h ₂ ^x
Y ₂ = g ₂ ^y
Is calculated (S320). The key generation unit 330 sets (q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ , X ₂ , Y ₂ ) as a public key pk, and (pk, α, x , Y) is a secret key sk. The public key pk may be (Γ, X ₂ , Y ₂ ). In the processing so far, the signature recording unit 390 records q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ , X ₂ , Y ₂ , α, x, y. It will be in the state. The signature confirmation unit 340 confirms whether the condition of e (M ₁ , h ₂ ) = e (g ₁ , M ₂ ) is satisfied. If this condition is not satisfied, an error is output and the process ends. If this condition is satisfied, the process proceeds to the next process (S340). The signature random number generation unit 350 generates a random integer r of 1 to q−1 (S350). The signature calculation unit 360
A ₁ = g ₁ ^r
A ₂ = M ₁ ^ry
B ₃ = h ₂ ^rx M ₂ ^rxy
B ₄ = g ₂ ^ry
Is calculated (S360). The signature output unit 370 outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ (S 370). The verification input unit 410 receives the message m and the signature σ (S410). The verification confirmation unit 420
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , h ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
It is confirmed that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ ) (S420). The verification output unit 430 outputs information (for example, “1”) indicating that the signature is correct when the verification confirmation unit 420 confirms that all the conditions are satisfied, and confirms that any of the conditions is not satisfied. In this case, information indicating that the book title is not correct (for example, “0”) is output (S430).

  Also in the signature / verification system of the second embodiment, the signature can be composed of four group elements, and the number of pairing equations that must be confirmed by the verification device can be increased to four. In addition, the signature length is shortened only by changing the configuration of the signature without reducing the matters that must be confirmed by the signature (whether each element has not been forged), so there is no deterioration in security. . Therefore, it is possible to provide a digital signature method for a group element message that has a short signature length, requires a smaller amount of calculation of a verification formula, and can prove high security.

  Further, when the above-described configuration is realized by a computer, processing contents of functions that each device should have are described by a 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, 700 Signature device 110, 310 Key random number generation unit 120, 320 Key calculation unit 130, 330 Key generation unit 140, 340 Signature confirmation unit 150, 350 Signature random number generation unit 160, 360 Signature calculation unit 170, 370 Signature output Unit 190, 390 Signature recording unit 200, 400, 900 Verification device 210, 410 Verification input unit 220, 420 Verification confirmation unit 230, 430 Verification output unit 290, 490 Verification recording unit 800 Network

Claims (13)

G _{1, G} 2, the group mapping and its inverse mapping of a group of order q of _{G T G 1} → _{G 2} can not be computed efficiently, pairing the _{e G 1 × G 2 → G} T any generator of the group _{G 1} to _{g 1,} any generator of the _{g 2} groups _{G 2, M 1} and the group _{G 2} is a _(M 1, _{M 2)} other than 1 element on the group _{G 1} of e consists _{M 2} which is the original _{(M 1, g 2) =} e (g 1, M 2) message satisfies the m, x and y one or more q-1 following any _integer, X ₂ = _g 2 ^x , Y ₂ = g ₂ ^y ,
_q, and _{G 1, G 2, G T} , e, g 1, g 2, X 2, Y 2, x, the signature recording part for recording a y,
a signature confirmation unit for confirming that e (M ₁ , g ₂ ) = e (g ₁ , M ₂ );
A signature random number generator for generating a random integer r of 1 to q−1;
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = g ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
A signature calculation unit for calculating
A signature output unit that outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ;
A verification input unit for receiving the message m and the signature σ;
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , g ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
a verification confirmation unit for confirming that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ );
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 of the conditions is not satisfied, information indicating that the title is incorrect is output. A signature / verification system comprising: a verification device comprising: a verification output unit. The signature / verification system according to claim 1,
The signature device further includes a key random number generation unit that generates an integer x and an integer y,
A key calculation unit for calculating X ₂ = g ₂ ^x and Y ₂ = g ₂ ^y ;
And _{(q, G 1, G 2} , G T, e, g 1, g 2, X 2, Y 2) of the public key pk, comprising (pk, x, y) be a key generation unit for the secret key sk and This is a signature / verification system. G ₁ , G ₂ , G _T are groups of order q, e is a bilinear map of G ₁ × G ₂ → G _T , g ₁ and h ₁ are arbitrary generators of group G ₁ , g ₂ and h ₂ (Where h ₂ = g ₂ ^α ) is an arbitrary generator of the group G ₂ , and (M ₁ , M ₂ ) is an element other than ₁ on the group G ₁ and an element M of the group G _{2 2} Tona Ri _{e (M 1, h 2)} = e (g 1, M 2) message satisfies the m, x and y one or more q-1 following any ^{_{integer, X 2 = h 2 x,}} Y 2 = G ₂ ^y ,
_q, and _{G 1, G 2, G T} , e, g 1, h 1, g 2, h 2, X 2, Y 2, α, x, the signature recording part for recording a y,
a signature confirmation unit for confirming that e (M ₁ , h ₂ ) = e (g ₁ , M ₂ );
A signature random number generator for generating a random integer r of 1 to q−1;
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = h ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
A signature calculation unit for calculating
A signature output unit that outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ;
A verification input unit for receiving the message m and the signature σ;
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , h ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
a verification confirmation unit for confirming that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ );
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 of the conditions is not satisfied, information indicating that the title is incorrect is output. A signature / verification system comprising: a verification device comprising: a verification output unit. The signature / verification system according to claim 3,
The signature device further includes a key random number generation unit that generates an integer x and an integer y,
A key calculation unit for calculating X ₂ = h ₂ ^x and Y ₂ = g ₂ ^y ;
And _{(q, G 1, G 2} , G T, e, g 1, h 1, g 2, h 2, X 2, Y 2) a public key pk, (pk, α, x , y) and private key A signature / verification system comprising a key generation unit for sk. A signature / verification method in a signature / verification system including a signature device and a verification device,
G _{1, G} 2, the group mapping and its inverse mapping of a group of order q of _{G T G 1} → _{G 2} can not be computed efficiently, pairing the _{e G 1 × G 2 → G} T any generator of the group _{G 1} to _{g 1,} any generator of the _{g 2} groups _{G 2, M 1} and the group _{G 2} is a _(M 1, _{M 2)} other than 1 element on the group _{G 1} of _{M 2} Tona Ri _e is the original _{(M 1, g 2) =} e (g 1, M 2) message satisfies the m, x and y one or more q-1 following any _{integer, X} 2 = g ₂ ^x , Y ₂ = g ₂ ^y
In the signature device,
Q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ are recorded in advance in the signature recording unit,
A key random number generation unit for generating an integer x and an integer y;
A key calculation step in which the key calculation unit calculates X ₂ = g ₂ ^x and Y ₂ = g ₂ ^y ;
The key generation unit sets (q, G ₁ , G ₂ , G _T , e, g ₁ , g ₂ , X ₂ , Y ₂ ) as the public key pk and (pk, x, y) as the secret key sk. A key generation step;
A signature confirmation step in which the signature confirmation unit confirms that e (M ₁ , g ₂ ) = e (g ₁ , M ₂ );
A signature random number generation unit for generating a random integer r between 1 and q−1;
The signature calculation department
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = g ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
A signature calculation step for calculating
A signature output unit including a signature output step of outputting (A ₁ , A ₂ , B ₃ , B ₄ ) 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 ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , g ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
a verification check step for confirming that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ );
The verification output unit outputs information indicating that the signature is correct when the verification confirmation step confirms that all conditions are satisfied, and confirms that the title is not correct when it is confirmed that any of the conditions is not satisfied. 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 ₁ , G ₂ , G _T are groups of order q, e is a bilinear map of G ₁ × G ₂ → G _T , g ₁ and h ₁ are arbitrary generators of group G ₁ , g ₂ and h ₂ (Where h ₂ = g ₂ ^α ) is an arbitrary generator of the group G ₂ , and (M ₁ , M ₂ ) is an element other than ₁ on the group G ₁ and an element M of the group G _{2 2} Tona Ri _{e (M 1, h 2)} = e (g 1, M 2) message satisfies the m, x and y one or more q-1 following any ^{_{integer, X 2 = h 2 x,}} Y 2 = G ₂ ^y ,
In the signature device,
In the signature recording unit, q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ are recorded in advance,
A key random number generation unit for generating an integer x and an integer y;
A key calculation step in which the key calculation unit calculates X ₂ = h ₂ ^x and Y ₂ = g ₂ ^y ;
The key generation unit sets (q, G ₁ , G ₂ , G _T , e, g ₁ , h ₁ , g ₂ , h ₂ , X ₂ , Y ₂ ) as the public key pk, and (pk, α, x, a key generation step using y) as a secret key sk;
A signature confirmation step in which the signature confirmation unit confirms that e (M ₁ , h ₂ ) = e (g ₁ , M ₂ );
A signature random number generation unit for generating a random integer r between 1 and q−1;
The signature calculation department
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = h ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
A signature calculation step for calculating
A signature output unit including a signature output step of outputting (A ₁ , A ₂ , B ₃ , B ₄ ) 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 ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , h ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
a verification check step for confirming that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ );
The verification output unit outputs information indicating that the signature is correct when the verification confirmation step confirms that all conditions are satisfied, and confirms that the title is not correct when it is confirmed that any of the conditions is not satisfied. And a verification output step for outputting information indicating the signature / verification method. G _{1, G} 2, the group mapping and its inverse mapping of a group of order q of _{G T G 1} → _{G 2} can not be computed efficiently, pairing the _{e G 1 × G 2 → G} T any generator of the group _{G 1} to _{g 1,} any generator of the _{g 2} groups _{G 2, M 1} and the group _{G 2} is a _(M 1, _{M 2)} other than 1 element on the group _{G 1} of _{M 2} Tona Ri _e is the original _{(M 1, g 2) =} e (g 1, M 2) message satisfies the m, x and y one or more q-1 following any _{integer, X} 2 = g ₂ ^x , Y ₂ = g ₂ ^y
_q, and _{G 1, G 2, G T} , e, g 1, g 2, X 2, Y 2, x, the signature recording part for recording a y,
a signature confirmation unit for confirming that e (M ₁ , g ₂ ) = e (g ₁ , M ₂ );
A signature random number generator for generating a random integer r of 1 to q−1;
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = g ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
A signature calculation unit for calculating
And a signature output unit that outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ. The signature device according to claim 7,
A key random number generator for generating an integer x and an integer y;
A key calculation unit for calculating X ₂ = g ₂ ^x and Y ₂ = g ₂ ^y ;
And _{(q, G 1, G 2} , G T, e, g 1, g 2, X 2, Y 2) of the public key pk, comprising (pk, x, y) be a key generation unit for the secret key sk and The signature apparatus characterized by the above-mentioned. G ₁ , G ₂ , G _T are groups of order q, e is a bilinear map of G ₁ × G ₂ → G _T , g ₁ and h ₁ are arbitrary generators of group G ₁ , g ₂ and h ₂ (Where h ₂ = g ₂ ^α ) is an arbitrary generator of the group G ₂ , and (M ₁ , M ₂ ) is an element other than ₁ on the group G ₁ and an element M of the group G _{2 2} Tona Ri _{e (M 1, h 2)} = e (g 1, M 2) message satisfies the m, x and y one or more q-1 following any ^{_{integer, X 2 = h 2 x,}} Y 2 = G ₂ ^y ,
_q, and _{G 1, G 2, G T} , e, g 1, h 1, g 2, h 2, X 2, Y 2, α, x, the signature recording part for recording a y,
a signature confirmation unit for confirming that e (M ₁ , h ₂ ) = e (g ₁ , M ₂ );
A signature random number generator for generating a random integer r of 1 to q−1;
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = h ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
A signature calculation unit for calculating
And a signature output unit that outputs (A ₁ , A ₂ , B ₃ , B ₄ ) as a signature σ. The signature device according to claim 9, comprising:
A key random number generator for generating an integer x and an integer y;
A key calculation unit for calculating X ₂ = h ₂ ^x and Y ₂ = g ₂ ^y ;
And _{(q, G 1, G 2} , G T, e, g 1, h 1, g 2, h 2, X 2, Y 2) a public key pk, (pk, α, x , y) and private key A signature apparatus comprising a key generation unit for sk. G _{1, G} 2, the group mapping and its inverse mapping of a group of order q of _{G T G 1} → _{G 2} can not be computed efficiently, pairing the _{e G 1 × G 2 → G} T any generator of the group _{G 1} to _{g 1,} any generator of the _{g 2} groups _{G 2, M 1} and the group _{G 2} is a _(M 1, _{M 2)} other than 1 element on the group _{G 1} of _{M 2} Tona Ri _e is the original _{(M 1, g 2) =} e (g 1, M 2) messages satisfy m, x, y and r to 1 or q-1 following any integer, _{X 2} = G ₂ ^x , Y ₂ = g ₂ ^y
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = g ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
(A ₁ , A ₂ , B ₃ , B ₄ ) calculated as follows:
A verification input unit for receiving the message m and the signature σ;
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , g ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
a verification confirmation unit for confirming that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ );
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 of the conditions is not satisfied, information indicating that the title is incorrect is output. A verification device comprising: a verification output unit. G ₁ , G ₂ , G _T are groups of order q, e is a bilinear map of G ₁ × G ₂ → G _T , g ₁ and h ₁ are arbitrary generators of group G ₁ , g ₂ and h ₂ (Where h ₂ = g ₂ ^α ) is an arbitrary generator of the group G ₂ , and (M ₁ , M ₂ ) is an element other than ₁ on the group G ₁ and an element M of the group G _{2 2} Tona Ri _{e (M 1, h 2)} = e (g 1, M 2) messages satisfy m, x, y and r to 1 or q-1 following any _integer, X _{² =} ^h _{2 x,} Y ₂ = g ₂ ^y
A ₁ = g ₁ ^r ,
A ₂ = M ₁ ^ry ,
B ₃ = h ₂ ^rx M ₂ ^rxy ,
B ₄ = g ₂ ^ry
(A ₁ , A ₂ , B ₃ , B ₄ ) calculated as follows:
A verification input unit for receiving the message m and the signature σ;
A ₁ and M _{1 are} elements other than ₁ on the group G ₁ ;
e (M ₁ , h ₂ ) = e (g ₁ , M ₂ )
e (A ₁ , Y ₂ ) = e (g ₁ , B ₄ )
e (A ₂ , g ₂ ) = e (M ₁ , B ₄ ),
a verification confirmation unit for confirming that e (g ₁ , B ₃ ) = e (A ₁ A ₂ , X ₂ );
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 of the conditions is not satisfied, information indicating that the title is incorrect is output. A verification device comprising: a verification output unit.   A program for operating a computer as the signature device according to any one of claims 7 to 10 or the verification device according to claim 11 or 12.

Images