JP5330858B2 - Signature verification system, signature verification method, blind signature generation method, user device, and blind signature generation program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To verify that a user device owns a signature, without delivering the signature from the user device to a verification device. <P>SOLUTION: A prime factor q and the groups G1, G2 and GT of order q in which bilinear pairing e:G1&times;G2&rarr;GT exists are disclosed. The user device uses a commitment key ck to calculates a commitment C to information m, and transmits the results of calculating the commitment C to a signature generation apparatus as a signature request message M. The signature generation apparatus uses random numbers x, y and r belonging to generation sources g1 and g2 and Zq of the groups G1 and G2 to generate a pair of multiple elements as a signature &sigma; for M through calculation with the signature request message M and to transmit the results of generating the pair of multiple elements to the user device. The user device verifies whether a pairing equality is had for the element of the signature &sigma;, generates each non-interactive zero knowledge certification for the commitment C and for the signature &sigma;, and gives the results of generating the non-interactive zero knowledge certifications together with the information m as a blind signature to the verification device. The verification device verifies the non-interactive zero knowledge certifications. <P>COPYRIGHT: (C)2010,JPO&amp;INPIT

Description

  The present invention provides a signature verification system, a signature verification method, a blind signature generation method, a user device, which allows a user device to obtain a signature from a signature generation device and verify the validity of the signature without giving the signature to the verification device. And a blind signature generation program.

  Electronic signatures are used as basic components in various cryptographic protocols such as electronic cash and credential systems. The blind signature method is a method in which the user A can obtain the signature σ for the message M from the signer while keeping the contents of the message M secret. The user converts the signature σ obtained from the signer and submits the converted signature s to the verifier. It is possible to verify that the submitted signature s is indeed the signer's signature for M, and even if the submitted signature s is a signer, the signature s becomes the signer to the user A. There is a feature that it cannot be identified that it is given. In other words, since there is no knowledge of the direct exchange relationship of the signature s between the signer and the user, it is excellent in terms of safety. However, since the user needs to pass the signature s together with the message M to the verifier in order to verify the signature s, the signature σ transmitted from the signer to the user and the user s transmitted to the verifier. By eavesdropping the signature s and the message M, the relationship between σ, s, and M is known, which is not preferable.

  Non-Patent Document 1 proposes a blind signature scheme that can perform security proof on a universal composable model. The universal composable model is suitable for security verification when multiple protocols and cryptographic algorithms are used to form a single system, and many cryptographic tools are mixed in comparison with the random oracle model. It is a model that assumes such a complicated protocol. In the case of such a complex system, the conventional random oracle model can improve the security of the entire system even if the individual security (for example, a certain cryptographic algorithm and a certain signature algorithm) can be proved independently. It cannot be guaranteed, and if the safety of the system is shown, the whole system must be captured and recertified.

  In the universal composable model, when individual security is proved on an individual model, the security of the entire system can be shown by the accumulation, and the security of each (encryption algorithm and signature algorithm) is shown. If so, the safety of the entire system has the characteristics that can be derived from it.

Aggelos Kiayias, Hong-Sheng Zhou: "Equivocal Blind Signatures and Adaptie UC-Security", TCC 2008, pp.340-355.

  The requirements for constructing a blind signature that can be verified with the conventional universal composable model shown in Non-Patent Document 1 are complicated and difficult to understand, and require more conditions than necessary as the nature of security. Yes, and therefore inefficient. The object of the present invention is to prove that security can be proved on a universal composable model in which the user can verify that he / she has the signature for the message without giving the signature to the verifier. A signature verification system using a blind signature method, a signature verification method, a blind signature generation method, a user device, and a blind signature generation program are provided.

According to the present invention, a group G _{1 of} orders q including a user device, a signature generation device, and a verification device, and having a prime number q and bilinear pairing e: G ₁ × G ₂ → G _T exists. In the signature verification system that disclosed G ₂ and G _T ,

The user apparatus calculates a commitment C for the information m using a commitment key ck including the element g of G ₁ , h ₁ and the element h _{2 of} G ₂ , and sends a signature request message M to the signature generation apparatus. It is verified whether the pairing equation is established for the element of the signature σ transmitted and received from the signature generation apparatus. If the verification is successful, the non-interaction zero knowledge proof for the commitment C and the non-dialogue for the signature σ Each zero knowledge proof is generated and given to the verification device as a blind signature together with the information m,

The signature generation apparatus receives a signature request received from the user apparatus using random numbers x, y, r belonging to generation groups g ₁ and g _{2 of the} groups G ₁ and G ₂ and a residue group Z _q of order _q. A set of a plurality of elements that are _one of the groups G ₁ , G ₂ , and G _T is generated as a signature σ for M by operation with the message M, and is transmitted as a blind signature to the user device.

  The verification device verifies the non-dialog zero knowledge proof for the commitment received from the user device and the non-dialog zero knowledge proof for the signature using the public parameter and the commitment key, and if the verification is successful, the blind Configured to accept signatures.

  According to the signature verification system of the present invention, the user device generates a commitment C for the information m using an arbitrary value of a group of publicly available bilinear pairings, and the signature generation device uses an arbitrary value of the group. Is used to generate a signature σ for the signature request message M = C, and the user apparatus can prove that it knows the values of the group of bilinear pairings e for the commitment C and the signature σ, respectively. And is given to the verification device as a blind signature together with the information m. Therefore, a blind signature scheme capable of proving safety on the universal composable model is possible. Moreover, even if the signature from the signature device to the user device and the blind signature from the user device to the verification device are eavesdropped, the third party cannot specify the correspondence between them.

1 is a block diagram showing a signature verification system according to the present invention. The flowchart which shows an example of the process sequence by the signature verification system of FIG. FIG. 3 is a block diagram illustrating an example of a functional configuration of a user device according to the first embodiment. The flowchart which shows an example of the process sequence by the user apparatus of FIG. FIG. 3 is a block diagram illustrating an example of a functional configuration of a signature generation device according to the first embodiment. FIG. 6 is a flowchart showing an example of a processing procedure performed by the signature generation apparatus in FIG. 5. FIG. 3 is a block diagram illustrating an example of a functional configuration of a verification device according to the first embodiment. The flowchart which shows an example of the process sequence by the verification apparatus of FIG. FIG. 9 is a block diagram illustrating an example of a functional configuration of a user device according to a second embodiment. The flowchart which shows an example of the process sequence by the user apparatus of FIG. FIG. 9 is a block diagram illustrating an example of a functional configuration of a signature generation device according to a second embodiment. FIG. 12 is a flowchart showing an example of a processing procedure performed by the signature generation device of FIG. 11. FIG. 9 is a block diagram illustrating an example of a functional configuration of a verification device according to a second embodiment. FIG. 14 is a flowchart showing an example of a processing procedure performed by the verification apparatus in FIG. 13. FIG. 10 is a block diagram illustrating an example of a functional configuration of a user device according to a third embodiment. The flowchart which shows an example of the process sequence by the user apparatus of FIG. FIG. 10 is a block diagram illustrating an example of a functional configuration of a signature generation device according to a third embodiment. FIG. 18 is a flowchart showing an example of a processing procedure performed by the signature generation device in FIG. 17. FIG. 10 is a block diagram illustrating an example of a functional configuration of a verification device according to a third embodiment. The flowchart which shows an example of the process sequence by the verification apparatus of FIG. The block diagram which illustrated the hardware constitutions of the user apparatus in the signature verification system of this invention.

FIG. 1 shows an outline of a configuration of an electronic signature verification system 10 in which the present invention is implemented, and FIG. 2 shows a processing procedure in the signature verification system. The electronic signature verification system includes a user device 100, a signature generation device 200, a verification device 300, and a registration device 400. The registration device 400 previously determines a large prime number q and groups G ₁ , G ₂ , G _T of order q satisfying bilinear pairing e: G ₁ × G ₂ → G _T , and public parameters v = (q, G ₁ , G ₂ , G _T , e). G ₁ and G ₂ can calculate h ₂ ^t from h ₁ ^t for an arbitrary random number t only when the random number t is known, assuming that their arbitrary generation sources are h ₁ and h _2. It is a group having the property. Note that g ^b means that an operation defined by the group G is performed b times on gεG. As the bilinear pairing e, Weil pairing or Tate pairing can be used.

The user device 100 acquires the public parameter v from the registration device 400 in advance (S11), generates a commitment key ck based on the public parameter v, and registers it in the registration device 400 (S12). Even if the public parameter v is not requested every time a commitment is made, the public parameter v may be stored and used. The user device 100 further generates a commitment C for the input information m using the commitment key ck = (v, g, h ₁ , h ₂ ), and sends it to the signature generation device 200 as a signature request message M. (S13). Note that the public key v may not be included in the commitment key ck, and the same applies to the following embodiments.

  The signature generation apparatus 200 acquires the public parameter v from the registration apparatus 400 in advance (S21), generates a public key pk and a secret key sk based on the public parameter v, and registers the public key pk in the registration apparatus 400 (S22). ). A signature σ is generated using the secret key sk for the signature request message M, which is the commitment C received from the user device 100, and is transmitted to the user device 100 (S23).

  The user device 100 acquires the public key pk from the registration device 400 (S14), verifies the received signature σ using the public key pk (S15), and if it is valid, the non-interaction zero knowledge proof Prf (C ) And a non-interactive zero knowledge proof Prf (σ) for the blind signature σ, and sends it to the verification device 300 as a blind signature together with the information m (S16). The verification device 300 acquires the public parameter v from the registration device 400 in advance (S31), and further acquires the commitment key ck from the registration device 400 (S32). The received non-interactive zero knowledge proof Prf (C) and non-interactive zero knowledge proof Prf (σ) are verified using the public parameter v, commitment key ck, and information m (S33). If the verification succeeds, it is confirmed that the user apparatus 100 surely owns the signature σ for the commitment C corresponding to the information m, and therefore possesses the commitment C for the information m.

  Non-interactive zero-knowledge proof for commitment C and blind signature σ is a pairing group disclosed in, for example, Jens Groth, Amit Sahai, "Efficient Non-interractive Proof Systems for Bilinear Groups", EUROCRYPT 2008, pp.415-432 A non-interactive zero-knowledge proof for elements of can be used.

The outline of the above system is common to the following embodiments. Details of each embodiment will be described below. In the above description, the case where the user device 100 generates the commitment key ck = (v, g, h ₁ , h ₂ ) and registers it in the registration device 400 has been described. However, the registration device 400 generates the commitment key ck. The user apparatus 100 and the verification apparatus 300 may be provided. In that case, the commitment key generation unit 110 in the user apparatus 100 in FIG. 3 is not necessary, and step S12 in FIG. 4 is replaced with a commitment key acquisition step from the registration apparatus 400. In each of the following embodiments, a case where the user device 100 generates the commitment key ck is shown, but the registration device 400 may generate the commitment key.

[Registered device]
The registration device 400 is managed by a trusted third party or the like, and registers and discloses the public parameter v. For example, the registration device 400 includes a communication unit, a storage unit, and a control unit (not shown), and transmits the public parameter v to the user device 100, the signature generation device 200, and the verification device 300 via the communication unit. To do. Also, the public key pk is received from the signature generation device 200, registered in the storage unit, and the public key pk is transmitted to the user device 100 in response to the request. Hereinafter, it is assumed that communication with these devices is performed via a communication unit even if not specifically described. The communication unit includes, for example, a LAN adapter or the like, and is connected to a network including a LAN and the Internet. However, the user device 100, the signature generation device 200, and the verification device 300 do not necessarily have a communication unit. For example, the public parameter v may be input from an input device such as a keyboard, or a USB memory or the like. The public parameter v may be stored in the portable medium and input. Similarly, each device (user device, signature generation device, and verification device) may not have a transmission unit, and data input / output between devices may be a method other than communication. A storage unit (not shown) of the registration device 400 stores a public parameter v, a commitment key ck, a public key pk, and the like. The “registration” may mean storing in the storage unit. “Public” means that information (eg, public parameter v, commitment key ck, public key pk, etc.) can be browsed or acquired according to a user's request. The control unit controls each process.

[User device]
FIG. 3 shows a configuration example of the user device 100, and FIG. 4 shows an example of a processing procedure S100 of the user device 100. The user device 100 includes a communication unit 101, a storage unit 102, a control unit 103, a commitment key generation unit 110, a random number generation unit 120, a commitment generation unit 130, an opening information generation unit 140, and a signature verification unit. 150, a signature transformation unit 160, and a zero knowledge proof generation unit 170.

  The user device 100 according to the present embodiment executes each process under the control of the control unit 103. The user device 100 receives the public parameter v from the registration device 400. For example, the communication unit 101 communicates with the signature generation device 200, the registration device 400, and the verification device 300, receives the public parameter v from the registration device 400, and stores it in the storage unit 102 (S110). Hereinafter, it is assumed that the communication with the signature generation apparatus 200, the registration apparatus 400, and the verification apparatus 300 is performed via the communication unit 101 even if not specifically described.

  Unless otherwise indicated, each input / output data and each data in the calculation process are stored / read out in the storage unit 102 one by one, and each calculation process proceeds. However, the data need not necessarily be stored in the storage unit 102, and data may be directly transferred between the units.

The commitment key generation unit 110 receives the public parameters v = (q, G ₁ , G ₂ , G _T , e) from the storage unit 102, generates the generators g and h ₁ from G _1, and the generator h from G _{2 2} is selected at random, and a commitment key ck = (v, g, h ₁ , h ₂ ) is generated using these generation sources and registered in the registration device 400. Further, the generation source h ₁ is output to the commitment generation unit 130, and the generation source h ₂ is output to the opening information calculation unit 140 (S120).

The random number generation unit 120 generates arbitrary random numbers t and η belonging to Z _q , stores them in the storage unit 102, and outputs the random number t to the opening information calculation unit 140 and the commitment generation unit 130 (S130). Unsealing information calculation unit 140 generates based on _{h 2} and a random number t of _{G 2} is inputted, calculates the opening information ^{_{H = h 2 t (S140)}} . Thereby, the unsealing information H becomes a source of difficulty in the discrete logarithm problem. The opening information calculation unit 140 outputs the opening information H = h ₂ ^t to the zero knowledge proof generation unit 170.

The commitment generation unit 130 receives the random number t from the random number generation unit 120, the generation source g and h ₁ of G ₁ from the commitment key generation unit 120, and the information m, and generates commitment C = g ^m h ₁ ^t. The signature request message M = C is transmitted to the signature generation apparatus 200 (S150). Further, the commitment C is given to the signature verification unit 150 and the zero knowledge proof generation unit 170. Note that the information mεZ _q is data input from an auxiliary storage device or memory, or data input from an input interface, a keyboard, a mouse, or the like.

  The signature verification unit 150, the signature transformation unit 160, and the zero knowledge proof generation unit 170 will be described after the description of the next signature generation device 200.

[Signature generator]
FIG. 5 is a diagram illustrating a configuration example of the signature generation apparatus 200. FIG. 6 is a diagram illustrating an example of a processing procedure S200 of the signature generation apparatus 200. The signature generation apparatus 200 includes a communication unit 201, a storage unit 202, a control unit 203, a generation source selection unit 210, a random number generation unit 220, a public key generation unit 230, and an electronic signature generation unit 240.

  The signature generation apparatus 200 according to the present exemplary embodiment executes each process under the control of the control unit 203. The signature generation apparatus 200 is assumed to be performed via the communication unit 201 when communicating with the registration apparatus 400 and the user apparatus 100, unless otherwise specified. In addition, unless otherwise indicated, each input / output data and each data in the calculation process are stored and read in the storage unit 202 one by one, and each calculation process proceeds. However, the data need not necessarily be stored in the storage unit 202, and data may be directly transferred between the units. The signature generation apparatus 200 receives the public parameter v from the registration apparatus 400 and stores it in the storage unit 202 (S210).

The generator selection unit 210 randomly selects generators g ₁ and g ₂ from the groups G ₁ and G ₂ in the given public parameter v, receives the public parameter v, and generates the generators g ₁ and g. ₂ is output to the public key generation unit 230 and the electronic signature generation unit 240 (S220). The random number generation unit 220 generates random numbers r, x, and y belonging to Z _q , and outputs the random numbers x, y to the public key generation unit 230 and the random numbers r, x, y to the electronic signature generation unit 240 (S230). . The random number generation unit 220 secretly stores the random numbers x and y as secret keys sk = (x, y) in the storage unit 202 (S240). The secret key sk may include the corresponding public key pk, and sk = (pk, x, y). The same applies to other embodiments. Details of the public key pk will be described later.

The public key generation unit 230 receives x, y, g ₁ and g ₂ , calculates X ′ = g ₂ ^x , Y ′ = g ₂ ^y, and calculates the public key pk = (v, g ₁ , g ₂ , X ′, Y ′) is generated, sent to the registration device 400 via the communication unit 201, and registered (S250). However, the XDH assumption is assumed here. XDH is an abbreviation for The External Diffie-Hellman (XDH) assumption, and is assumed to have the following three properties when so-called elliptical pairing exists.

The discrete logarithm problem (DLP) → discrete logarithm problem The computational Diffie-Hellman problem (CDH) → the so-called DH problem The computational co-Diffie-Hellman problem (co-DH)

  Among the above, co-DH is a problem of calculating DH of a group different from the given group given the information of one group of the dual as follows, it is difficult to solve this Is assumed. Specifically, it is as follows.

The co-Diffie-Hellman (co-DH) problem on (G1; G2) is:
Let G1 and G2 be cyclic groups of order L generated by P1 and P2, respectively. The co-DH problem on (G1, G2) is to calculate aP2 given (P1; aP1; P2).

The public key pk may include pk = (i, g ₁ , g ₂ , X ′, Y ′) including key information i representing the public parameter v instead of the used public parameter v. In this case, the verification device 300 described below requests a public parameter v _i corresponding to the registration device 400 based on the key information i. When the corresponding public parameter v can be specified from the public parameters stored in the registration device 400, the public key pk includes the public parameter v, key information i for displaying the public parameter, and the like. The verification apparatus 300 requests the registration apparatus 400 for the public parameter v when the information m and the electronic signature σ are received. These also apply to other examples described later.

The electronic signature generation unit 240 receives g ₁ , g ₂ , r, x, y and the signature request message M∈G ₁ that is the commitment C received from the user apparatus 100. Five formulas a ₁ = g ₁ ^r (1)
a ₂ = M ^r (2)
a ₃ = g ₁ ^rx M ^rxy (3)
a ₄ = M ^ry (4)
a ₅ = g ₂ ^r (5)
And the set of these five values is set as the electronic signature σ = (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) ∈G ₁ ⁵ × G ₂ for the signature request message M, and Transmit (S260).

Hereinafter, the description returns to the user device 100.
The signature verification unit 150 acquires the public key pk = (v, g ₁ , g ₂ , X ′, Y ′) of the signature generation apparatus 200 from the registration apparatus 400 (S160), and the signature σ = received from the signature generation apparatus 200 (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) and the signature request message M (ie, commitment C) are verified by checking whether the following four pairing equations hold ( S170).

e (g ₁ , a ₅ ) = e (a ₁ , g ₂ ) (6)
e (M, a ₅ ) = e (a ₂ , g ₂ ) (7)
e (a ₂ , Y ′) = e (a ₄ , g ₂ ) (8)
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′) (9)

<Validity of verification>
Equation (6) can be expressed as follows using equations (1) and (5).

e (g ₁ , g ₂ ^r ) = e (g ₁ ^r , g ₂ ) (6) ′
If this is established, it is possible to confirm that the random numbers r not known to the user device 100 on both sides are the same from the property of bilinear pairing. Similarly, equation (7) can be expressed as follows using equations (1) and (2).

^{_{e (M, g 2 r)}} = e (M r, g 2) (7) '
Since the identity of r is confirmed in the expression (6) ′, it is possible to confirm that the transmitted M = C and the signature target M are the same when the expression (7) ′ is satisfied. it can. Equation (8) can be expressed as follows using equations (2) and (4), Y ′ = g ₂ ^y .

e (M ^r , g ₂ ^y ) = e (M ^ry , g ₂ ) (8) ′
Since the identity of the random number r and the identity of the message M are confirmed by the equations (6) ′ and (7) ′, it can be confirmed that the random number y is correct when the equation (8) ′ holds. Equation (9) can be expressed as follows using equations (1), (3), (4), and X ′ = g ₂ ^x .

_{^{e (g 1 rx M rxy,}} g 2) = e (g 1 r M ry, g 2 x) (9) '
Since it was confirmed that the random number r, the message M, and the random number y are correct in the expressions (6) ′, (7) ′, and (8) ′, the random number x is correct if the expression (9) ′ holds. Can be confirmed. With these processes, it can be confirmed that only the signer who knows the secret key sk = (x, y) can create the electronic signature σ.

When the signature verification unit 150 succeeds in verifying the signature σ, a non-interaction zero knowledge proof for the signature is generated and transmitted to the verification apparatus 300, but some elements of the signature σ are used as verification information as described later. Since the non-interactive zero knowledge proof is generated for the signature σ itself because it must be transmitted to the verification device 300, the signature generated in any session between the signature device and the user device from the wiretapped signature element is the current user. There is a risk that it is specified whether the data is linked to the blind signature data output from the device. Therefore, in order to increase security, the signature transformation unit 160 performs an arithmetic process on each element of the signature σ using the random number η generated by the random number generation unit 120 to thereby convert the signature σ into the signature σ ′ = (a ′ ₁ , a ' ₂ , a' ₃ , a ' ₄ , a' ₅ ) Here, it is transformed into a signature σ ′ by arithmetic processing a ′ _i = a _i ^η , i = 1,..., 5 (S180). The zero knowledge proof generation unit 170 generates the non-interactive zero knowledge proof Prf (C) for the commitment C related to the information m using the opening information H as follows.

Prf (C): NIZK {(C, H): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H) = 1} (10)
Equation (10) shows that e (C / g) indicates that user device 100 surely owns (C, H) while hiding (C, H) from verification device 300. ^This represents a non-interactive zero-knowledge proof that proves when ^{m 1} , h ₂ ) e (h ₁ ⁻¹ , H) = 1 holds.

The zero knowledge proof generation unit 170 further generates the following three non-interactive zero knowledge proofs similarly for the elements a ′ ₂ , a ′ ₃ , and a ′ _{4 in} the modified signature σ ′.

Prf (σ '): NIZK {(C, a' ₂ ): e (C, a ' ₅ ) e (a' ₂ , g ₂ ^-1 ) = 1} (11)
NIZK {(a ' ₂ , a' ₄ ): e (a ' ₂ , Y') e (a ' ₄ , g ₂ ^-1 ) = 1} (12)
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1} (13)
Equations (11), (12), and (13) indicate that (C, a ' ₂ ), (a' ₂ , a ' ₄ ), (a' ₃ , a ' ₄ ) Represents a non-interactive zero knowledge proof that proves that the user device 100 surely possesses them while the respective equations are satisfied, and puts these three zero knowledge proofs together into Prf ( σ ′). The non-interactive zero knowledge proofs Prf (C) and Prf (σ ′) are transmitted to the verification apparatus 300 together with the information m and elements a ′ ₁ and a ′ ₅ as verification information (S180).

  Any non-interactive zero knowledge proof may be used as long as it is a non-interactive zero knowledge proof for elements of a pairing group. For example, the technique shown in Non-Patent Document 2 may be used. The same applies to other examples described later.

[Verification equipment]
FIG. 7 shows the configuration of the verification apparatus 300, and FIG. 8 shows an example of the verification processing procedure S300. The verification device 300 includes a communication unit 301, a storage unit 302, a control unit 303, and a zero knowledge proof verification unit 310. The control unit 303 controls operations of the communication unit 301, the storage unit 302, and the zero knowledge proof verification unit 310. The verification device 300 communicates with the user device 100 and the registration device 400 through the communication unit 301, acquires the public parameter v = (q, G ₁ , G ₂ , G _T , e) from the registration device 400, and stores the storage unit 302. (S310), and the commitment key ck = (v, g, h ₁ , h ₂ ) is acquired from the registration device 400 and stored in the storage unit 302 (S320).

The verification apparatus 300 receives information m from the user apparatus 100 through the communication unit 301, elements a ′ ₁ and a ′ _{5 of} the signature σ ′, non-dialog zero knowledge proof Rrf (C) for the commitment C, and non-dialog zero knowledge for the signature σ ′. The proof Prf (σ ′) is received, stored in the storage unit 302, and given to the zero knowledge proof verification unit 310 (S330). The zero-knowledge proof verification unit 310 verifies that Pr (C) holds for Expression (10) using the commitment key ck and the public parameter v (S340). For Prf (σ ′), using the elements a ′ ₁ and a ′ ₅ of the signature σ ′,
e (g ₁ , a ′ ₅ ) = e (a ′ ₁ , g ₂ ) (14)
Is satisfied, and if it is satisfied, the random number r used for signature generation by the signature device 200 and the random number r (a ′ ₁ = a ₁ ^η , a ′ ₅ = a ₅ ^η received from the user device It can be confirmed that the expressions (1) and (5) match.

  It is verified by using the public parameter v that Pr. (Σ ′) further satisfies the equations (11), (12), and (13). If the verification is successful, Prf (C), Prf (σ ′) ), M is accepted as a valid blind signature (S350).

In the first embodiment, the case where the user apparatus 100 generates the commitment key ck = (v, g, h ₁ , h ₂ ) and registers it in the registration apparatus 400 has been described. The key ck may be generated and given to the user device 100 and the verification device 300 as required.

  In the second embodiment, the number of elements of the signature σ in the first embodiment is reduced by one to four, and the number of verification expressions for the signature σ is also reduced by one to three, thereby reducing the amount of processing information and accordingly processing time. Can be shortened. The basic configuration and overall processing procedure of the signature verification system according to the second embodiment are the same as those shown in FIGS. The differences are the internal configurations of the user device 100, the signature generation device 200, and the verification device 300. These will be described below.

Also in Example 2, the large prime number q assuming the same manner as in Example _{1, G 1, G 2,} G T was a group of order q, efficiently computable bilinear pairing e e: G ₁ × G ₂ → G _T and v = (q, G ₁ , G ₂ , G _T , e) are public parameters.

[User device]
FIG. 9 illustrates a configuration example of the user device 100 according to the second embodiment, and FIG. 10 illustrates an example of a processing procedure S100 of the user device 100. The user device 100 includes a communication unit 101, a storage unit 102, a control unit 103, a commitment key generation unit 110, a random number generation unit 120, a commitment generation unit 130, an opening information generation unit 140, and a signature verification unit. 151, a signature transformation unit 161, and a zero knowledge proof generation unit 171. 9, the signature verification unit 150, signature transformation unit 160, and zero knowledge proof generation unit 170 in the user device of FIG. 3 are changed to a signature verification unit 151, a signature transformation unit 161, and a zero knowledge proof generation unit 171. It has only been done. Further, in the processing procedure of FIG. 10, steps S170, S180, and S190 in the processing procedure of FIG. 4 are merely changed to steps S171, S181, and S191.

The user device 100 according to the second embodiment receives the public parameter v from the registration device 400 and stores it in the storage unit 102 (S110). Commitment key generating unit 110, the public parameter v = from the storage unit _{102 (q, G 1, G} 2, G T, e) are inputted, the generator g and _{h 1} from G _1, a generator of G ₂ h ₂ is selected at random, and a commitment key ck = (v, g, h ₁ , h ₂ ) is generated using these generation sources and registered in the registration device 400. Further, the generation source h ₁ is output to the commitment generation unit 130, and the generation source h ₂ is output to the opening information calculation unit 140 (S120).

The random number generation unit 120 generates random numbers t and η belonging to Z _q , stores them in the storage unit 102, and outputs the random number t to the unsealing information calculation unit 140 and the commitment generation unit 130 (S130). Unsealing information calculation unit 140 generates based on _{h 2} and a random number t of _{G 2} is inputted, calculates the opening information ^{_{H = h 2 t (S140)}} . Thereby, the unsealing information H becomes a source of difficulty in the discrete logarithm problem. The opening information calculation unit 140 outputs the opening information H = h ₂ ^t to the zero knowledge proof generation unit 171. The commitment generation unit 130 receives the random number t from the random number generation unit 120, the generation source g and h ₁ of G ₁ from the commitment key generation unit 120, and the information m, and generates commitment C = g ^m h ₁ ^t. The signature request message M = C is transmitted to the signature generation apparatus 200 (S150). Further, the commitment C is given to the signature verification unit 150 and the zero knowledge proof generation unit 171.

  The signature verification unit 151, the signature transformation unit 161, and the zero knowledge proof generation unit 171 will be described after the next description of the signature generation apparatus 200.

[Signature generator]
FIG. 11 shows a configuration example of the signature generation apparatus 200 according to the second embodiment, and FIG. 12 shows an example of the signature generation processing procedure S200. The signature generation apparatus 200 includes a communication unit 201, a storage unit 202, a control unit 203, a generation source selection unit 210, a random number generation unit 220, a public key generation unit 230, and an electronic signature generation unit 241. In the signature generation device of FIG. 11, only the electronic signature generation unit 240 in the signature generation device of FIG. 5 is changed to an electronic signature generation unit 241, and the processing procedure of FIG. 12 is the same as step S260 in the processing procedure of FIG. Only step S261 is changed.

The signature generation apparatus 200 according to the second embodiment receives the public parameter v from the registration apparatus 400 and stores it in the storage unit 202 (S210). The generator selection unit 210 randomly selects generators g ₁ and g ₂ from the groups G ₁ and G ₂ in the given public parameter v, receives the public parameter v, and generates the generators g ₁ and g. ₂ is output to the public key generation unit 230 and the electronic signature generation unit 240 (S220). The random number generation unit 220 generates random numbers r, x, and y belonging to Z _q , and outputs the random numbers x, y to the public key generation unit 230 and the random numbers r, x, y to the electronic signature generation unit 240 (S230). . The random number generation unit 220 secretly stores the random numbers x and y as secret keys sk = (x, y) in the storage unit 202 (S240). The secret key sk may include the corresponding public key pk, and sk = (pk, x, y). The same applies to other embodiments. Details of the public key pk will be described later.

The public key generation unit 230 receives x, y, g ₁ and g ₂ , calculates X ′ = g ₂ ^x , Y ′ = g ₂ ^y, and calculates the public key pk = (v, g ₁ , g ₂ , X ′, Y ′) is generated, sent to the registration device 400 via the communication unit 201, and registered (S250). However, the XDH assumption is assumed here as well, as described above.

The electronic signature generation unit 240 receives g ₁ , g ₂ , r, x, y and the signature request message M∈G ₁ that is the commitment C received from the user apparatus 100, and the signature request message M Unlike 1, the following four formulas a ₁ = g ₁ ^r (15)
a ₃ = g ₁ ^rx M ^rxy (16)
a ₄ = M ^ry (17)
a ₅ = g ₂ ^ry (18)
And sets of these four values as electronic signature σ = (a ₁ , a ₃ , a ₄ , a ₅ ) ∈G ₁ ⁴ × G ₂ for the signature request message M and transmits it to the user apparatus 100 ( S261).

Hereinafter, the description returns to the user apparatus 100 of FIG.
The signature verification unit 151 acquires the public key pk = (v, g ₁ , g ₂ , X ′, Y ′) of the signature generation apparatus 200 from the registration apparatus 400 (S160), and the signature σ = received from the signature generation apparatus 200 Verification of the set of (a ₁ , a ₃ , a ₄ , a ₅ ) and the signature request message M (ie, commitment C) is performed by checking whether the following three pairing equations are satisfied (S171).

e (a ₁ , Y ′) = e (g ₁ , a ₅ ) (19)
e (M, a ₅ ) = e (a ₄ , g ₂ ) (20)
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′) (21)

<Validity of verification>
Expression (19) can be expressed as follows using Expressions (15), (18) and Y ′ = g ₂ ^y .

^{_{e (g r 1, g 2}} y) = e (g 1, g 2 ry) (19) '
When this is established, it is possible to confirm that the random numbers r and y not known to the user device 100 on both sides are the same from the property of bilinear pairing. Similarly, equation (20) can be expressed as follows using equations (18) and (17).

e (M, g ₂ ^ry ) = e (M ^ry , g ₂ ) (20) ′
Since the identity of r and y is confirmed in Expression (19) ′, when Expression (18) ′ is satisfied, it is confirmed that the transmitted M = C and the signature target M are the same. be able to. Expression (21) can be expressed as follows using Expressions (15), (18), (17), and X ′ = g ₂ ^x .

_{^{e (g 1 rx M rxy,}} g 2) = e (g 1 r M ry, g 2 x) (21) '
Since it is confirmed that the random numbers r, y and the message M are correct in the equations (19) ′ and (20) ′, if the equation (21) ′ holds, it can be confirmed that the random number x is correct. Through these processes, it can be confirmed that only the signer who knows the secret key sk = (x, y) can create the electronic signature σ.

When the signature verification unit 151 succeeds in verifying the signature σ, the signature σ is converted into the signature σ ′ = (a ′ ₁ , a ′ ₃ , a ′ ₄ , using the random number η generated by the signature deformation unit 161 a ′ ₅ ), where a ′ _i = a _i ^η and i = 1, 3, 4, 5 The zero knowledge proof generating unit 171 generates the non-interactive zero knowledge proof Prf (C) for the commitment C related to the information m using the unsealing information H as follows.

Prf (C): NIZK {(C, H): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H) = 1} (22)
Equation (22) shows that the user device 100 certainly owns (C, H) while (C, H) is hidden from the verification device 300 by the equation e (C / g ^m , h ₂ ) represents a non-interactive zero knowledge proof that is proved by the fact that e (h ₁ ⁻¹ , H) = 1 holds.

The zero knowledge proof generation unit 171 further generates the following two non-interactive zero knowledge proofs similarly for the elements a ′ ₃ and a ′ _{4 in} the modified signature σ ′.

Prf (σ '): NIZK {(C, a' ₄ ): e (C, a ' ₅ ) e (a' ₄ , g ₂ ^-1 ) = 1} (23)
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1} (24)
Equations (23) and (24) indicate that the user apparatus 100 has possession of (C, a ′ ₄ ) and (a ′ ₃ , a ′ ₄ ) while the user apparatus 100 hides (C, a ′ ₄ ) and (a ′ ₃ ), respectively, from the verification apparatus. This represents a non-interactive zero knowledge proof that proves that each equation holds, and these two zero knowledge proofs are collectively expressed as Prf (σ ′). The non-interactive zero knowledge proofs Prf (C) and Prf (σ ′) are transmitted to the verification device 300 together with the information m and the elements a ′ ₁ and a ′ ₅ (S191).

[Verification equipment]
FIG. 13 shows the configuration of the verification apparatus 300 according to the second embodiment, and FIG. 14 shows the verification processing procedure S300. The verification device 300 includes a communication unit 301, a storage unit 302, a control unit 303, and a zero knowledge proof verification unit 311. In the verification device of FIG. 13, the zero knowledge proof verification unit 310 in FIG. 7 is merely changed to a zero knowledge proof verification unit 311. Further, the processing procedure of FIG. 14 is merely the change of step S350 in FIG. 8 to step S351.

The verification apparatus 300 acquires the public parameter v = (q, G ₁ , G ₂ , G _T , e) from the registration apparatus 400 and stores it in the storage unit 302 (S310), and further, the commitment key ck = (v, g, h ₁ , h ₂ ) is acquired and stored in the storage unit 302 (S320). Further, the verification device 300 receives information m from the user device 100, elements a ′ ₁ and a ′ _{5 of} the signature σ ′, a non-interactive zero knowledge proof Rrf (C) for the commitment C, and a non-interactive zero knowledge proof Prf for the signature σ ′. (σ ′) is received, stored in the storage unit 302, and given to the zero knowledge proof verification unit 311 (S330). The zero-knowledge proof verification unit 311 verifies that Pr.sub. (C) is satisfied by using the commitment key ck and the public parameter v (S340). For Prf (σ ′), using the elements a ′ ₁ and a ′ ₅ of the signature σ ′,
_{e (a '1, Y'} ) = e (g 1, a '5) (25)
Is satisfied, and if it is satisfied, the random number r used for signature generation by the signature device 200 and the random number r (a ′ ₁ = a ₁ ^η , a ′ ₅ = a ₅ ^η received from the user device It can be confirmed that the equations (15) and (18) match.

  It is verified using the public parameter v that Pr. (Σ ′) further satisfies the equations (23) and (24). If the verification is successful, Prf (C), Prf (σ ′), m The pair is accepted as a valid blind signature (S351).

Also in the second embodiment, the case where the user apparatus 100 generates the commitment key ck = (G ₁ , G ₂ , G _T , g, h ₁ , h ₂ ) and registers it in the registration apparatus 400 has been described. As described above, the registration device 400 may generate the commitment key ck and give it to the user device 100 and the verification device 300 in response to a request.

  In the third embodiment, the number of elements of the signature σ in the first embodiment is reduced by two to three, and the number of signature σ verification expressions is also reduced by two to two, thereby further increasing the amount of processing information compared to the second embodiment. This makes it possible to reduce the processing time. The basic configuration and overall processing procedure of the signature verification system according to the third embodiment are the same as those shown in FIGS. The differences are the internal configurations of the user device 100, the signature generation device 200, and the verification device 300. These will be described below.

Also in Example 3, the large prime number q assuming the same manner as in Example _{1, G 1, G 2,} G T was a group of order q, efficiently computable bilinear pairing e e: G ₁ × G ₂ → G _T and v = (q, G ₁ , G ₂ , G _T , e) are public parameters.

[User device]
FIG. 15 illustrates a configuration example of the user device 100 according to the second embodiment, and FIG. 16 illustrates an example of a processing procedure S100 of the user device 100. The user device 100 includes a communication unit 101, a storage unit 102, a control unit 103, a commitment key generation unit 110, a random number generation unit 120, a commitment generation unit 130, an opening information generation unit 140, and a signature verification unit. 152, a signature transformation unit 162, and a zero knowledge proof generation unit 172. 15, the signature verification unit 150, signature transformation unit 160, and zero knowledge proof generation unit 170 in the user device of FIG. 3 are changed to a signature verification unit 152, a signature transformation unit 162, and a zero knowledge proof generation unit 172. It has only been done. In addition, the processing procedure of FIG. 16 is merely changed from steps S170, S180, and S190 to steps S172, S182, and S192 in the processing procedure of FIG.

The user device 100 according to the third embodiment receives the public parameter v from the registration device 400 and stores it in the storage unit 102 (S110). The commitment key generation unit 110 receives the public parameters v = (q, G ₁ , G ₂ , G _T , e) from the storage unit 102, generates the generators g and h ₁ from G _1, and the generator h from G _{2 2} is selected at random, and a commitment key ck = (v, g, h ₁ , h ₂ ) is generated using these generation sources and registered in the registration device 400. Further, the generation source h ₁ is output to the commitment generation unit 130, and the generation source h ₂ is output to the opening information calculation unit 140 (S120).

The random number generation unit 120 generates random numbers t and η belonging to Z _q , stores them in the storage unit 102, and outputs the random number t to the unsealing information calculation unit 140 and the commitment generation unit 130 (S130). Unsealing information calculation unit 140 generates based on _{h 2} and a random number t of _{G 2} is inputted, calculates the opening information ^{_{H = h 2 t (S140)}} . Thereby, the unsealing information H becomes a source of difficulty in the discrete logarithm problem. The opening information calculation unit 140 outputs the opening information H = h ₂ ^t to the zero knowledge proof generation unit 172.

The commitment generation unit 130 receives the random number t from the random number generation unit 120, the generation source g and h ₁ of G ₁ from the commitment key generation unit 120, and the information m, and generates commitment C = g ^m h ₁ ^t. The signature request message M = C is transmitted to the signature generation apparatus 200 (S150). Further, the commitment C is given to the signature verification unit 150 and the zero knowledge proof generation unit 172.

  The signature verification unit 152, the signature transformation unit 162, and the zero knowledge proof generation unit 172 will be described after the description of the next signature generation device 200.

[Signature generator]
FIG. 17 shows a configuration example of the signature generation apparatus 200 according to the second embodiment, and FIG. 18 shows an example of the signature generation processing procedure S200. The signature generation apparatus 200 includes a communication unit 201, a storage unit 202, a control unit 203, a generation source selection unit 210, a random number generation unit 220, a public key generation unit 232, and an electronic signature generation unit 242. In the signature generation apparatus of FIG. 17, the public key generation unit 230 and the electronic signature generation unit 240 in the signature generation apparatus of FIG. 5 are changed to a public key generation unit 232 and an electronic signature generation unit 242. In the processing procedure of FIG. 6, steps S250 and S260 in the processing procedure of FIG. 6 are merely changed to steps S252 and S262.

The signature generation apparatus 200 according to the third embodiment receives the public parameter v from the registration apparatus 400 and stores it in the storage unit 202 (S210). The generator selection unit 210 randomly selects generators g ₁ and g ₂ from the groups G ₁ and G ₂ in the given public parameter v, receives the public parameter v, and generates the generators g ₁ and g. ₂ is output to the public key generation unit 230 and the electronic signature generation unit 240 (S220). The random number generation unit 220 generates random numbers r, x, and y belonging to Z _q , and outputs the random numbers x, y to the public key generation unit 230 and the random numbers r, x, y to the electronic signature generation unit 240 (S230). . The random number generation unit 220 secretly stores the random numbers x and y as secret keys sk = (x, y) in the storage unit 202 (S240). The secret key sk may include the corresponding public key pk, and sk = (pk, x, y). The same applies to other embodiments. Details of the public key pk will be described later.

The public key generation unit 232 receives x, y, g ₁ and g ₂ , calculates X ′ = g ₂ ^x , Y ′ = g ₂ ^y , further calculates Y = g ₁ ^y , and public key pk = (V, g ₁ , g ₂ , X ′, Y ′, Y) is generated, sent to the registration device 400 via the communication unit 201, and registered (S252). However, SXDH (asymmetric XDH) is assumed here, and even if Y ′ = g ₂ ^y and Y = g ₁ ^y are disclosed under that assumption, they are independent of each other, and each other's information is leaked. Absent. Note that the SXDH assumption is based on the above XDH assumption for both groups of pairing.

The electronic signature generation unit 242 receives g ₁ , g ₂ , r, x, y and a signature request message MεG ₁ that is the commitment C received from the user apparatus 100, and the signature request message M Unlike 1, the following three formulas a ₁ = M ^ry Y ^r (26)
a ₃ = Y ^rx M ^rxy (27)
a ₅ = g ₂ ^ry (28)
And the set of these three values is set to the electronic signature σ = (a ₁ , a ₃ , a ₅ ) εG ₁ ² × G ₂ for the signature request message M and transmitted to the user apparatus 100 (S262).

Hereinafter, the description returns to the user apparatus 100 of FIG.
The signature verification unit 152 acquires the public key pk = (v, g ₁ , g ₂ , X ′, Y ′, Y) of the signature generation apparatus 200 from the registration apparatus 400 (S160), and the signature received from the signature generation apparatus 200 Verification of the set of σ = (a ₁ , a ₃ , a ₅ ) and the signature request message M (ie, commitment C) is performed by checking whether the following two pairing equations are satisfied (S172).

e (a ₁ , g ₂ ) = e (Mg ₁ , a ₅ ) (29)
e (a ₃ , g ₂ ) = e (a ₁ , X ′) (30)

<Validity of verification>
Equation (29) can be expressed as follows using equations (26), (28) and Y = g ₁ ^y .

e ((Mg ₁ ) ^ry , g ₂ ) = e (Mg ₁ , g ₂ ^ry ) (29) ′
When this is established, it is possible to confirm that the random numbers r and y not known to the user device 100 on both sides are the same from the property of bilinear pairing. Expression (30) can be expressed as follows using Expressions (27) and (26) and X ′ = g ₂ ^x and Y = g ₁ ^y .

^{e ((Y r M ry)} x, g 2) = e (Y r M ry, g 2 x) (30) '
Since it can be confirmed that the random numbers r and y are correct in the equation (29), it can be confirmed that the message M and the random number x are correct when the equation (30) is satisfied. With these processes, it can be confirmed that only the signer who knows the secret key sk = (x, y) can create the electronic signature σ.

When the signature verification unit 152 succeeds in verifying the signature σ, the signature transformation unit 162 converts the signature σ to the signature σ ′ = (a ′ ₁ , a ′ ₃ , a ′ ₅ using the random number η generated by the random number generation unit 120. However, it is transformed into a ′ _i = a _i ^η and i = 1, 3, 5 (S182). The zero knowledge proof generation unit 172 generates the non-interactive zero knowledge proof Prf (C) for the commitment C regarding the information m using the unsealing information H as follows.

Prf (C): NIZK {(C, H): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H) = 1} (31)
Equation (31) shows that the user device 100 definitely owns (C, H) while (C, H) is hidden from the verification device 300 by the equation e (C / g ^m , h ₂ ) represents a non-interactive zero knowledge proof that is proved by the fact that e (h ₁ ⁻¹ , H) = 1 holds.

Further, similarly for the elements a ′ ₁ and a ′ ₃ in the modified signature σ ′, the following two non-interactive zero knowledge proofs are generated.

Prf (σ ′): NIZK {(C, a ′ ₁ ): e (C, a ′ ₅ ⁻¹ ) e (a ′ ₁ , g ₂ ) = 1} (32)
NIZK {(a ' ₁ , a' ₃ ): e (a ' ₃ , g ₂ ) e (a' ₁ , X ' ^-1 ) = 1} (33)
Equations (32) and (33) indicate that the user apparatus 100 has possession of (C, a ′ ₁ ) and (a ′ ₁ , a ′ ₃ ) while hiding (C, a ′ ₁ ) and (a ′ ₁ , a ′ ₃ ) from the verification apparatus, respectively. This represents a non-interactive zero knowledge proof that proves that each equation holds, and these two zero knowledge proofs are collectively expressed as Prf (σ ′). The non-interactive zero knowledge proofs Prf (C) and Prf (σ ′) are transmitted to the verification apparatus 300 together with the information m and the element a ′ ₅ (S192).

[Verification equipment]
FIG. 19 shows the configuration of the verification apparatus 300 of the second embodiment, and FIG. 20 shows an example of the verification processing procedure S300. The verification device 300 includes a communication unit 301, a storage unit 302, a control unit 303, and a zero knowledge proof verification unit 312. In the verification apparatus of FIG. 19, the zero knowledge proof verification unit 310 in FIG. Further, the processing procedure of FIG. 20 is merely the step S350 in FIG. 8 changed to step S352.

The verification apparatus 300 acquires the public parameter v = (q, G ₁ , G ₂ , G _T , e) from the registration apparatus 400 and stores it in the storage unit 302 (S310), and further, the commitment key ck = (v, g, h ₁ , h ₂ ) is acquired and stored in the storage unit 302 (S320). Further, the verification apparatus 300 receives information m from the user apparatus 100, the element a ′ ₅ of the signature σ ′, the non-interactive zero knowledge proof Rrf (C) for the commitment C, and the non-interactive zero knowledge proof Prf (σ ′) for the signature σ ′. Is stored in the storage unit 302 and given to the zero knowledge proof verification unit 312 (S330). The zero-knowledge proof verification unit 312 verifies that Pr.sub. (C) is satisfied by using the commitment key ck and the public parameter v (S340).

  It is verified by using the public parameter v that Pr. (Σ ′) further satisfies the equations (32) and (33). If the verification is successful, Prf (C), Prf (σ ′), m The pair is accepted as a valid blind signature (S350).

Also in the third embodiment, the case where the user apparatus 100 generates the commitment key ck = (G ₁ , G ₂ , G _T , g, h ₁ , h ₂ ) and registers it in the registration apparatus 400 has been described. As described above, the registration device 400 may generate the commitment key ck and give it to the user device 100 and the verification device 300 in response to a request.

<Hardware configuration>
FIG. 21 is a block diagram illustrating a hardware configuration of the user apparatus 100 in the signature verification system according to the present invention shown in FIG. The signature generation device 200, the verification device 300, and the registration device 400 can have the same configuration.

  As illustrated in FIG. 21, the user device 100 in this example includes a CPU (Central Processing Unit) 11, an input unit 12, an output unit 13, an auxiliary storage device 14, a ROM (Read Only Memory) 15, and a RAM (Random Access). Memory) 16 and a bus 17.

  The CPU 11 in this example includes a control unit 11a, a calculation unit 11b, and a register 11c, and executes various calculation processes according to various programs read into the register 11c. The input unit 12 is an input interface for inputting data, a keyboard, a mouse, and the like, and the output unit 13 is an output interface for outputting data. The auxiliary storage device 14 is, for example, a hard disk, an MO (Magneto-Optical disc), a semiconductor memory, or the like, and a program area in which programs for causing the computer to function as the signature generation device 200, the verification device 300, and the registration device 400 are stored. 14a and a data area 14b for storing various data. The RAM 16 is an SRAM (Static Random Access Memory), a DRAM (Dynamic Random Access Memory), or the like, and has a program area 16a in which the above program is stored and a data area 16b in which various data are stored. The bus 17 connects the CPU 11, the input unit 12, the output unit 13, the auxiliary storage device 14, the ROM 15, and the RAM 16 so that they can communicate with each other.

  In addition, as a specific example of such hardware, a server apparatus, a workstation, etc. other than a personal computer can be illustrated, for example.

  As described above, in the program areas 14a and 16a, the commitment key generation unit 110, the random number generation unit 120, the commitment generation unit 130, and the unsealing information calculation unit 140 of the user apparatus 100 of FIG. 3 shown in the processing procedure of FIG. , A program for executing processing of the signature verification unit 150, the signature transformation unit 160, the zero knowledge proof generation unit 170, and the like is stored. The program for executing the processing procedure of the user device 100 (FIG. 4) may be described as a single program sequence, or at least a part of the program may be stored in the library as a separate module. . In addition, each program may realize each function alone, or each program may read each other library to realize each function.

  The CPU 11 (FIG. 21) writes the above-mentioned program stored in the program area 14 a of the auxiliary storage device 14 in the program area 16 a of the RAM 16 in accordance with the read OS (Operating System) program. Similarly, the CPU 11 writes various data stored in the data area 14 b of the auxiliary storage device 14 in the data area 16 b of the RAM 16. The address on the RAM 16 where the program and data are written is stored in the register 11c of the CPU 11. The control unit 11a of the CPU 11 sequentially reads these addresses stored in the register 11c, reads a program and data from the area on the RAM 16 indicated by the read address, causes the calculation unit 11b to sequentially execute the operation indicated by the program, The calculation result is stored in the register 11c.

  The signature generation device 200, the verification device 300, and the registration device 400 can be similarly configured. 3, 5, and 7 described above are block diagrams illustrating functional configurations of the user device 100, the signature generation device 200, and the verification device 300 that are configured by the CPU 11 reading and executing the above-described program. FIG.

  For example, in the case of the signature generation device 200 of FIG. 5, the storage unit 202 corresponds to any one of the auxiliary storage device 14, the RAM 16, the register 11 c, other buffer memory and cache memory, or a storage area using these in combination. In addition, the communication unit 201, the storage unit 202, the control unit 203, the generation source selection unit 210, the random number generation unit 220, the public key generation unit 230, and the electronic signature generation unit 240 store a signature generation program in the CPU 11. It is configured by executing. The same applies to the user device 100 and the verification device 300.

  The configuration in which the present invention described with reference to FIG. 21 is implemented by a computer can be applied to the second and third embodiments.

Claims (21)

A group G ₁ , G ₂ , G _T of order q including a prime number q and bilinear pairing e: G ₁ × G ₂ → G _T , including a user device, a signature generation device, and a verification device; Is a signature verification system that
The user apparatus calculates a commitment C for the information m using a commitment key ck including the element g of G ₁ , h ₁ and the element h _{2 of} G ₂ , and sends a signature request message M to the signature generation apparatus. A commitment generator to send;
A signature verification unit that verifies whether a pairing equation holds for the element of the signature σ received from the signature generation device;
A zero-knowledge proof generator for generating a non-dialogue zero-knowledge proof for the commitment C and a non-dialogue-zero-knowledge proof for the signature σ when the verification is successful, and giving the information m as a blind signature to the verification device; Including
The signature generation apparatus, the group G _1, a generator g ₁ of G _2, g ₂ and Z _q random number belonging to the x, y, by using the r by calculation of the signature request message M received from the user device An electronic signature generation unit that generates a set of a plurality of elements as a source of any of the groups G ₁ , G ₂ , and G _T as a signature σ for M and transmits it as a blind signature to the user device,
The verification device verifies the non-dialog zero knowledge proof for the commitment received from the user device and the non-dialog zero knowledge proof for the signature using the public parameter and the commitment key, and if the verification is successful, the blind A signature verification system including a zero knowledge proof verification unit that accepts a signature. The signature verification system according to claim 1,
The user device includes a first random number generation unit that generates random numbers t and η belonging to Z _q , an unsealing information calculation unit that calculates unsealing information H ′ = h ₂ ^t from the element h ₂ and the random number t, A signature transformation unit, and the commitment generation unit calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, and The signature verification unit receives σ = (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) as the signature from the signature generation device, the commitment C = M, and the public key generated by the signature generation device The following four pairing equations using g ₁ , g ₂ , X ′, and Y ′
e (g ₁ , a ₅ ) = e (a ₁ , g ₂ )
e (M, a ₅ ) = e (a ₂ , g ₂ )
e (a ₂ , Y ′) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
The signature deforming unit processes each element a _i , i = 1,..., 5 of the signature σ with the random number η and deforms the signature σ ′ = (a ′ ₁ , a ′ ₂ , a ′ ₃ , a ′ ₄ , a ′ ₅ ) are generated and given to the zero knowledge proof generator, and the zero knowledge proof generator uses the unsealing information H ′. Non-dialogue zero knowledge proof Prf (C) for commitment C above:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₂ ): e (C, a' ₅ ) e (a ' ₂ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₂ , a' ₄ ): e (a ' ₂ , Y') e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
M, Prf the (C), Prf (σ ' ) is output as the blind signature preparative generated with the random number η treated element a' _1, a _'5 with a
The signature generation apparatus includes a second random number generation unit that generates the random numbers r, x, and y, a generation source selection unit that selects the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ , and X ′ = a public key generation unit that calculates g ₁ ^x , Y ′ = g ₂ ^y and publishes a public key pk including g ₁ , g ₂ , X ′, and Y ′, and the electronic signature generation unit includes:
a ₁ = g ₁ ^r
a ₂ = M ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^r
And outputs a set of the above a ₁ , a ₂ , a ₃ , a ₄ , a ₅ as the signature σ,
The verification apparatus uses the elements a ′ ₁ and a ′ ₅ processed with the commitment key ck and the random number η to perform the non-interactive zero knowledge proof Prf (C) for the commitment C and the modified signature σ ′. A signature verification system characterized by verifying non-interactive zero knowledge proof Prf (σ '). The signature verification system according to claim 1,
The user device includes a first random number generation unit that generates random numbers t and η belonging to Z _q , an unsealing information calculation unit that calculates unsealing information H ′ = h ₂ ^t from the element h ₂ and the random number t, A signature transformation unit, and the commitment generation unit calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, and The signature verification unit receives σ = (a ₁ , a ₃ , a ₄ , a ₅ ) as the signature from the signature generation device, and is included in the commitment C = M and the public key generated by the signature generation device. Using g ₁ , g ₂ , X ′, Y ′, the following three pairing equations
e (a ₁ , Y ′) = e (g ₁ , a ₅ )
e (M, a ₅ ) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
The signature transformation unit processes each element a _i , i = 1, 3, 4, 5 of the signature σ with the random number η and transforms the signature σ. '= (A' ₁ , a ' ₃ , a' ₄ , a ' ₅ ) is generated and given to the zero knowledge proof generator, and the zero knowledge proof generator uses the unsealing information H' to make the commitment Non-dialogue zero knowledge proof Prf (C) for C:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₄ ): e (C, a' ₅ ) e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
M, Prf the (C), Prf (σ ' ) is output as the blind signature preparative generated with the random number η treated element a' _1, a _'5 with a
The signature generation apparatus includes a second random number generation unit that generates the random numbers r, x, and y, a generation source selection unit that selects the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ , and X ′ = a public key generation unit that calculates g ₁ ^x , Y ′ = g ₂ ^y and publishes a public key pk including g ₁ , g ₂ , X ′, and Y ′, and the electronic signature generation unit includes:
a ₁ = g ₁ ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^ry
And outputs the set of a ₁ , a ₃ , a ₄ , a ₅ as the signature σ,
The verification apparatus uses the elements a ′ ₁ and a ′ ₅ processed with the commitment key ck and the random number η to perform the non-interactive zero knowledge proof Prf (C) for the commitment C and the modified signature σ ′. A signature verification system characterized by verifying non-interactive zero knowledge proof Prf (σ '). The signature verification system according to claim 1,
The user device includes a first random number generation unit that generates random numbers t and η belonging to Z _q , an unsealing information calculation unit that calculates unsealing information H ′ = h ₂ ^t from the element h ₂ and the random number t, A signature transformation unit, and the commitment generation unit calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, and The signature verification unit receives σ = (a ₁ , a ₃ , a ₅ ) as the signature from the signature generation device, and receives the commitment C = M and g ₁ , included in the public key generated by the signature generation device. Using g ₂ , X ′, Y ′, Y, the following two pairing equations
e (a ₁ , g ₂ ) = e (Mg ₁ , a ₅ )
e (a ₃ , g ₂ ) = e (a ₁ , X ′)
The signature transformation unit processes each element a _i , i = 1, 3, 5 of the signature σ with the random number η and transforms the signature σ ′ = (a ′ ₁ , a ′ ₃ , a ′ ₅ ) are generated and given to the zero knowledge proof generation unit, and the zero knowledge proof generation unit uses the unsealing information H ′ to perform non-interaction zero with respect to the commitment C. Knowledge Proof Prf (C):
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₁ ): e (C, a' ₅ ^-1 ) e (a ' ₁ , g ₂ ) = 1}
NIZK {(a ' ₁ , a' ₃ ): e (a ' ₃ , g ₂ ) e (a' ₁ , X ' ^-1 ) = 1}
'M with _{5, Prf (C), Prf} (σ' element a that has been processed by the random number η a) is output as the blind signature generating bets,
The signature generation apparatus includes a second random number generation unit that generates the random numbers r, x, and y, a generation source selection unit that selects the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ , and X ′ = a public key generator that calculates g ₁ ^x , Y ′ = g ₂ ^y , Y = g ₁ ^y , and publishes a public key pk including g ₁ , g ₂ , X ′, Y ′, Y, and The electronic signature generator
a ₁ = M ^ry Y ^r
a ₃ = Y ^rx M ^rxy
a ₅ = g ₂ ^ry
And outputs the set of a ₁ , a ₃ , a ₅ as the signature σ,
The verification device uses the element a ′ ₅ processed with the commitment key ck and the random number η , and the non-interactive zero knowledge proof Prf (C) for the commitment C and the non-interactive zero knowledge for the modified signature σ ′. A signature verification system characterized by verifying a proof Prf (σ '). 5. The signature verification system according to claim 1, further comprising a registration device that generates the commitment key in advance and gives the user device and the verification device upon request. Signature verification system. 5. The signature verification system according to claim 1, further comprising: a registration device, wherein the user device includes a commitment key generation unit that generates the commitment key and registers the registration key in the registration device. And the registration device gives the commitment key to the verification device upon request. A user apparatus used in a signature verification system in which a prime number q and a group G ₁ , G ₂ , G _T of order q in which bilinear pairing e: G ₁ × G ₂ → G _T exists are disclosed , A signature verification method by a signature generation device and a verification device,
The user apparatus calculates a commitment C for the information m using a commitment key ck including the element g of G ₁ , the element h ₁ of G _1, and the element h _{2 of} G ₂ , and sends it to the signature generation apparatus as a signature request message M A commitment generation stage to send,
The signature generation device performs an operation on the signature request message M received from the user device using the generation sources g ₁ and g _{2 of the} groups G ₁ and G _{2 and} the random numbers x, y, and r belonging to Z _q. An electronic signature generation stage for generating a set of a plurality of elements as _{one of} the groups G ₁ , G ₂ , and G _T as a signature σ for M and transmitting it to the user device;
A signature verification stage for verifying whether a pairing equation holds for the element of the signature σ received by the user device from the signature generation device;
If the verification is successful, the user device generates a non-dialogue zero knowledge proof for the commitment C and a non-dialogue zero knowledge proof for the signature σ, respectively, and gives the zero knowledge as a blind signature together with the information m to the verification device A proof generation phase;
The verification device verifies the non-interaction zero knowledge proof for the commitment received from the user device and the non-interaction zero knowledge proof for the signature using the public parameter and the commitment key, and if the verification is successful, the blind signature A signature verification method comprising a zero knowledge proof verification step for accepting. The signature verification method according to claim 7,
A first random number generation step in which the user device generates random numbers t and η belonging to Z _q , an unsealing information calculation step in which unsealing information H ′ = h ₂ ^t is calculated from the element h ₂ and the random number t; And the commitment generation step calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key. In the signature verification step, σ = (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) is received as the signature from the signature generation device, and the commitment C = M is generated by the signature generation device. The following four pairing equations using g ₁ , g ₂ , X ′, and Y ′ included in the public key
e (g ₁ , a ₅ ) = e (a ₁ , g ₂ )
e (M, a ₅ ) = e (a ₂ , g ₂ )
e (a ₂ , Y ′) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
And if so, the step of transforming the signature is to transform each of the elements a _i , i = 1,..., 5 of the signature σ with the random number η and transform the signature σ. '= (A' ₁ , a ' ₂ , a' ₃ , a ' ₄ , a' ₅ ) is generated and given to the zero knowledge proof generation stage. The zero knowledge proof generation stage includes the unsealing information H ' Use non-dialogue zero knowledge proof Prf (C) for commitment C above:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₂ ): e (C, a' ₅ ) e (a ' ₂ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₂ , a' ₄ ): e (a ' ₂ , Y') e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
M, Prf the (C), Prf (σ ' ) is output as the blind signature preparative generated with the random number η treated element a' _1, a _'5 with a
The signature generation device generates a second random number generation step for generating the random numbers r, x, and y; a generation source selection step for selecting the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ ; and X ′ = g ₁ ^x, Y '= g a ₂ ^y _{calculated, g 1, g 2, X} ' and a public key generation step of publishing the public key pk comprising Y ', the electronic signature generation step,
a ₁ = g ₁ ^r
a ₂ = M ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^r
And outputs a set of the above a ₁ , a ₂ , a ₃ , a ₄ , a ₅ as the signature σ,
The zero-knowledge proof verification stage by the verification device includes the non-interactive zero-knowledge proof Prf (C) for the commitment C using the elements a ′ ₁ and a ′ ₅ processed by the commitment key ck and the random number η A signature verification method characterized by verifying a non-interactive zero knowledge proof Prf (σ ') for a modified signature σ'. The signature verification method according to claim 7,
A first random number generation stage in which the user device generates a random number t and a random number η belonging to Z _q; an unsealing information calculation stage in which the unsealing information H ′ = h ₂ ^t is calculated from the element h ₂ and the random number t; A signature transformation stage, and the commitment generation stage calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, The signature verification stage receives σ = (a ₁ , a ₃ , a ₄ , a ₅ ) as the signature from the signature generation device, and includes the commitment C = M and the public key generated by the signature generation device. The following three pairing equations using g ₁ , g ₂ , X ′, and Y ′
e (a ₁ , Y ′) = e (g ₁ , a ₅ )
e (M, a ₅ ) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
The signature transformation stage processes each element a _i , i = 1, 3, 4, 5 of the signature σ with the random number η and transforms the signature σ. '= (A' ₁ , a ' ₃ , a' ₄ , a ' ₅ ) is generated and given to the zero knowledge proof generation stage. The zero knowledge proof generation stage uses the unsealing information H' to make the commitment Non-dialogue zero knowledge proof Prf (C) for C:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₄ ): e (C, a' ₅ ) e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
And m, Prf (C), Prf (σ ′) together with the elements a ′ ₁ and a ′ ₅ processed by the random number η are output as the blind signature,
The signature generation device generates a second random number generation step for generating the random numbers r, x, and y; a generation source selection step for selecting the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ ; and X ′ = g ₁ ^x, Y '= g a ₂ ^y _{calculated, g 1, g 2, X} ' and a public key generation step of publishing the public key pk comprising Y ', the electronic signature generation step,
a ₁ = g ₁ ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^ry
And outputs the set of a ₁ , a ₃ , a ₄ , a ₅ as the signature σ,
The zero-knowledge proof verification stage by the verification device includes the non-interactive zero-knowledge proof Prf (C) for the commitment C using the elements a ′ ₁ and a ′ ₅ processed by the commitment key ck and the random number η A signature verification method characterized by verifying the non-interaction zero knowledge proof Prf (σ ') for the modified signature σ'. The signature verification method according to claim 7,
A first random number generation step in which the user device generates random numbers t and η belonging to Z _q , an unsealing information calculation step in which unsealing information H ′ = h ₂ ^t is calculated from the element h ₂ and the random number t; A signature transformation step, wherein the commitment generation step calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, and In the signature verification stage, σ = (a ₁ , a ₃ , a ₅ ) is received as the signature from the signature generation device, the commitment C = M, and g ₁ , included in the public key generated by the signature generation device. Using g ₂ , X ′, Y ′, Y, the following two pairing equations
e (a ₁ , g ₂ ) = e (Mg ₁ , a ₅ )
e (a ₃ , g ₂ ) = e (a ₁ , X ′)
Is satisfied, and if it is satisfied, the signature transformation stage processes each element a _i , i = 1, 3, 5 of the signature σ with the random number η and transforms the signature σ ′ = (a ′ ₁ , a ′ ₃ , a ′ ₅ ) are generated and given to the zero knowledge proof generation stage. The zero knowledge proof generation stage uses the unsealing information H ′ to perform non-interaction zero for the commitment C. Knowledge Proof Prf (C):
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₁ ): e (C, a' ₅ ^-1 ) e (a ' ₁ , g ₂ ) = 1}
NIZK {(a ' ₁ , a' ₃ ): e (a ' ₃ , g ₂ ) e (a' ₁ , X ' ^-1 ) = 1}
And m, Prf (C), and Prf (σ ′) together with the element a ′ ₅ processed with the random number η are output as the blind signature,
The signature generation device generates a second random number generation step for generating the random numbers r, x, and y; a generation source selection step for selecting the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ ; and X ′ = a public key generation stage that calculates g ₁ ^x , Y ′ = g ₂ ^y , Y = g ₁ ^y and publishes a public key pk including g ₁ , g ₂ , X ′, Y ′, Y, and The electronic signature generation stage
a ₁ = M ^ry Y ^r
a ₃ = Y ^rx M ^rxy
a ₅ = g ₂ ^ry
And outputs the set of a ₁ , a ₃ , a ₅ as the signature σ,
The zero-knowledge proof verification step by the verification device includes a non-interactive zero-knowledge proof Prf (C) for the commitment C and the modified signature using the element a ′ ₅ processed with the commitment key ck and the random number η. A signature verification method characterized by verifying a non-interactive zero knowledge proof Prf (σ ') for σ'. 11. The signature verification method according to claim 7, wherein a registration device is provided, and the registration device generates the commitment key in advance and provides the user device and the verification device upon request. A signature verification method comprising steps. 11. The signature verification method according to claim 7, further comprising a registration device, wherein the user device generates the commitment key and registers the registration key in the registration device. And the registration apparatus includes the step of providing the commitment key to the verification apparatus upon request. A user apparatus used in a signature verification system in which a prime number q and a group G ₁ , G ₂ , G _T of order q in which bilinear pairing e: G ₁ × G ₂ → G _T exists are disclosed , A blind signature generation method with a signature generation device,
The user apparatus calculates a commitment C for the information m using a commitment key ck including the element g of G ₁ , the element h ₁ of G _1, and the element h _{2 of} G ₂ , and sends it to the signature generation apparatus as a signature request message M A commitment generation stage to send,
The signature generation device performs an operation on the signature request message M received from the user device using the generation sources g ₁ and g _{2 of the} groups G ₁ and G _{2 and} the random numbers x, y, and r belonging to Z _q. An electronic signature generation stage for generating a set of a plurality of elements as _{one of} the groups G ₁ , G ₂ , and G _T as a signature σ for M and transmitting it to the user device;
A signature verification stage for verifying whether a pairing equation holds for the element of the signature σ received by the user device from the signature generation device;
If the verification is successful, the user device generates a non-dialogue zero knowledge proof for the commitment C and a non-dialogue zero knowledge proof for the signature σ, and outputs them as a blind signature together with the information m. And a blind signature generation method. The blind signature generation method according to claim 13, wherein
A first random number generation step in which the user device generates random numbers t and η belonging to Z _q , an unsealing information calculation step in which unsealing information H ′ = h ₂ ^t is calculated from the element h ₂ and the random number t; And the commitment generation step calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key. In the signature verification step, σ = (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) is received as the signature from the signature generation device, and the commitment C = M is generated by the signature generation device. The following four pairing equations using g ₁ , g ₂ , X ′, and Y ′ included in the public key
e (g ₁ , a ₅ ) = e (a ₁ , g ₂ )
e (M, a ₅ ) = e (a ₂ , g ₂ )
e (a ₂ , Y ′) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
And if so, the step of transforming the signature is to transform each of the elements a _i , i = 1,..., 5 of the signature σ with the random number η and transform the signature σ. '= (A' ₁ , a ' ₂ , a' ₃ , a ' ₄ , a' ₅ ) is generated and given to the zero knowledge proof generation stage. The zero knowledge proof generation stage includes the unsealing information H ' Use non-dialogue zero knowledge proof Prf (C) for commitment C above:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₂ ): e (C, a' ₅ ) e (a ' ₂ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₂ , a' ₄ ): e (a ' ₂ , Y') e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
And m, Prf (C), Prf (σ ′) together with the elements a ′ ₁ and a ′ ₅ processed by the random number η are output as the blind signature,
The signature generation device generates a second random number generation step for generating the random numbers r, x, and y; a generation source selection step for selecting the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ ; and X ′ = g ₁ ^x, Y '= g a ₂ ^y _{calculated, g 1, g 2, X} ' and a public key generation step of publishing the public key pk comprising Y ', the electronic signature generation step,
a ₁ = g ₁ ^r
a ₂ = M ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^r
And a set of the above a ₁ , a ₂ , a ₃ , a ₄ , a ₅ is output as the signature σ. The blind signature generation method according to claim 13, wherein
A first random number generation stage in which the user device generates a random number t and a random number η belonging to Z _q; an unsealing information calculation stage in which the unsealing information H ′ = h ₂ ^t is calculated from the element h ₂ and the random number t; A signature transformation stage, and the commitment generation stage calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, The signature verification stage receives σ = (a ₁ , a ₃ , a ₄ , a ₅ ) as the signature from the signature generation device, and includes the commitment C = M and the public key generated by the signature generation device. The following three pairing equations using g ₁ , g ₂ , X ′, and Y ′
e (a ₁ , Y ′) = e (g ₁ , a ₅ )
e (M, a ₅ ) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
The signature transformation stage processes each element a _i , i = 1, 3, 4, 5 of the signature σ with the random number η and transforms the signature σ. '= (A' ₁ , a ' ₃ , a' ₄ , a ' ₅ ) is generated and given to the zero knowledge proof generation stage. The zero knowledge proof generation stage uses the unsealing information H' to make the commitment Non-dialogue zero knowledge proof Prf (C) for C:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₄ ): e (C, a' ₅ ) e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
And m, Prf (C), Prf (σ ′) together with the elements a ′ ₁ and a ′ ₅ processed by the random number η are output as the blind signature,
The signature generation device generates a second random number generation step for generating the random numbers r, x, and y; a generation source selection step for selecting the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ ; and X ′ = g ₁ ^x, Y '= g a ₂ ^y _{calculated, g 1, g 2, X} ' and a public key generation step of publishing the public key pk comprising Y ', the electronic signature generation step,
a ₁ = g ₁ ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^ry
And a set of a ₁ , a ₃ , a ₄ , and a ₅ is output as the signature σ. The blind signature generation method according to claim 13, wherein
A first random number generation step in which the user device generates random numbers t and η belonging to Z _q , an unsealing information calculation step in which unsealing information H ′ = h ₂ ^t is calculated from the element h ₂ and the random number t; A signature transformation step, wherein the commitment generation step calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ and the random number t included in the commitment key, and In the signature verification stage, σ = (a ₁ , a ₃ , a ₅ ) is received as the signature from the signature generation device, the commitment C = M, and g ₁ , included in the public key generated by the signature generation device. Using g ₂ , X ′, Y ′, Y, the following two pairing equations
e (a ₁ , g ₂ ) = e (Mg ₁ , a ₅ )
e (a ₃ , g ₂ ) = e (a ₁ , X ′)
Is satisfied, and if it is satisfied, the signature transformation stage processes each element a _i , i = 1, 3, 5 of the signature σ with the random number η and transforms the signature σ ′ = (a ′ ₁ , a ′ ₃ , a ′ ₅ ) are generated and given to the zero knowledge proof generation unit, and the zero knowledge proof generation step uses the unsealing information H ′ to perform non-interaction zero for the commitment C Knowledge Proof Prf (C):
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₁ ): e (C, a' ₅ ^-1 ) e (a ' ₁ , g ₂ ) = 1}
NIZK {(a ' ₁ , a' ₃ ): e (a ' ₃ , g ₂ ) e (a' ₁ , X ' ^-1 ) = 1}
And m, Prf (C), and Prf (σ ′) together with the element a ′ ₅ processed with the random number η are output as the blind signature,
The signature generation device generates a second random number generation step for generating the random numbers r, x, and y; a generation source selection step for selecting the generation sources g ₁ and g ₂ from the groups G ₁ and G ₂ ; and X ′ = a public key generation stage that calculates g ₁ ^x , Y ′ = g ₂ ^y , Y = g ₁ ^y and publishes a public key pk including g ₁ , g ₂ , X ′, Y ′, Y, and The electronic signature generation stage
a ₁ = M ^ry Y ^r
a ₃ = Y ^rx M ^rxy
a ₅ = g ₂ ^ry
And a set of the above a ₁ , a ₃ , and a ₅ is output as the signature σ. Use for a signature verification system in which a prime number q, a pairing e, and a group G ₁ , G ₂ , G _T of the order q in which the pairing e: G ₁ × G ₂ → G _T exists are disclosed Device,
A commitment generation unit that calculates a commitment C for the information m using a commitment key ck including the element g of G ₁ , h ₁ and the element h _{2 of} G ₂ , and sends the commitment request message M to the signature generation apparatus;
A signature verification unit that verifies whether a pairing equation is established for the element of the signature σ received from the signature generation device;
A zero-knowledge proof generating unit that generates a non-dialogue zero-knowledge proof for the commitment C and a non-dialogue zero-knowledge proof for the signature σ when the verification is successful, and outputs it as a blind signature together with the information m A user device characterized by. The user device according to claim 17 further calculates a first random number generator for generating random numbers t and η belonging to Z _q , and the opening information H ′ = h ₂ ^t from the element h ₂ and the random number t. Including an opening information calculation unit and a signature change unit,
The commitment generation unit calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ included in the commitment key and the random number t, and the signature verification unit sets the signature as the signature. The signature generation device is a ₁ = g ₁ ^r
a ₂ = M ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^r
The generated signature σ = (a ₁ , a ₂ , a ₃ , a ₄ , a ₅ ) generated by computing is received from the signature generation device, and the commitment C = M and the signature generation device generate The following four pairing equations using g ₁ , g ₂ , X ′, and Y ′ included in the public key
e (g ₁ , a ₅ ) = e (a ₁ , g ₂ )
e (M, a ₅ ) = e (a ₂ , g ₂ )
e (a ₂ , Y ′) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
The signature deforming unit processes each element a _i , i = 1,..., 5 of the signature σ with the random number η and deforms the signature σ ′ = (a ′ ₁ , a ′ ₂ , a ′ ₃ , a ′ ₄ , a ′ ₅ ) are generated and given to the zero knowledge proof generator, and the zero knowledge proof generator uses the unsealing information H ′. Non-dialogue zero knowledge proof Prf (C) for commitment C above:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₂ ): e (C, a' ₅ ) e (a ' ₂ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₂ , a' ₄ ): e (a ' ₂ , Y') e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
And m, Prf (C), and Prf (σ ′) are output as the blind signature together with the elements a ′ ₁ and a ′ ₅ processed by the random number η.
The user device according to claim 17 further calculates a first random number generator for generating random numbers t and η belonging to Z _q , and the opening information H ′ = h ₂ ^t from the element h ₂ and the random number t. Including an opening information calculation unit and a signature transformation unit,
The commitment generation unit calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ included in the commitment key and the random number t, and the signature verification unit sets the signature as the signature. The signature generation device is a ₁ = g ₁ ^r
a ₃ = g ₁ ^rx M ^rxy
a ₄ = M ^ry
a ₅ = g ₂ ^ry
The signature σ = (a ₁ , a ₃ , a ₄ , a ₅ ) generated by computing is received from the signature generation device and included in the commitment C = M and the public key generated by the signature generation device The following three pairing equations using g ₁ , g ₂ , X ′, and Y ′
e (a ₁ , Y ′) = e (g ₁ , a ₅ )
e (M, a ₅ ) = e (a ₄ , g ₂ )
e (a ₃ , g ₂ ) = e (a ₁ a ₄ , X ′)
The signature deforming unit processes each element a _i , i = 1,..., 5 of the signature σ with the random number η and deforms the signature σ ′ = (a ′ ₁ , a ′ ₂ , a ′ ₃ , a ′ ₄ , a ′ ₅ ) are generated and given to the zero knowledge proof generator, and the zero knowledge proof generator uses the unsealing information H ′. Non-dialogue zero knowledge proof Prf (C) for commitment C above:
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₄ ): e (C, a' ₅ ) e (a ' ₄ , g ₂ ^-1 ) = 1}
NIZK {(a ' ₃ , a' ₄ ): e (a ' ₃ , g ₂ ) e (a' ₁ a ' ₄ , X' ^-1 ) = 1}
And m, Prf (C), and Prf (σ ′) are output as the blind signature together with the elements a ′ ₁ and a ′ ₅ processed by the random number η. The user device according to claim 17 further calculates a first random number generator for generating random numbers t and η belonging to Z _q , and the opening information H ′ = h ₂ ^t from the element h ₂ and the random number t. Including an opening information calculation unit and a signature transformation unit,
The commitment generation unit calculates a commitment C = g ^m h ₁ ^t for the information m using the elements g and h ₁ included in the commitment key and the random number t, and the signature verification unit sets the signature as the signature. The signature generation device is a ₁ = M ^ry Y ^r
a ₃ = Y ^rx M ^rxy
a ₅ = g ₂ ^ry
The signature σ = (a ₁ , a ₃ , a ₅ ) generated by computing is received from the signature generation device, and the commitment C = M and g ₁ included in the public key generated by the signature generation device are received. Using g ₂ , X ′, Y ′, Y, the following two pairing equations
e (a ₁ , g ₂ ) = e (Mg ₁ , a ₅ )
e (a ₃ , g ₂ ) = e (a ₁ , X ′)
The signature transformation unit processes each element a _i , i = 1, 3, 5 of the signature σ with the random number η and transforms the signature σ ′ = (a ′ ₁ , a ′ ₃ , a ′ ₅ ) are generated and given to the zero knowledge proof generation unit, and the zero knowledge proof generation unit uses the unsealing information H ′ to perform non-interaction zero with respect to the commitment C. Knowledge Proof Prf (C):
NIZK {(C, H ′): e (C / g ^m , h ₂ ) e (h ₁ ⁻¹ , H ′) = 1}
And non-interactive zero knowledge proof Prf (σ ′) for the modified signature σ ′:
NIZK {(C, a ' ₁ ): e (C, a' ₅ ^-1 ) e (a ' ₁ , g ₂ ) = 1}
NIZK {(a ' ₁ , a' ₃ ): e (a ' ₃ , g ₂ ) e (a' ₁ , X ' ^-1 ) = 1}
And m, Prf (C), and Prf (σ ′) together with the element a ′ ₅ processed by the random number η are output as the blind signature. 21. A blind signature generation program for causing a computer to function as a user device for generating a blind signature according to claim 17.

Images